Decoding Random Binary Linear Codes in 2^(n/20): How 1+1=0 Improves Information Set Decoding

Anja Becker · Antoine Joux · Alexander May · Alexander Meurer

Eurocrypt 2012

Time bound

2^{0.102 n + o(n)}

Space bound

—

Source / version date

20 Jan 2012

Comparison variant

Binary · full GV distance

Cost scale

2^{c n + o(n)}

Code alphabet

𝔽₂

Rate convention

Maximize over 0≤R≤1

Error weight

Full GV distance: n H₂⁻¹(1−R)

Computation model

Classical random-code ISD analysis

reference

BJMM12

coefficient_source

https://link.springer.com/chapter/10.1007/978-3-662-46800-5_9

Assumptions and source notes

Rounded full-distance coefficient stated in May–Ozerov 2015 abstract; 0.0494 is the different half-distance bound.

Primary source ↗

@misc{paper-f1a990a4cd6f,
  author = {Anja Becker and Antoine Joux and Alexander May and Alexander Meurer},
  title = {{Decoding Random Binary Linear Codes in 2^(n/20): How 1+1=0 Improves Information Set Decoding}},
  year = {2012},
  url = {https://eprint.iacr.org/2012/026},
  cr_date = {2012-01-20},
  cr_status = {published},
  cr_author_ids = {anja-becker; antoine-joux; alexander-may; alexander-meurer},
  howpublished = {EUROCRYPT 2012; full version Cryptology ePrint Archive, Paper 2012/026}
}