Kyber
Kyber is a key encapsulation method (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 presumably NP-hard lattice problem of learning with errors as its basic trapdoor function. It is considered the most promising candidate for a first post-quantum cryptography standard. Kyber is named after the fictional kyber crystals used to power lightsabers in the Star Wars universe (compare [Light-]SABER).

Properties 
The system is based on module learning with errors (M-LWE) from the field of machine learning, in conjunction with cyclotomic rings. Since recently, there is also a tight formal mathematical security reduction of the ring-LWE problem to MLWE. 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. 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). At a complexity of 161 bits, the secret keys are 2400, the public keys 1184, and the ciphertexts 1088 bytes in size. With an accordingly optimized implementation, 4 kilobytes of memory can be sufficient for the cryptographic operations. 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. 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. 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. 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 one of the most promising finalists for the standard that is expected in early 2022. As one of four asymmetric encryption algorithms, it competes with at least two other methods. The McEliece method is based on a different principle and could be standardized additionally. In the second phase of the selection process, several parameters of the algorithm were adjusted and the compression of the public keys was dropped. While the computational complexity of the algorithm is outstandingly low by comparison, NIST could choose NTRU as a more conservative option, should security issues or patent claims arise for Kyber. The French National Centre for Scientific Research's claimed applicability of its Gaborit and Aguilar-Melchor patent is disputed. 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).

Usage 
The developers have released a reference implementation into the public domain (or under CC0), which is written in C. The program library liboqs of the Open Quantum Safe (OQS) project contains an implementation based on that. OQS also maintains a quantum-safe development branch of OpenSSL, has integrated it into BoringSSL, and its code has also been integrated into WolfSSL. There are a handful of implementations using various other programming languages from third-party developers, including JavaScript and Java. Various (free) optimized hardware implementations exist, including one that is resistant to side-channel attacks. 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.

References

External links 
 
 
 original method by 

Asymmetric-key algorithms