It is the final round of the NIST (National Institute of Standards and Technology) Post Quantum Cryptography Standardization process - and among the finalists are numerous members of the Cluster of Excellence "CASA – Cyber Security in the Age of Large-Scale Adversaries." Four out of seven proposals on "Public-key Encryption and Key-establishment" (Classic McEliece, CRYSTALS-KYBER) and "Digital Signature" (CRYSTALS-DILITHIUM, Rainbow) algorithms are submitted with the participation of PIs Daniel Bernstein, Tim Güneysu, Eike Kiltz and Tanja Lange and postdoc Ming-Shing Chen. "Quantum-Resistant Cryptography" represents a core topic (research challenge) within the Cluster of Excellence.
CASA members are also involved in the proposals that made it to the round as alternate candidates: BIKE, NTRU Prime, SPHINCS+. Another participant in the finalist NTRU is Peter Schwabe, who will work at the Max Planck Institute for Cybersecurity and Privacy in Bochum, which is closely associated with CASA. A detailed list can be found at the end of the article.
Selection round forms first post-quantum cryptography standard
According to NIST, this "selection round" will help the agency decide on the small subset of these algorithms that will form the core of the first post-quantum cryptography standard. "The likely outcome is that at the end of this third round, we will standardize one or two algorithms for encryption and key establishment, and one or two others for digital signatures," NIST mathematician Dustin Moody says in a NIST press release. "But by the time we are finished, the review process will have been going on for five or six years, and someone may have had a good idea in the interim. So we'll find a way to look at newer approaches too."
The NIST standardization is of particular interest because current encryption methods would no longer withstand quantum computers' use. Since the news about Google's quantum supremacy, it is clear that this new technology is no longer a future vision. Since quantum computers would work differently from conventional computers, the current public-key encryption and signature systems would theoretically be obsolete. Digital communication would be less protected.
Sustainable security for encryption
The NIST standardization process for post-quantum cryptography began in 2017 with 69 candidate algorithms, and the finalists were selected from the 26 candidates in the second round. The new public-key cryptography standards are intended to specify one or more digital signatures, public-key encryption, and key-enabling algorithms to complement existing standards. The aim is to provide sustainable security for encryption.
Overview to the abstracts of the finalists
BIKE - Bit Flipping Key Encapsulation
Abstract
This document presents BIKE, a suite of algorithms for key encapsulation based on quasi-cyclic moderate density parity-check (QC-MDPC) codes that can be decoded using bit flipping decoding techniques. In particular, this document highlights the number of security, performance and simplicity advantages that make BIKE a compelling candidate for post-quantum key encapsulation standardization.
Participants
- Tim Güneysu (CASA)
- Nicolas Aragon
- Paulo S. L. M. Barreto
- Slim Bettaieb
- Loïc Bidoux
- Olivier Blazy
- Jean-Christophe Deneuville
- Philippe Gaborit
- Shay Gueron
- Carlos Aguilar Melchor
- Rafael Misoczki
- Edoardo Persichetti
- Nicolas Sendrier
- Jean-Pierre Tillich
- Valentin Vasseur
- Gilles Zémor
Classic McEliece
Abstract
The first code-based public-key cryptosystem was introduced in 1978 by McEliece. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding: extracting the codeword from the ciphertext, identifying and removing the errors.
The McEliece system was designed to be one-way (OW-CPA), meaning that an attacker cannot efficiently find the codeword from a ciphertext and public key, when the codeword is chosen randomly. The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 40 years. The original McEliece parameters were designed for only 264 security, but the system easily scales up to "overkill" parameters that provide ample security margin against advances in computer technology, including quantum computers.
The McEliece system has prompted a tremendous amount of followup work. Some of this work improves efficiency while clearly preserving security: this includes a "dual" PKE proposed by Niederreiter, software speedups, and hardware speedups.
Furthermore, it is now well known how to efficiently convert an OW-CPA PKE into a KEM that is IND-CCA2 secure against all ROM attacks. This conversion is tight, preserving the security level, under two assumptions that are satisfied by the McEliece PKE: first, the PKE is deterministic (i.e., decryption recovers all randomness that was used); second, the PKE has no decryption failures for valid ciphertexts. Even better, very recent work suggests the possibility of achieving similar tightness for the broader class of QROM attacks. The risk that a hash-function-specific attack could be faster than a ROM or QROM attack is addressed by the standard practice of selecting a well-studied, high-security, "unstructured" hash function.
Classic McEliece brings all of this together. It is a KEM designed for IND-CCA2 security at a very high security level, even against quantum computers. The KEM is built conservatively from a PKE designed for OW-CPA security, namely Niederreiter's dual version of McEliece's PKE using binary Goppa codes. Every level of the construction is designed so that future cryptographic auditors can be confident in the long-term security of post-quantum public-key encryption.
Participants
- Daniel J. Bernstein (CASA)
- Tanja Lange (CASA)
- Tung Chou
- Ingo von Maurich
- Rafael Misoczki
- Ruben Niederhagen
- Edoardo Persichetti
- Christiane Peters
- Peter Schwabe
- Nicolas Sendrier
- Jakub Szefer
- Wen Wang
Crystals Dilithium
Abstract
Dilithium is a digital signature scheme that is strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices. The security notion means that an adversary having access to a signing oracle cannot produce a signature of a message whose signature he hasn't yet seen, nor produce a different signature of a message that he already saw signed.
Participants
- Eike Kiltz (CASA)
- Peter Schwabe (MPI-SP)
- Roberto Avanzi
- Joppe Bos
- Léo Ducas
- Tancrède Lepoint
- Vadim Lyubashevsky
- John M. Schanck
- Gregor Seiler
- Damien Stehle
Crystals Kyber
Abstract
Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. The submission lists three different parameter sets aiming at different security levels. Specifically, Kyber-512 aims at security roughly equivalent to AES-128, Kyber-768 aims at security roughly equivalent to AES-192, and Kyber-1024 aims at security roughly equivalent to AES-256.
Participants
- Eike Kiltz (CASA)
- Peter Schwabe (MPI-SP)
- Roberto Avanzi
- Joppe Bos
- Léo Ducas
- Tancrède Lepoint
- Vadim Lyubashevsky
- John M. Schanck
- Gregor Seiler
- Damien Stehle
NTRU Prime
Abstract
Several ideal-lattice-based cryptosystems have been broken by recent attacks that exploit special structures of the rings used in those cryptosystems. The same structures are also used in the leading proposals for post-quantum lattice-based cryptography, including the classic NTRU cryptosystem and typical Ring-LWE-based cryptosystems.
NTRU Prime tweaks NTRU to use rings without these structures. Here are two public-key cryptosystems in the NTRU Prime family, both designed for the standard goal of IND-CCA2 security:
• Streamlined NTRU Prime is optimized from an implementation perspective.
• NTRU LPRime (pronounced "ell-prime") is a variant offering different tradeoffs.
Participants
- Daniel J. Bernstein (CASA)
- Tanja Lange (CASA)
- Chitchanok Chuengsatiansup
- Christine van Vredendaal
SPHINCS+
Abstract
SPHINCS+ is a stateless hash-based signature scheme. The design advances the SPHINCS signature scheme, which was presented at EUROCRYPT 2015. It incorporates multiple improvements, specifically aimed at reducing signature size. For a quick overview of the changes from SPHINCS to SPHINCS+ see the blog post by Andreas Hülsing. The submission proposes three different signature schemes:
• SPHINCS+-SHAKE256
• SPHINCS+-SHA-256
• SPHINCS+-Haraka
These signature schemes are obtained by instantiating the SPHINCS+ construction with SHAKE256, SHA-256, and Haraka, respectively.
The second round submission of SPHINCS+ introduces a split of the above three signature schemes into a simple and a robust variant for each choice of hash function. The robust variant is exactly the SPHINCS+ version from the first round submission and comes with all the conservative security guarantees given before. The simple variants are pure random oracle instantiations. These instantiations achieve about a factor three speed-up compared to the robust counterparts. This comes at the cost of a purely heuristic security argument.
Participants
- Daniel J. Bernstein (CASA)
- Tanja Lange (CASA)
- Peter Schwabe (MPI-SP)
- Jean-Philippe Aumasson
- Christoph Dobraunig
- Maria Eichlseder
- Scott Fluhrer
- Stefan-Lukas Gazdag
- Andreas Hülsing
- Panos Kampanakis
- Stefan Kölbl
- Martin M. Lauridsen
- Florian Mendel
- Ruben Niederhagen
- Christian Rechberger
- Joost Rijneveld
Rainbow
Abstract
Rainbow is a multivariate signature scheme. It is constructed, based on the Unbalanced Oil-Vinegar (UOV) signature scheme, with layered UOV structures. Though there is no formal security proof connecting Rainbow to a hard mathematical problem such as MQ, the last attack requiring a major parameter change was the band separation attack found in 2008 since Rainbow was proposed in 2005. Rainbow is known for its small signatures and fast signing/verification process, although the main disadvantage is its large public and private keys.
Participants
- Ming-Shing Chen (CASA)
- Jintai Ding
- Albrecht Petzoldt
- Dieter Schmidt
- Bo-Yin Yang
General note: In case of using gender-assigning attributes we include all those who consider themselves in this gender regardless of their own biological sex.
