Post-quantum cryptography
A large-scale, fault-tolerant quantum computer will be able to break most public-key cryptography currently in use, including cryptosystems based on factoring, such as RSA, and (elliptic curve) discrete logarithms. In order to prepare for such a catastrophic event, the National Institute of Standards and Technology (NIST) has launched a multi-year project
with the goal of selecting and standardizing the next generation of quantum-safe crypto algorithms. We have been working in close collaboration with several partners in industry and academia in the design and implementation of a few promising post-quantum primitives. These primitives, which were submitted to the NIST's Post-Quantum Cryptography Standardization project, include:
Supersingular isogeny key encapsulation (SIKE), a KEM based on supersingular isogenies.
FrodoKEM, a KEM based on unstructured, standard lattices (LWE problem).
qTESLA, an efficient and compact digital signature scheme based on ideal lattices (R-LWE problem).
Supersingular isogeny Diffie-Hellman (SIDH) key exchange
In 2011, Jao and De Feo
proposed the so-called Supersingular Isogeny Diffie-Hellman key exchange (SIDH) protocol which is based on the difficulty of computing isogenies between supersingular elliptic curves. Since then, this relatively young cryptographic primitive has gained great popularity. One of the most attractive features of SIDH is that it exhibits the smallest public keys among all the well-established post-quantum candidates for key exchange.
In 2016, we published a paper (Costello–Longa–Naehrig) presenting several algorithmic improvements for SIDH, including an efficient parametrization called SIDHp751, and released an efficient constant-time implementation which later became part of the SIDH Library. The improvements made possible to reduce the cost of SIDH from hundreds of milliseconds (running in variable time) to less than 60 milliseconds (running in constant-time) on a desktop-class processor (a 3.4GHz Intel Core i7 Haswell processor).
Later, in 2017 we published a paper (Costello–Jao–Longa–Naehrig–Renes–Urbanik) presenting a compression technique that reduces SIDH public keys even further (e.g., with the technique it is possible to reduce SIDHp751 public keys from 564 bytes to only 330 bytes). More recently, we have been able to improve the performance of SIDH even further, using smaller field sizes and faster algorithms, on x64 Intel processors (about 9 milliseconds to run SIDHp503 on a 3.4GHz Intel Core i7 Skylake processor, see my talk at TUDarmstadt), and on 32-bit and 64-bit ARM processors (see our paper
Seo–Liu–Longa–Hu). Despite these promising results, SIDH in its current form presents a drawback: Galbraith–Petit–Shani–Ti discovered an active attack that allows to recover the secret key when used in static mode. The consequence of this attack is that SIDH keys cannot be reused
and should be immediately discarded after use. To solve this problem, we proposed SIKE.
Supersingular isogeny key encapsulation (SIKE) protocol
SIKE is an isogeny-based key encapsulation suite whose hardness is based on pseudo-random walks in supersingular isogeny graphs. It consists of two algorithms:
A CPA-secure public key encryption algorithm SIKE.PKE, and
A CCA-secure key encapsulation mechanism SIKE.KEM,
each instantiated with three parameter sets: SIKEp503, SIKEp751 and SIKEp964.
SIKE has been submitted to the NIST's Post-Quantum Cryptography Standardization project.
qTESLA: an efficient and compact signature scheme based on ideal lattices
qTESLA is a family of post-quantum signature schemes based on the hardness of the decisional Ring-Learning With Errors (R-LWE) problem. The scheme is an efficient variant of the Bai-Galbraith signature scheme —which in turn is based on the “Fiat-Shamir with Aborts” framework by Lyubashevsky— adapted to the setting of ideal lattices.
qTESLA utilizes two different approaches for parameter generation in order to target a wide range of application scenarios. The first approach, referred to as “heuristic qTESLA” follows a heuristic parameter generation and enables high-speed, compactimplementations with relatively small key and signature sizes. The second approach, referred to as “provably-secure qTESLA”, is a more conservative approach that follows a provably-secure parameter generation according to existing security reductions.
FrodoKEM: a KEM based on standard lattices
FrodoKEM is a family of key-encapsulation mechanisms that are designed to be conservative yet practical post-quantum constructions whose security derives from cautious parametrizations of the well-studied learning with errors (LWE) problem.
Concretely, FrodoKEM includes the following KEM schemes using AES128 for the generation of the public matrix "A":
And the following KEM schemes using cSHAKE128 for the generation of the public matrix "A":
FourQ: a high-speed high-security elliptic curve
FourQ, introduced in Costello–Longa, is a high-security, high-performance elliptic curve that targets the 128-bit security level. At the highest arithmetic level, cryptographic scalar multiplications on FourQ can use a four-dimensional Gallant-Lambert-Vanstone decomposition to minimize the total number of elliptic curve group operations. At the group arithmetic level, FourQ admits the use of extended twisted Edwards coordinates and can therefore exploit the fastest known elliptic curve addition formulas over large prime characteristic fields. Finally, at the finite field level, arithmetic is performed modulo the extremely fast Mersenne prime 2^127 - 1. This powerful combination facilitates scalar multiplications that are significantly faster than other curve-based alternatives. For example, on Intel's Haswell architecture, a variable-base scalar multiplication using FourQ is computed in 56,000 cycles; and, on the same platform, a Diffie-Hellman shared secret is computed in 88,000 cycles. These results show that FourQ is around four to five times faster than the NIST P-256 curve and between two and three times faster than Curve25519.
We also proposed a high-speed signature scheme based on FourQ, called SchnorrQ (see Costello–Longa), and developed efficient and secure implementations of FourQ and SchnorrQ for ARM using NEON (Longa), and for the popular microcontrollers 32-bit ARM Cortex-M4, 16-bit MSP430X and 8-bit Atmel AVR (Liu–Longa–Pereira–Reparaz–Seo) including strong side-channel countermeasures. A fast yet area-efficient hardware implementation on FPGA was also realized by Järvinen–Miele–Azarderakhsh–Longa. I wrote a software library, called FourQlib, that contains our various implementations of FourQ for multiple 32-bit and 64-bit platforms including x64, 32-bit ARM with NEON, and ARM Cortex-M4. At the crypto protocol level FourQlib includes support for key exchange and digital signatures.