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.0494 n + o(n)}

Space bound

—

Source / version date

20 Jan 2012

Comparison variant

Binary · half distance

Cost scale

2^{c n + o(n)}

Field

𝔽₂

Code rate convention

Worst rate in the half-distance convention

Error-weight regime

Half the GV distance

Cost model

Asymptotic ISD operation count

reference

BJMM12

Assumptions and source notes

EUROCRYPT 2012. Historical asymptotic half-distance bound, maximized over rates. This coefficient must not be transferred to full-distance decoding or a fixed-rate instance.

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}
}