Am Mittwoch, den 22. Juli 2020, wurden die Finalist*innen des Post-Quanten-Kryptographie-Standardisierungsprozesses des National Institute of Standards and Technology (NIST) bekannt gegeben. Unter ihnen sind zahlreiche Mitglieder des Exzellenzclusters "CASA - Cybersicherheit im Zeitalter groß-skaliger Angreifer". Vier von sieben Vorschlägen zu den Algorithmen "Public-key Encryption and Key-establishment" (Classic McEliece, CRYSTALS-KYBER) und "Digital Signature" (CRYSTALS-DILITHIUM, Rainbow) wurden unter Beteiligung der PIs Daniel Bernstein (ehemaliger CASA PI), Tim Güneysu, Eike Kiltz und Tanja Lange sowie des Postdocs Ming-Shing Chen eingereicht. "Quantenresistente Kryptographie" stellt ein Kernthema (Forschungsherausforderung) innerhalb des Exzellenzclusters dar.
CASA-Mitglieder sind auch an den Vorschlägen beteiligt, die es als Ersatzkandidat*innen in die Runde geschafft haben: BIKE, NTRU Prime, SPHINCS+. Ein weiterer Partizipierender des Finalisten NTRU ist Peter Schwabe, der am Max-Planck-Institut für Cybersicherheit und Datenschutz in Bochum arbeiten wird, das eng mit der CASA verbunden ist. Die Abstracts und partizipierenden Personen der Vorschläge finden sich am Ende des Artikels.
Auswahlrunde bildet Kern des ersten Post-Quantum-Kryptographie-Standards
Laut NIST wird diese "Auswahlrunde" bei der Entscheidung über die kleine Teilmenge dieser Algorithmen helfen, die den Kern des ersten Post-Quantum-Kryptographie-Standards bilden wird. "Das wahrscheinliche Ergebnis ist, dass wir am Ende dieser dritten Runde ein oder zwei Algorithmen für Verschlüsselung und Schlüsseleinrichtung und ein oder zwei andere für digitale Signaturen standardisieren werden", so der NIST-Mathematiker Dustin Moody in einer NIST-Pressemitteilung. "Aber wenn wir fertig sind, wird der Überprüfungsprozess bereits fünf oder sechs Jahre andauern, und jemand könnte in der Zwischenzeit eine gute Idee gehabt haben. Wir werden also einen Weg finden, auch neuere Ansätze zu betrachten".
Die NIST-Standardisierung ist von besonderem Interesse, weil die derzeitigen Verschlüsselungsmethoden dem Einsatz von Quantencomputern nicht mehr standhalten würden. Seit den Nachrichten über die Quantenüberlegenheit von Google ist klar, dass diese neue Technologie keine Zukunftsvision mehr ist. Da Quantencomputer anders funktionieren würden als herkömmliche Computer, wären die derzeitigen Public-Key-Verschlüsselungs- und Signatursysteme theoretisch obsolet. Die digitale Kommunikation wäre weniger gut geschützt.
Nachhaltige Sicherheit als Ziel
Der NIST-Standardisierungsprozess für die Post-Quanten-Kryptographie begann 2017 mit 69 Kandidaten-Algorithmen, und die Finalist*innen wurden in der zweiten Runde am 22. Juli 2020 aus den 26 Kandidaten ausgewählt. Die neuen Public-Key-Kryptographiestandards sollen eine oder mehrere digitale Signaturen, Public-Key-Verschlüsselung und schlüsselaktivierende Algorithmen zur Ergänzung bestehender Standards spezifizieren. Ziel ist es, die Verschlüsselung nachhaltig zu sichern.
Übersicht zu den Abstracts
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, former CASA PI)
- 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, former CASA PI)
- 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, former CASA PI)
- 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
Allgemeiner Hinweis: Mit einer möglichen Nennung von geschlechtszuweisenden Attributen implizieren wir alle, die sich diesem Geschlecht zugehörig fühlen, unabhängig vom biologischen Geschlecht.
