Paper 2020/455

Cryptanalysis of LEDAcrypt

Daniel Apon, Ray Perlner, Angela Robinson, and Paolo Santini


We report on the concrete cryptanalysis of LEDAcrypt, a 2nd Round candidate in NIST's Post-Quantum Cryptography standardization process and one of 17 encryption schemes that remain as candidates for near-term standardization. LEDAcrypt consists of a public-key encryption scheme built from the McEliece paradigm and a key-encapsulation mechanism (KEM) built from the Niederreiter paradigm, both using a quasi-cyclic low-density parity-check (QC-LDPC) code. In this work, we identify a large class of extremely weak keys and provide an algorithm to recover them. For example, we demonstrate how to recover 1 in $2^{47.72}$ of LEDAcrypt's keys using only $2^{18.72}$ guesses at the 256-bit security level. This is a major, practical break of LEDAcrypt. Further, we demonstrate a continuum of progressively less weak keys (from extremely weak keys up to all keys) that can be recovered in substantially less work than previously known. This demonstrates that the imperfection of LEDAcrypt is fundamental to the system's design.

Note: Fixed a few typos

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
NIST PQCLEDAcryptMcElieceQC-LDPCCryptanalysis
Contact author(s)
daniel apon @ nist gov
ray perlner @ nist gov
angela robinson @ nist gov
p santini @ pm univpm it
2020-04-20: last of 2 revisions
2020-04-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Apon and Ray Perlner and Angela Robinson and Paolo Santini},
      title = {Cryptanalysis of LEDAcrypt},
      howpublished = {Cryptology ePrint Archive, Paper 2020/455},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.