In 2017, the National Institute of Standards and Technology (NIST) first began running a competition to select the best quantum-resistant algorithmic standard. The candidates are mostly code- and lattice-based systems. Even though lattice-based candidates tend to be more efficient, their hardness is not as well studied and understood as code-based schemes.
Code-based algorithms work via error-correction. Therefore, an error-term is added to the data for encryption, hiding the plain text. The code in combination with a decoding-secret then allows the error to be corrected and, hence, recovers the data. The code is publicly known (public key), as it defines the kind of data that can be encrypted. Only the code coupled with the decoding-secret (secret key) enables efficient decoding. The Classic McEliece scheme follows this principle.
As the only non-lattice-based NIST encryption finalist the McEliece algorithm is a public-key cryptosystem - and requires different keys for encryption (public key) and decryption (secret key). The security of the system relies on the fact that decrypting a ciphertext without knowing the secret key is not feasible.
A cryptanalysis team at CRC has set new records in computation – the team was able to decrypt a (reduced) McEliece ciphertext without knowing the secret key and, thus, claimed the first two places at INRIA’s McEliece decoding challenge. Its record computation took about 31.4 days of computation time on a cluster using 256 CPU-cores, which corresponds to 256 * 31.4 = 8038.4 CPU months, which is about 22 CPU Years. This allowed the team to secure the first place, which was previously held by Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto from Information Security Laboratory at KDDI Research Inc., Fujimino, Japan.
In the same attempt, the team achieved multiple other records in different decoding disciplines. These included the first five places for decoding quasi-cyclic codes, which form the basis of two other post quantum secure code-based public key encryption candidates BIKE and HQC. The previous record-holder Noémie Bossard, was an independent contestant. In addition, the team claimed the first five first places in the category of decoding ternary codes, previously held by Nicolas Bordes and Pierre Karpman from Université Grenoble Alpes, CNRS, France. These codes are the basis of the post-quantum signature scheme WAVE.
CRC’s successful results were published in a scientific paper titled ‘McEliece needs a Break – Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD’, which will appear at Eurocrypt 2022, a prestigious cryptography conference.
The work – a collaboration between TII and Ruhr University Bochum - is attributed to a team comprising Dr. Andre Esser, Senior Crypto Analyst at CRC, Floyd Zweydinger, a PhD student at Ruhr University Bochum, currently an intern at CRC, and Dr. Alexander May, Professor at Ruhr University Bochum and Scientific Advisor for TII.
Highlighting the significance of the competition, Dr. Esser said: “It was a combination of both practical experiments and theoretical estimation. To obtain these records, we implemented for the first time advanced ‘information set decoding’ algorithms. These are a class of algorithms that allow generic decoding attacks, i.e., they can be applied to nearly all code-based schemes.”
When assessing the security of a cryptographic scheme it is common practice to break the scheme into smaller instances, that is decreasing the parameters of the scheme (making it less secure) until the scheme can be broken. The team obtained practical timings to enhance the trust in the security estimate, which is a theoretical estimation of the number of operations required to break the scheme.
Using its newly obtained record computations, the team can now extrapolate the hardness of cryptographic sized instances and offer a more precise estimate of the security of the schemes.
