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 247.72 of LEDAcrypt’s keys using only 218.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. © International Association for Cryptologic Research 2020.

Cryptanalysis of LEDAcrypt / Apon, D.; Perlner, R.; Robinson, A.; Santini, P.. - 12172:(2020), pp. 389-418. (Intervento presentato al convegno 40th Annual International Cryptology Conference, CRYPTO 2020 tenutosi a Santa Barbara, USA nel August 2020) [10.1007/978-3-030-56877-1_14].

Cryptanalysis of LEDAcrypt

Santini, P.
2020-01-01

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 247.72 of LEDAcrypt’s keys using only 218.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. © International Association for Cryptologic Research 2020.
2020
Lecture Notes in Computer Science
978-303056876-4
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11566/287574
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact