Kyber: Difference between revisions

From HandWiki
(add)
 
(url)
 
Line 1: Line 1:
{{Short description|Quantum-safe key encapsulation mechanism}}
'''Kyber''' is a [[Social:Key encapsulation mechanism|key encapsulation mechanism]] (KEM) designed to be resistant to [[Cryptanalysis|cryptanalytic]] attacks with future powerful [[Quantum computing|quantum computers]]. It is used to establish a [[Social:Shared secret|shared secret]] between two communicating parties without an (IND-CCA2) attacker in the transmission system being able to decrypt it. This [[Public-key cryptography|asymmetric cryptosystem]] uses a variant of the [[Learning with errors|learning with errors]] [[Lattice problem|lattice problem]] as its basic [[Trapdoor function|trapdoor function]]. It won the [[NIST Post-Quantum Cryptography Standardization|NIST competition]] for the first [[Post-quantum cryptography|post-quantum cryptography]] (PQ) standard.<ref>{{citation |last=Moody |first=Dustin |date=2022 |title=Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process |url=https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf |location=Gaithersburg, MD |pages=NIST IR 8413 |doi=10.6028/nist.ir.8413|s2cid=247903639 }}</ref> NIST calls its standard, numbered '''FIPS 203''', '''Module-Lattice-Based Key-Encapsulation Mechanism''' ('''ML-KEM''').<ref>{{cite web |last1=Technology |first1=National Institute of Standards and |title=Module-Lattice-Based Key-Encapsulation Mechanism Standard [FIPS 203]|url=https://csrc.nist.gov/pubs/fips/203/final |publisher=U.S. Department of Commerce |language=en |date=13 August 2024}}</ref>
{{For multi|the fictional crystals|Lightsaber|the computing I/O scheduler|I/O scheduling|other uses|Khyber (disambiguation)}}


'''Kyber''' is a [[Social:Key encapsulation mechanism|key encapsulation mechanism]] (KEM) designed to be resistant to [[Cryptanalysis|cryptanalytic]] attacks with future powerful [[Quantum computing|quantum computers]]. It is used to establish a [[Social:Shared secret|shared secret]] between two communicating parties without an ([[Ciphertext indistinguishability|IND-CCA2]]) attacker in the transmission system being able to decrypt it. This [[Public-key cryptography|asymmetric cryptosystem]] uses a variant of the [[Learning with errors|learning with errors]] [[Lattice problem|lattice problem]] as its basic [[Trapdoor function|trapdoor function]]. It won the [[NIST Post-Quantum Cryptography Standardization|NIST competition]] for the first [[Post-quantum cryptography|post-quantum cryptography]] (PQ) standard.<ref>{{citation |last=Moody |first=Dustin |date=2022 |title=Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process |url=https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf |location=Gaithersburg, MD |pages=NIST IR 8413 |doi=10.6028/nist.ir.8413|s2cid=247903639 }}</ref>  
== Properties ==
The system is based on the module [[Learning with errors|learning with errors]] (M-LWE) problem, in conjunction with [[Cyclotomic field|cyclotomic]] [[Ring (mathematics)|rings]].<ref name="Moody2019"/> Recently, there has also been a tight formal mathematical security [[Reduction (mathematics)|reduction]] of the ring-LWE problem to MLWE.<ref name="NISTIR 8309"/><ref name="Peikert&Pepin"/> 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.<ref name="Basso2021"/>


== Properties ==
Variants with different security levels have been defined: Kyber512 (NIST security level 1, ≈[[Advanced Encryption Standard|AES]] 128), Kyber768 (NIST security level 3, ≈AES 192), and Kyber1024 (NIST security level 5, ≈AES 256).<ref name="PQSecure"/> At the Kyber768 level, the secret keys are 2400 bytes in size, the public keys 1184, and the ciphertexts 1088.<ref name="Bos et al."/><ref name="v3.02" />
The system is based on the module [[Learning with errors|learning with errors]] (M-LWE) problem, in conjunction with [[Cyclotomic field|cyclotomic]] [[Ring (mathematics)|rings]].<ref name="Moody2019"/> Recently, there has also been a tight formal mathematical security [[Reduction (mathematics)|reduction]] of the ring-LWE problem to MLWE.<ref name="NISTIR 8309"/><ref name="Peikert&Pepin"/> 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.<ref name="Basso2021"/> Variants with different security levels have been defined: Kyber512 (NIST security level 1, ≈[[Advanced Encryption Standard|AES]] 128), Kyber768 (NIST security level 3, ≈AES 192), and Kyber1024 (NIST security level 5, ≈AES 256).<ref name="PQSecure"/> At a complexity of 161 bits, the secret keys are 2400, the public keys 1184, and the ciphertexts 1088 bytes in size.<ref name="Bos et al."/><ref name="v3.02"/> With an accordingly optimized implementation, 4 kilobytes of memory can be sufficient for the cryptographic operations.<ref name="nttm4"/> For a [[Social:Online chat|chat]] encryption scenario using liboqs, replacing the extremely efficient, non-quantum-safe [[Elliptic-curve Diffie–Hellman|ECDH]] key exchange using [[Curve25519]] was found to increase [[Runtime (program lifecycle phase)|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 (computing)|overhead]].<ref name="Duits19"/> Internal hashing operations account for the majority of the runtime, which would thus potentially benefit greatly from corresponding [[Hardware acceleration|hardware acceleration]].
 
With an accordingly optimized implementation, 4 kilobytes of memory can be sufficient for the cryptographic operations.<ref name="nttm4"/> For a [[Social:Online chat|chat]] encryption scenario using liboqs, replacing the extremely efficient, non-quantum-safe [[Elliptic-curve Diffie–Hellman|ECDH]] key exchange using [[Curve25519]] was found to increase [[Runtime (program lifecycle phase)|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 (computing)|overhead]].<ref name="Duits19"/> Internal hashing operations account for the majority of the runtime, which would thus potentially benefit greatly from corresponding [[Hardware acceleration|hardware acceleration]].


== Development ==
== Development ==
Kyber is derived from a method published in 2005 by [[Biography:Oded Regev (computer scientist)|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.<ref name="ack">[https://pq-crystals.org/] {{Bare URL inline|date=August 2022}}</ref> 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 [[Cryptographic hash function|hashing]] internally. In Kyber's case, variants of Keccak ([[SHA-3]]/SHAKE) are used here, to [[Pseudorandom number generator|generate pseudorandom numbers]], among other things.<ref name="nttm4"/> In 2017 the method was submitted to the US [[Organization:National Institute of Standards and Technology|National Institute of Standards and Technology]] (NIST) for its public [[NIST Post-Quantum Cryptography Standardization|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.<ref name="NISTIR 8309"/> According to a footnote the report announcing the decision, it is conditional on the execution of various [[Social:Patent|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.<ref name="nttm4"/> 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 attack|side-channel attack]]s (SCA).<ref name="NISTIR 8309"/>
Kyber is derived from a method published in 2005 by [[Biography:Oded Regev (computer scientist)|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.<ref name="ack">{{Cite web|url=https://pq-crystals.org/|title=CRYSTALS|first=Peter|last=Schwabe|website=pq-crystals.org}}</ref> 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 [[Cryptographic hash function|hashing]] internally. In Kyber's case, variants of Keccak ([[SHA-3]]/SHAKE) are used here, to [[Pseudorandom number generator|generate pseudorandom numbers]], among other things.<ref name="nttm4"/> In 2017 the method was submitted to the US [[Organization:National Institute of Standards and Technology|National Institute of Standards and Technology]] (NIST) for its public [[NIST Post-Quantum Cryptography Standardization|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.<ref name="NISTIR 8309"/> According to a footnote the report announcing the decision, it is conditional on the execution of various [[Social:Patent|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.<ref name="nttm4"/> 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 attack|side-channel attack]]s (SCA).<ref name="NISTIR 8309"/>


=== Evolution ===
=== Evolution ===
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:<ref name=v2>Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. [https://csrc.nist.gov/CSRC/media/Presentations/crystals-kyber-round-2-presentation/images-media/crystals-kyber-schwabe.pdf CRYSTALS–Kyber]<small> (Round 2 presentation)</small> August 23, 2019.</ref>
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:<ref name=v2>Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. [https://csrc.nist.gov/CSRC/media/Presentations/crystals-kyber-round-2-presentation/images-media/crystals-kyber-schwabe.pdf CRYSTALS–Kyber] (Round 2 presentation) August 23, 2019.</ref>
* public key compression removed (due to NIST comments on the security proof);
* public key compression removed (due to NIST comments on the security proof);
* parameter q reduced to 3329 (from 7681);
* parameter ''q'' reduced to 3329 (from 7681);
* ciphertext compression parameters changed;
* ciphertext compression parameters changed;
* number-theoretic transform (NTT) definition changed along the lines of NTTRU for faster polynomial multiplication;
* number-theoretic transform (NTT) definition changed along the lines of NTTRU for faster polynomial multiplication;
* noise parameter reduced to {{nowrap|1=''η'' = 2}} for faster noise sampling;
* noise parameter reduced to {{nowrap|1=''η'' = 2}} for faster noise sampling;
* public key representation is changed to NTT domain in order to save the NTT operations.
* public key representation changed to NTT domain in order to save the NTT operations.
Submission to round 3 underwent further tweaks:<ref name=r3>Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. [https://csrc.nist.gov/CSRC/media/Presentations/crystals-kyber-round-3-presentation/images-media/session-7-crystals-kyber-schwabe.pdf CRYSTALS–Kyber]<small> (Round 3 presentation)</small> June 9, 2021.</ref>
Submission to round 3 underwent further tweaks:<ref name=r3>Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. [https://csrc.nist.gov/CSRC/media/Presentations/crystals-kyber-round-3-presentation/images-media/session-7-crystals-kyber-schwabe.pdf CRYSTALS–Kyber] (Round 3 presentation) June 9, 2021.</ref>
* the use of Fujisaki–Okamoto transformation (FO transform) modified;
* the use of Fujisaki–Okamoto transformation (FO transform) modified;
* noise level increased and ciphertext compression reduced for the level 1 parameter set;  
* noise level increased and ciphertext compression reduced for the level 1 parameter set;  
Line 24: Line 25:


== Usage ==
== Usage ==
The developers have released a [[Reference implementation|reference implementation]] into the [[Social:Public domain|public domain]] (or under CC0), which is written in [[C (programming language)|C]].<ref name="PD"/> The [[Library (computing)|program library]] ''liboqs'' of the Open Quantum Safe (OQS) project contains an implementation based<ref>{{cite web |url=https://openquantumsafe.org/liboqs/algorithms/kem/Kyber |title=Kyber – Open Quantum Safe |access-date=2022-01-13 |archive-date=2021-04-20 |archive-url=https://web.archive.org/web/20210420002308/https://openquantumsafe.org/liboqs/algorithms/kem/kyber |url-status=dead }}</ref> on that.<ref name="Duits19"/> OQS also maintains a quantum-safe development branch of [[Software:OpenSSL|OpenSSL]],<ref name="PQ OpenSSL"/> has integrated it into [[BoringSSL]], and its code has also been integrated into [[Software:WolfSSL|WolfSSL]].<ref name="wolfSSL-liboqs"/> There are a handful of implementations using various other programming languages from third-party developers, including JavaScript and Java.<ref>{{cite web |url=https://github.com/fisherstevenk/kyberJCE |title = CRYSTALS KYBER Java|website = [[GitHub]] |date = 25 October 2021 }}</ref><ref>{{cite web |url=https://github.com/antontutoveanu/crystals-kyber-javascript |title = CRYSTALS-KYBER JavaScript |website = [[GitHub]] |date = 11 December 2021 }}</ref><ref>{{cite web |url=https://git.schwanenlied.me/yawning/kyber |title=Yawning/Kyber |access-date=2022-01-13 |archive-date=2021-07-28 |archive-url=https://web.archive.org/web/20210728002417/https://git.schwanenlied.me/yawning/kyber |url-status=dead }}</ref> Various (free) optimized hardware implementations exist, including one that is resistant to side-channel attacks.<ref name="Dang et al."/><ref name="Jati et al."/> The German [[Organization:Federal Office for Information Security|Federal Office for Information Security]] is aiming for implementation in [[Software:Mozilla Thunderbird|Thunderbird]], and in this context also an implementation in the [[Software:Botan (programming library)|Botan]] program library and corresponding adjustments to the OpenPGP standard.<ref name="Thunderbird"/>
[[File:Cloudflare Post-Quantum Key Agreement on Firefox 135.0 screenshot.webp|thumb|Screenshot of [[Cloudflare]] Post-Quantum Key Agreement test page showing [[Software:Firefox|Firefox]] 135.0 using X25519MLKEM768]]
In 2023, the encrypted messaging service [[Software:Signal|Signal]] implemented PQXDH, a Kyber-based post-quantum encryption algorithm, to their [[Signal Protocol]] which is used by [[Software:WhatsApp|WhatsApp]] and others.<ref name="Signal"/><ref>{{cite web |title=Signal Messenger Introduces PQXDH Quantum-Resistant Encryption |url=https://thehackernews.com/2023/09/signal-messenger-introduces-pqxdh.html |access-date=2023-09-22 |website=The Hacker News |language=en}}</ref>
The developers have released a [[Reference implementation|reference implementation]] into the [[Social:Public domain|public domain]] (or under CC0), which is written in [[C (programming language)|C]].<ref name="PD"/> The [[Library (computing)|program library]] ''liboqs'' of the Open Quantum Safe (OQS) project contains an implementation based<ref>{{cite web |url=https://openquantumsafe.org/liboqs/algorithms/kem/Kyber |title=Kyber – Open Quantum Safe |access-date=2022-01-13 |archive-date=2021-04-20 |archive-url=https://web.archive.org/web/20210420002308/https://openquantumsafe.org/liboqs/algorithms/kem/kyber |url-status=dead }}</ref> on that.<ref name="Duits19"/> OQS also maintains a quantum-safe Provider module for [[Software:OpenSSL|OpenSSL]] 3.x,<ref name="PQ OpenSSL"/> and has integrated its code into [[BoringSSL]] and [[Software:WolfSSL|wolfSSL]].<ref name="wolfSSL-liboqs"/> There are a handful of implementations using various other programming languages from third-party developers, including JavaScript and Java.<ref>{{cite web |url=https://github.com/fisherstevenk/kyberJCE |title = CRYSTALS KYBER Java|website = [[GitHub]] |date = 25 October 2021 }}</ref><ref>{{cite web |url=https://github.com/antontutoveanu/crystals-kyber-javascript |title = CRYSTALS-KYBER JavaScript |website = [[GitHub]] |date = 11 December 2021 }}</ref><ref>{{cite web |url=https://git.schwanenlied.me/yawning/kyber |title=Yawning/Kyber |access-date=2022-01-13 |archive-date=2021-07-28 |archive-url=https://web.archive.org/web/20210728002417/https://git.schwanenlied.me/yawning/kyber |url-status=dead }}</ref> Various (free) optimized hardware implementations exist, including one that is resistant to side-channel attacks.<ref name="Dang et al."/><ref name="Jati et al."/> The German [[Organization:Federal Office for Information Security|Federal Office for Information Security]] is aiming for implementation in [[Software:Mozilla Thunderbird|Thunderbird]], and in this context also an implementation in the [[Software:Botan (programming library)|Botan]] program library and corresponding adjustments to the OpenPGP standard.<ref name="Thunderbird"/>
[[Company:Amazon Web Services|Amazon Web Services]] (AWS) integrated Kyber into their Key Management Service (KMS) in 2020 as a hybrid post-quantum key exchange option for [[Transport Layer Security|TLS]] connections.<ref>{{Cite web |date=2020-11-16 |title=Round 2 post-quantum TLS is now supported in AWS KMS {{!}} AWS Security Blog |url=https://aws.amazon.com/blogs/security/round-2-post-quantum-tls-is-now-supported-in-aws-kms/ |access-date=2025-02-17 |website=aws.amazon.com |language=en-US}}</ref> In 2023, the encrypted messaging service Signal implemented PQXDH, a Kyber-based post-quantum encryption algorithm, to their [[Signal Protocol]].<ref name="Signal"/><ref>{{cite web |title=Signal Messenger Introduces PQXDH Quantum-Resistant Encryption |url=https://thehackernews.com/2023/09/signal-messenger-introduces-pqxdh.html |access-date=2023-09-22 |website=The Hacker News |language=en}}</ref>  
 
== Implementations ==
* [[Software:OpenSSL|OpenSSL]]
* [[Software:WolfSSL|wolfSSL]]
* libOQS
* [[Software:IAIK-JCE|IAIK-JCE]]


== References ==
== References ==
Line 32: Line 40:
(PDF-Datei)</ref>
(PDF-Datei)</ref>


<ref name="NISTIR 8309">[https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf Status Report on the Second Round of the NIST PQC Standardization Process] (PDF-Datei)</ref>
<ref name="NISTIR 8309">[https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf Status Report on the Third Round of the NIST PQC Standardization Process] (PDF-Datei)</ref>


<ref name="Peikert&Pepin">
<ref name="Peikert&Pepin">
Line 68: Line 76:
}}</ref>
}}</ref>


<ref name="v3.02">https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf {{Bare URL PDF|date=March 2022}}</ref>
<ref name="v3.02">{{Cite web |date=4 August 2021 |title=CRYSTALS-Kyber Algorithm Specifications And Supporting Documentation |url=https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf}}</ref>


<ref name="nttm4">
<ref name="nttm4">
Line 93: Line 101:
  |title=The Post-Quantum Signal Protocol: Secure Chat in a Quantum World
  |title=The Post-Quantum Signal Protocol: Secure Chat in a Quantum World
  |date=2019-02-05
  |date=2019-02-05
  |language=German
  |language=en
  |url=https://essay.utwente.nl/77239/1/Duits_MA_EEMCS.pdf
  |url=https://essay.utwente.nl/77239/1/Duits_MA_EEMCS.pdf
}}</ref>
}}</ref>


<ref name="PD">[https://github.com/pq-crystals/kyber/blob/master/LICENSE Kyber/LICENSE at master · pq-crystals/kyber · GitHub]</ref>
<ref name="PD">{{Cite web|url=https://github.com/pq-crystals/kyber/blob/main/LICENSE|title=kyber/LICENSE at main · pq-crystals/kyber|website=GitHub}}</ref>


<ref name="PQ OpenSSL">
<ref name="PQ OpenSSL">
{{cite web |title=Post-Quantum TLS
{{cite web |title=OQS Provider for OpenSSL 3.x
  |periodical=Microsoft Research
  |periodical=Oqs-provider
  |publisher=
  |publisher=
  |url=https://www.microsoft.com/en-us/research/project/post-quantum-tls/
  |url=https://github.com/open-quantum-safe/oqs-provider
  |url-status=
  |url-status=
  |format=
  |format=
Line 163: Line 171:


== External links ==
== External links ==
* {{Official website|https://pq-crystals.org/kyber/}}
* {{GitHub|pq-crystals/kyber}}
* {{GitHub|pq-crystals/kyber}}
* original method by {{citation |surname1=Oded Regev |periodical=Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC '05) |title=On lattices, learning with errors, random linear codes, and cryptography |publication-place=Baltimore, MD, USA |publisher=ACM Press |page=84 |isbn=978-1-58113-960-0 |date=2005 |language=German |doi=10.1145/1060590.1060603 |s2cid=53223958 |url=http://portal.acm.org/citation.cfm?doid=1060590.1060603 |arxiv=2401.03703 }}
* original method by {{citation |surname1=Oded Regev |periodical=Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC '05) |title=On lattices, learning with errors, random linear codes, and cryptography |publication-place=Baltimore, MD, USA |publisher=ACM Press |page=84 |isbn=978-1-58113-960-0 |date=2005 |language=German |doi=10.1145/1060590.1060603 |s2cid=53223958 |url=http://portal.acm.org/citation.cfm?doid=1060590.1060603 |arxiv=2401.03703 }}
* [https://csrc.nist.gov/pubs/fips/203/final FIPS 203 "Module-Lattice-Based Key-Encapsulation Mechanism Standard"]


{{ Cryptography navbox | public-key }}
{{ Cryptography navbox | public-key }}

Latest revision as of 20:09, 17 August 2025

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

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]

  • public key compression removed (due to NIST comments on the security proof);
  • parameter q reduced to 3329 (from 7681);
  • ciphertext compression parameters changed;
  • number-theoretic transform (NTT) definition changed along the lines of NTTRU for faster polynomial multiplication;
  • noise parameter reduced to η = 2 for faster noise sampling;
  • public key representation changed to NTT domain in order to save the NTT operations.

Submission to round 3 underwent further tweaks:[14]

  • the use of Fujisaki–Okamoto transformation (FO transform) modified;
  • noise level increased and ciphertext compression reduced for the level 1 parameter set;
  • sampling algorithm improved.

Usage

Screenshot of Cloudflare Post-Quantum Key Agreement test page showing Firefox 135.0 using X25519MLKEM768

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] Amazon Web Services (AWS) integrated Kyber into their Key Management Service (KMS) in 2020 as a hybrid post-quantum key exchange option for TLS connections.[25] In 2023, the encrypted messaging service Signal implemented PQXDH, a Kyber-based post-quantum encryption algorithm, to their Signal Protocol.[26][27]

Implementations

References

  1. ↑ Moody, Dustin (2022), Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, Gaithersburg, MD, pp. NIST IR 8413, doi:10.6028/nist.ir.8413, https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf 
  2. ↑ Technology, National Institute of Standards and (13 August 2024). "Module-Lattice-Based Key-Encapsulation Mechanism Standard [FIPS 203"] (in en). U.S. Department of Commerce. https://csrc.nist.gov/pubs/fips/203/final. 
  3. ↑ What was NIST thinking? (PDF-Datei)
  4. ↑ 4.0 4.1 4.2 Status Report on the Third Round of the NIST PQC Standardization Process (PDF-Datei)
  5. ↑ Chris Peikert, Zachary Pepin (2019), "Algebraically Structured LWE, Revisited" (in German), Theory of Cryptography, Lecture Notes in Computer Science (Cham: Springer International Publishing) 11891: 1–23, doi:10.1007/978-3-030-36030-6_1, ISBN 978-3-030-36029-0, http://web.eecs.umich.edu/~cpeikert/pubs/structured-lwe.pdf 
  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): 353–367, doi:10.1109/EuroSP.2018.00032, ISBN 978-1-5386-4228-3, https://eprint.iacr.org/2017/634 
  9. ↑ "CRYSTALS-Kyber Algorithm Specifications And Supporting Documentation". 4 August 2021. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf. 
  10. ↑ 10.0 10.1 10.2 Leon Botros, Matthias J. Kannwischer, Peter Schwabe (2019), "Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4" (in German), Progress in Cryptology – AFRICACRYPT 2019, Lecture Notes in Computer Science (Cham: Springer International Publishing) 11627: 209–228, doi:10.1007/978-3-030-23696-0_11, ISBN 978-3-030-23696-0, https://kannwischer.eu/papers/2019_nttm4.pdf 
  11. ↑ 11.0 11.1 Ines Duits (2019-02-05) (in en), The Post-Quantum Signal Protocol: Secure Chat in a Quantum World, https://essay.utwente.nl/77239/1/Duits_MA_EEMCS.pdf 
  12. ↑ Schwabe, Peter. "CRYSTALS". https://pq-crystals.org/. 
  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 main · pq-crystals/kyber". https://github.com/pq-crystals/kyber/blob/main/LICENSE. 
  16. ↑ "Kyber – Open Quantum Safe". https://openquantumsafe.org/liboqs/algorithms/kem/Kyber. 
  17. ↑ "OQS Provider for OpenSSL 3.x" (in en-US). https://github.com/open-quantum-safe/oqs-provider. 
  18. ↑ "wolfSSL and libOQS Integration" (in en-US). 2021-09-01. https://www.wolfssl.com/wolfssl-liboqs-integration/. 
  19. ↑ "CRYSTALS KYBER Java". 25 October 2021. https://github.com/fisherstevenk/kyberJCE. 
  20. ↑ "CRYSTALS-KYBER JavaScript". 11 December 2021. https://github.com/antontutoveanu/crystals-kyber-javascript. 
  21. ↑ "Yawning/Kyber". https://git.schwanenlied.me/yawning/kyber. 
  22. ↑ B. Dang, Kamyar Mohajerani, K. Gaj (2021) (in German), High-Speed Hardware Architectures and Fair FPGA Benchmarking, https://csrc.nist.gov/CSRC/media/Events/third-pqc-standardization-conference/documents/accepted-papers/gaj-high-speed-hardware-gmu-pqc2021.pdf 
  23. ↑ Arpan Jati, Naina Gupta, A. Chattopadhyay, S. Sanadhya (2021), "A Configurable Crystals-Kyber Hardware Implementation with Side-Channel Protection" (in German), IACR Cryptol. ePrint Arch., https://eprint.iacr.org/2021/1189.pdf 
  24. ↑ "E-Vergabe, die Vergabeplattform des Bundes". https://www.evergabe-online.de/tenderdetails.html?id=397181. 
  25. ↑ "Round 2 post-quantum TLS is now supported in AWS KMS | AWS Security Blog" (in en-US). 2020-11-16. https://aws.amazon.com/blogs/security/round-2-post-quantum-tls-is-now-supported-in-aws-kms/. 
  26. ↑ "Add Kyber KEM and implement PQXDH protocol". https://github.com/signalapp/libsignal/commit/ff09619432e19e96231ebed913fe4433f26ee0d2. 
  27. ↑ "Signal Messenger Introduces PQXDH Quantum-Resistant Encryption" (in en). https://thehackernews.com/2023/09/signal-messenger-introduces-pqxdh.html. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Kyber&oldid=3742378"