We are announcing a new revision of the LEDAcrypt specification (full document) introducing several improvements.

  • We address the existence of weak keys, as pointed out by NIST at the last Dagstuhl seminar on Quantum Cryptanalysis, due to the product structure of the secret parity-check matrix of the public codes. We made the conservative choice of selecting parametrizations of LEDAcrypt that entirely avoids the product structure (i.e., picking Q=I in the H*Q product), which is guaranteed to prevent the existence of such weak keys.

  • We provide a complete description of our construction to obtain an IND-CCA2 KEM, detailing our official comment posted on July 5th, 2019 and providing a proof of its IND-CCA2 guarantees. In particular, this construction addresses the definition discrepancy between delta-correctness and decoding failure rate.

  • We provide a new technique to predict the DFR of our in-place bit flipping decoder, in addition to the previous one for our out-of-place bit flipping decoder, along with its validation through numerical simulations. We remark that these models do not rely on any curve extrapolation. We design the IND-CPA parameters applying the out-of-place decoder and provide the IND-CCA2 parameters with both decoding approaches and their combination, while employing a fixed number of iterations to support constant time implementation.

  • Based on these improvements, we provide new parameter sets, which result in a decrease of the public key and ciphertext size in the range of 5%–25% for IND-CPA parameters, and in the range of 30%–50% for IND-CCA2 parameters.

  • We are in the progress of updating the associated software package, to provide a constant time implementation of the IND-CCA primitives, together with a performance analysis which will select either the in- place or the out-of-place decoding strategy in the light of keysize- vs-computing speed tradeoffs.