Paper 2011/367

Decoding One Out of Many

Nicolas Sendrier

Abstract

Generic decoding of linear codes is the best known attack against most code-based cryptosystems. Understanding and measuring the complexity of the best decoding technique is thus necessary to select secure parameters. We consider here the possibility that an attacker has access to many cryptograms and is satisfied by decrypting (i.e.\ decoding) only one of them. We show that, in many cases of interest in cryptology, a variant of Stern's collision decoding can be adapted to gain a factor almost $\sqrt{N}$ when $N$ instances are given. If the attacker has access to an unlimited number of instances, we show that the attack complexity is significantly lower, in fact raised by a power slightly larger than $2/3$. Finally we give indications on how to counter those attacks.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
code-based cryptography
Contact author(s)
nicolas sendrier @ inria fr
History
2011-07-10: received
Short URL
https://ia.cr/2011/367
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/367,
      author = {Nicolas Sendrier},
      title = {Decoding One Out of Many},
      howpublished = {Cryptology ePrint Archive, Paper 2011/367},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/367}},
      url = {https://eprint.iacr.org/2011/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.