Cryptanalysis of LEDAcrypt (a 2nd round NIST Post-Quantum Cryptography candidate)

Add to your list(s) Download to your calendar using vCal

• Daniel Apon, National Institute of Standards and Technology (NIST) of the US
• Monday 21 October 2019, 14:00-15:00
• Room 909B, EEE Building.

If you have a question about this talk, please contact Cong Ling.

LED Acrypt is a code-based key-encapsulation / public-key encryption candidate in NIST ’s Post-Quantum Cryptography standardization effort, which is now in its 2nd round with 26 remaining candidates. LED Acrypt is a McEliece style cryptosystem based on a unique type of QC-LDPC (Quasi-Cyclic Low-Density Parity-Check) code, whose origins date back to 2008.

In this talk, I will present the first substantial attack against LED Acrypt in its 11-year history. In particular, LED Acrypt uses a type of “product structure” when generating its keys, which I will demonstrate leads to large classes of weak public-secret key pairs. As an example, for a parameter set that should require (for every honest key-gen) at least 2^{256 bit operations to break, the attack will succeed against 1 out of ₂}40 of key-gens, with only 2^{20 (large) matrix inversions equalling the work of about ~2}55 bit operations.

Mathematical maturity will be assumed (but no special knowledge of code-based cryptography).

Bio. Daniel Apon received his PhD in Computer Science with an emphasis on cryptography in 2017 from the University of Maryland, advised by Johnathan Katz. He then spent a year in a postdoctoral position at the University of California, Berkeley, hosted by Sanjam Garg, before joining the National Institute of Standards and Technology (NIST) a little over a year ago to work on their international post-quantum cryptography effort.

His background includes expertise in cryptographic program obfuscation (building the first open-source indistinguishability obfuscator with colleagues from Stanford, Yale, etc.— then a year later, breaking it!), as well as in lattice-based cryptography especially.

This talk is part of the COMMSP Seminar series.

This talk is included in these lists:

• COMMSP & CP list
• COMMSP Seminar
• Room 909B, EEE Building
• SAP Talks

Note that ex-directory lists are not shown.