Kyber is a key encapsulation mechanism (KEM) designed to be resistant to cryptanalytic attacks with future powerful quantum computers. It is used to establish a shared secret between two communicating parties without an (IND-CCA2) attacker in the transmission system being able to decrypt it. This asymmetric cryptosystem uses a variant of the learning with errors lattice problem as its basic trapdoor function. It won the NIST competition for the first post-quantum cryptography (PQ) standard. [1] NIST calls its draft standard Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). [2] However, at least for Kyber512, there are claims that NIST's security calculations were amiss. [3]
The system is based on the module learning with errors (M-LWE) problem, in conjunction with cyclotomic rings. [4] Recently, there has also been a tight formal mathematical security reduction of the ring-LWE problem to MLWE. [5] [6] Compared to competing PQ methods, it has typical advantages of lattice-based methods, e.g. in regard to runtime as well as the size of the ciphertexts and the key material. [7]
Variants with different security levels have been defined: Kyber512 (NIST security level 1, ≈AES 128), Kyber768 (NIST security level 3, ≈AES 192), and Kyber1024 (NIST security level 5, ≈AES 256). [8] At the Kyber768 level, the secret keys are 2400 bytes in size, the public keys 1184, and the ciphertexts 1088. [9] [10] At least for Kyber512, however, there are claims that NIST's security calculations were amiss. [3]
With an accordingly optimized implementation, 4 kilobytes of memory can be sufficient for the cryptographic operations. [11] For a chat encryption scenario using liboqs, replacing the extremely efficient, non-quantum-safe ECDH key exchange using Curve25519 was found to increase runtime by a factor of about 2.3 (1.5–7), an estimated 2.3-fold (1.4–3.1) increase in energy consumption, and have about 70 times (48–92) more data overhead. [12] Internal hashing operations account for the majority of the runtime, which would thus potentially benefit greatly from corresponding hardware acceleration.
Kyber is derived from a method published in 2005 by Oded Regev, developed by developers from Europe and North America, who are employed by various government universities or research institutions, or by private companies, with funding from the European Commission, Switzerland, the Netherlands, and Germany. [13] They also developed the related and complementary signature scheme Dilithium, as another component of their "Cryptographic Suite for Algebraic Lattices" (CRYSTALS). Like other PQC-KEM methods, Kyber makes extensive use of hashing internally. In Kyber's case, variants of Keccak (SHA-3/SHAKE) are used here, to generate pseudorandom numbers, among other things. [11] In 2017 the method was submitted to the US National Institute of Standards and Technology (NIST) for its public selection process for a first standard for quantum-safe cryptographic primitives (NISTPQC). It is the only key encapsulation mechanism that has been selected for standardization at the end of the third round of the NIST standardization process. [5] According to a footnote the report announcing the decision, it is conditional on the execution of various patent-related agreements, with NTRU being a fallback option. Currently, a fourth round of the standardization process is underway, with the goal of standardizing an additional KEM. In the second phase of the selection process, several parameters of the algorithm were adjusted and the compression of the public keys was dropped. [11] Most recently, NIST paid particular attention to costs in terms of runtime and complexity for implementations that mask runtimes in order to prevent corresponding side-channel attacks (SCA). [5]
During the NIST standardization process, Kyber has undergone changes. In particular, in the submission for round 2 (so called Kyber v2), the following features have been changed: [14]
Submission to round 3 underwent further tweaks: [15]
The developers have released a reference implementation into the public domain (or under CC0), which is written in C. [16] The program library liboqs of the Open Quantum Safe (OQS) project contains an implementation based [17] on that. [12] OQS also maintains a quantum-safe development branch of OpenSSL, [18] has integrated it into BoringSSL, and its code has also been integrated into WolfSSL. [19] There are a handful of implementations using various other programming languages from third-party developers, including JavaScript and Java. [20] [21] [22] Various (free) optimized hardware implementations exist, including one that is resistant to side-channel attacks. [23] [24] The German Federal Office for Information Security is aiming for implementation in Thunderbird, and in this context also an implementation in the Botan program library and corresponding adjustments to the OpenPGP standard. [25] In 2023, the encrypted messaging service Signal implemented PQXDH, a Kyber-based post-quantum encryption algorithm, to their Signal Protocol which is used by WhatsApp and others. [26] [27]
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.
NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unlike other popular public-key cryptosystems, it is resistant to attacks using Shor's algorithm. NTRUEncrypt was patented, but it was placed in the public domain in 2017. NTRUSign is patented, but it can be used by software under the GPL.
Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.
NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), and was published at CrypTEC'99. The improved version of PASS was named as NTRUSign, and was presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. The 2003 publication included parameter recommendations for 80-bit security. A subsequent 2005 publication revised the parameter recommendations for 80-bit security, presented parameters that gave claimed security levels of 112, 128, 160, 192 and 256 bits, and described an algorithm to derive parameter sets at any desired security level. NTRU Cryptosystems, Inc. have applied for a patent on the algorithm.
Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted.
In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest curves in ECC, and is not covered by any known patents. The reference implementation is public domain software.
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.
The following outline is provided as an overview of and topical guide to cryptography:
In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear -ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with popular algorithms currently used in the market is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves. It is designed to be faster than existing digital signature schemes without sacrificing security. It was developed by a team including Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. The reference implementation is public-domain software.
Digital signatures are a means to protect digital information from intentional modification and to authenticate the source of digital information. Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures. However, the primary public key signatures currently in use will become completely insecure if scientists are ever able to build a moderately sized quantum computer. Post quantum cryptography is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used RSA and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as Ring learning with errors. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes
In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption. Public-key cryptography relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought. Homomorphic encryption is a form of encryption that allows computation on ciphertext, such as arithmetic on numeric values stored in an encrypted database.
In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.
BLISS is a digital signature scheme proposed by Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky in their 2013 paper "Lattice Signature and Bimodal Gaussians".
Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.
Post-Quantum Cryptography Standardization is a program and competition by NIST to update their standards to include post-quantum cryptography. It was announced at PQCrypto 2016. 23 signature schemes and 59 encryption/KEM schemes were submitted by the initial submission deadline at the end of 2017 of which 69 total were deemed complete and proper and participated in the first round. Seven of these, of which 3 are signature schemes, have advanced to the third round, which was announced on July 22, 2020.
In cryptography, Combined Elliptic-Curve and Post-Quantum 2 (CECPQ2) is a quantum secure modification to Transport Layer Security (TLS) 1.3 developed by Google. It is intended to be used experimentally, to help evaluate the performance of post quantum key-exchange algorithms on actual users' devices.
In post-quantum cryptography, NewHope is a key-agreement protocol by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist quantum computer attacks.
Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. It has been designed by Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte and Zhenfei Zhang. It relies on the hash-and-sign technique over the Gentry, Peikert and Vaikuntanathan framework over NTRU lattices. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU.
{{citation}}: CS1 maint: location missing publisher (link){{citation}}: CS1 maint: multiple names: authors list (link){{citation}}: CS1 maint: multiple names: authors list (link){{citation}}: CS1 maint: multiple names: authors list (link){{citation}}: CS1 maint: multiple names: authors list (link)