NIST proposals

Members of the RISQ project have contributed to NIST’s call for post-quantum schemes by proposing no less than 9 cryptographic schemes, about one seventh of the 69 schemes accepted for the first round of the selection process. We have proposed signature schemes as well as encryption schemes and key encapsulation mechanisms (KEMs), and have based our schemes on several technologies: lattices, error-correcting codes, multivariate equations and supersingular isogenies.

CFKPM

CPFKM is a KEM based on the problem of solving a system of noisy non-linear polynomials, also known as the PoSSo with Noise Problem.

CRYSTALS-Dilithium

CRYSTALS-Dilithium is a digital signature with security inherited from the hardness of the module-LWE and module-SIS problems. These problems offer both lattice security and parameter flexibility. Apart from the classical efficiency/security trade-off, the main design criterion was simplicity. The scheme is balanced, offering good overall performance (sizes of keys and signatures, costs of signing and verifying). More information can be found on ePrint or the dedicated website, and the implementation is available on GitHub.

CRYSTALS-Kyber

CRYSTALS-Kyber is an encryption scheme with security inherited from the hardness of the module-LWE problem. Module-LWE provides both lattice security and parameter flexibility. Apart from the classical efficiency/security trade-off, the main design criterion was simplicity. The scheme is balanced, offering good overall performance (sizes of keys and ciphertexts, costs of encrypting and decrypting). More information can be found on ePrint or the dedicated website, and the implementation is available on GitHub.

DualModeMS

DualModeMS is a multivariate-based signature scheme with a rather peculiar property. Its public-key is small whilst the signature is large. This is in sharp contrast with traditionnal multivariate signature schemes based on the so-called Matsumoto and Imai (MI) constructions that produce short signatures but have larger public-keys.

DualModeMS is composed by two distinct layers. The first one is a classical MI-like multivariate scheme based on HFEv. The second part is based on the method proposed by A. Szepieniec, W. Beullens, and B. Preneel in“ MQ signatures for PKI” where present a generic technique permitting to transform any MI-based multivariate signature scheme into a new scheme with much shorter public-key but larger signatures.

We emphasize that this technique can be viewed as a mode of operations that offers a new flexibility for MI-like signature schemes. Thus, we believe that DualModeMS could also be useful for others multivariate-based signature candidates proposed to NIST.

Falcon

Falcon stands for Fast Fourier, lattice-based compact signatures over NTRU. As its name implies, it is a lattice-based signature scheme. Compactness was the leading principle in the design of Falcon, which led us to use the space-efficient class of NTRU lattices and develop a new and compact signing procedure. As a result, we get small public key and signature sizes.

A noteworthy feature of Falcon is that it can be easily converted in an identity-based encryption scheme. In addition, an optional “key recovery” mode allows to compress the public key down to 40 bytes, and an optional “message recovery” mode allows to recover a short message from its signature. More information can be found on the dedicated website.

GeMSS

GeMSS stands for Great Multivariate Signature Scheme. GeMSS is a multivariate based signature scheme producing small signatures. It has a fast verification process, and a medium/large public-key. GeMSS is in direct lineage from the multivariate signature scheme QUARTZ. Thus, GeMSS is built from the Hidden Field Equations crypotsystem (HFE) by using the so-called minus and vinegar modifiers, i.e. HFEv-. GeMSS is a faster variant of QUARTZ that incorporates the latest results in multivariate cryptography to reach higher security levels than QUARTZ whilst improving efficiency.

LAKE

LAKE stands for Low rAnk parity check codes Key Exchange. It can be viewed as a rank metric analogue of NTRU. It is based on LRPC codes that are the rank metric analogues of LDPC/MDPC codes and which enjoy a very efficient decoding algorithm. In this proposal we build on a small variation of the LRPC rank metric approach, by introducing Ideal-LRPC codes, and propose an IND-CPA KEM for Key Exchange, efficient in terms of size of parameters and computational complexity which benefits from the nice properties of the rank metric. The scheme has a failure probability but this probability is well understood and can be made arbitrarily low.

LOCKER

LOCKER stands for LOw rank parity ChecK codes EncRyption. It is a rank metric code based public key encryption scheme. It is very similar to the LAKE Key Exchange protocol but its parameters have been adapted in order to give very low decryption probability failures.

SIKE

SIKE stands for Supersingular Isogeny Key Encapsulation. It exists in two variants: a CPA-secure public key encryption system, and a CCA-secure key encapsulation method. The KEM variant is derived from the PKE one by applying a generic transformation. Roughly speaking, their security is based on the difficulty of finding a path between two supersingular elliptic curves in an isogeny graph.

SIKE is the only isogeny-based protocol submitted to the NIST competition, somewhat unsurprisingly given the novelty of the mathematical construction. The only known attacks against SIKE have exponential complexity, both on classical and quantum computers; this allows us to construct instances with very compact public keys for all security levels. In fact, SIKE is the cryptosystem with the smallest public keys among all KEMs submitted to the NIST competition in categories 1, 3 and 5.