International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of LEDAcrypt

Authors:
Ray Perlner , National Institute of Standards and Technology, USA
Angela Robinson , National Institute of Standards and Technology, USA
Daniel Apon , National Institute of Standards and Technology, USA
Paolo Santini , Universita Politecnica delle Marche, Italy, Florida Atlantic University, USA
Download:
DOI: 10.1007/978-3-030-56877-1_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: 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.79}$ 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.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30535,
  title={Cryptanalysis of LEDAcrypt},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56877-1_14},
  author={Ray Perlner and Angela Robinson and Daniel Apon and Paolo Santini},
  year=2020
}