LWE · Binary secret and error · hybrid models

Binary secret and error · hybrid models

Uniform binary secret and error; exact finite n,m,q and preprocessing cost specified

2 results · 1 papers

ClassicalHeuristic / model-dependentUniform random LWE samples; explicit parameter contractParameter-dependent time and space expressions

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
—	On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle AttackJohannes Buchmann · Florian Göpfert · Rachel Player · Thomas WundererAfricacrypt 2016Source BibTeX / detailsbinary error binary secret hybrid heuristic cost	13 Apr 2016	T_reduce(m,δ) + 2¹⁶ binom(r,c) / sqrt(p·binom(2c,c)), r=4c	Collision tables scale with the number of guessed/stored partial secrets; source theorem does not give a common cn memory coefficient.	PublishedSource checked
—	On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle AttackJohannes Buchmann · Florian Göpfert · Rachel Player · Thomas WundererAfricacrypt 2016Source BibTeX / detailsfinite instance binary error hybrid historical estimate	13 Apr 2016	Approximately 2⁸⁵ bit operations for (n,m,q)=(256,512,256)	No numerical space estimate extracted.	PublishedSource checked

Comparison definition & assumptions

Regime: Uniform binary secret and error; exact finite n,m,q and preprocessing cost specified
Computation: Classical
Rigor: Heuristic / model-dependent
Instances: Uniform random LWE samples; explicit parameter contract
Cost scale: Parameter-dependent time and space expressions
Parameter: n, q, error width, secret distribution, sample budget and attack parameters
Description: Historical LWE bounds and cost models with parameters retained. Entries without a common fixed asymptotic scale are listed without a numerical rank.
Comparison rules: Specify q(n), error distribution and width convention, secret distribution, available samples, search versus decision objective, success criterion and lattice/algebraic assumptions. Formula-only entries have null coefficients. A concrete instance estimate is not an exponent c in 2^{cn}.
Tags: binary error, binary secret, hybrid, finite instance