Kyber

Last updated

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 standard Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). [2]

Contents

Properties

The system is based on the module learning with errors (M-LWE) problem, in conjunction with cyclotomic rings. [3] Recently, there has also been a tight formal mathematical security reduction of the ring-LWE problem to MLWE. [4] [5] 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. [6]

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). [7] At the Kyber768 level, the secret keys are 2400 bytes in size, the public keys 1184, and the ciphertexts 1088. [8] [9]

With an accordingly optimized implementation, 4 kilobytes of memory can be sufficient for the cryptographic operations. [10] 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. [11] Internal hashing operations account for the majority of the runtime, which would thus potentially benefit greatly from corresponding hardware acceleration.

Development

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. [12] 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. [10] 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. [4] 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. [10] 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). [4]

Evolution

Kyber underwent changes during the NIST standardization process. In particular, in the submission for round 2 (so called Kyber v2), the following features were changed: [13]

Submission to round 3 underwent further tweaks: [14]

Usage

The developers have released a reference implementation into the public domain (or under CC0), which is written in C. [15] The program library liboqs of the Open Quantum Safe (OQS) project contains an implementation based [16] on that. [11] OQS also maintains a quantum-safe Provider module for OpenSSL 3.x, [17] and has integrated its code into BoringSSL and wolfSSL. [18] There are a handful of implementations using various other programming languages from third-party developers, including JavaScript and Java. [19] [20] [21] Various (free) optimized hardware implementations exist, including one that is resistant to side-channel attacks. [22] [23] 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. [24] In 2023, the encrypted messaging service Signal implemented PQXDH, a Kyber-based post-quantum encryption algorithm, to their Signal Protocol. [25] [26]

Implementations

Related Research Articles

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.

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 outsourced 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 currently thought to be secure against a cryptanalytic attack by a quantum computer. Most widely-used public-key algorithms rely on the difficulty of one of three 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.

wolfSSL is a small, portable, embedded SSL/TLS library targeted for use by embedded systems developers. It is an open source implementation of TLS written in the C programming language. It includes SSL/TLS client libraries and an SSL/TLS server implementation as well as support for multiple APIs, including those defined by SSL and TLS. wolfSSL also includes an OpenSSL compatibility interface with the most commonly used OpenSSL functions.

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.

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.

<span class="mw-page-title-main">Commercial National Security Algorithm Suite</span> Set of cryptographic algorithms by the NSA

The Commercial National Security Algorithm Suite (CNSA) is a set of cryptographic algorithms promulgated by the National Security Agency as a replacement for NSA Suite B Cryptography algorithms. It serves as the cryptographic base to protect US National Security Systems information up to the top secret level, while the NSA plans for a transition to quantum-resistant cryptography.

Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. It was 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.

References

  1. ↑ Moody, Dustin (2022), Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process (PDF), Gaithersburg, MD, pp. NIST IR 8413, doi:10.6028/nist.ir.8413, S2CID   247903639 {{citation}}: CS1 maint: location missing publisher (link)
  2. ↑ Technology, National Institute of Standards and (13 August 2024). "Module-Lattice-Based Key-Encapsulation Mechanism Standard [FIPS 203]". U.S. Department of Commerce.
  3. ↑ What was NIST thinking? (PDF-Datei)
  4. 1 2 3 Status Report on the Second Round of the NIST PQC Standardization Process (PDF-Datei)
  5. ↑ Chris Peikert, Zachary Pepin (2019), "Algebraically Structured LWE, Revisited" (PDF), Theory of Cryptography, Lecture Notes in Computer Science (in German), vol. 11891, Cham: Springer International Publishing, pp. 1–23, doi:10.1007/978-3-030-36030-6_1, ISBN   978-3-030-36029-0, S2CID   199455447
  6. ↑ Lattice-based cryptography and SABER – Andrea Basso (PDF; 2,0 MB)
  7. ↑ Overview of NIST Round 3 Post-Quantum cryptography Candidates (PDF; 157 kB)
  8. ↑ Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé (2018), "CRYSTALS – Kyber: A CCA-Secure Module-Lattice-Based KEM", 2018 IEEE European Symposium on Security and Privacy, EuroS&P 2018., IEEE, pp. 353–367, doi:10.1109/EuroSP.2018.00032, hdl: 2066/195423 , ISBN   978-1-5386-4228-3, S2CID   20449721 {{citation}}: CS1 maint: multiple names: authors list (link)
  9. ↑ https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf [ bare URL PDF ]
  10. 1 2 3 Leon Botros, Matthias J. Kannwischer, Peter Schwabe (2019), "Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4" (PDF), Progress in Cryptology – AFRICACRYPT 2019, Lecture Notes in Computer Science (in German), vol. 11627, Cham: Springer International Publishing, pp. 209–228, doi:10.1007/978-3-030-23696-0_11, ISBN   978-3-030-23696-0, S2CID   174775508 {{citation}}: CS1 maint: multiple names: authors list (link)
  11. 1 2 Ines Duits (2019-02-05), University of Twente (ed.), The Post-Quantum Signal Protocol: Secure Chat in a Quantum World (PDF) (in German)
  12. ↑ [ bare URL ]
  13. ↑ Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. CRYSTALS–Kyber (Round 2 presentation) August 23, 2019.
  14. ↑ Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. CRYSTALS–Kyber (Round 3 presentation) June 9, 2021.
  15. ↑ Kyber/LICENSE at master · pq-crystals/kyber · GitHub
  16. ↑ "Kyber – Open Quantum Safe". Archived from the original on 2021-04-20. Retrieved 2022-01-13.
  17. ↑ "OQS Provider for OpenSSL 3.x". oqs-provider.
  18. ↑ "wolfSSL and libOQS Integration". WolfSSL-Website. 2021-09-01.
  19. ↑ "CRYSTALS KYBER Java". GitHub . 25 October 2021.
  20. ↑ "CRYSTALS-KYBER JavaScript". GitHub . 11 December 2021.
  21. ↑ "Yawning/Kyber". Archived from the original on 2021-07-28. Retrieved 2022-01-13.
  22. ↑ B. Dang, Kamyar Mohajerani, K. Gaj (2021), High-Speed Hardware Architectures and Fair FPGA Benchmarking (PDF) (in German){{citation}}: CS1 maint: multiple names: authors list (link)
  23. ↑ Arpan Jati, Naina Gupta, A. Chattopadhyay, S. Sanadhya (2021), "A Configurable Crystals-Kyber Hardware Implementation with Side-Channel Protection" (PDF), IACR Cryptol. ePrint Arch. (in German){{citation}}: CS1 maint: multiple names: authors list (link)
  24. ↑ "E-Vergabe, die Vergabeplattform des Bundes".
  25. ↑ "Add Kyber KEM and implement PQXDH protocol". GitHub .
  26. ↑ "Signal Messenger Introduces PQXDH Quantum-Resistant Encryption". The Hacker News. Retrieved 2023-09-22.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.