Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Simpósio Brasileiro de Cibersegurança (SBSeg)

The Importance of the Public Global Parameter on Ring-LWE problem-based Key Encapsulation Mechanims

Reynaldo Caceres Villena, Routo Terada

Published Sep 12, 2022• 0 citations
Publisher

Abstract

There are cryptographic systems that are secure against attacks by both quantum and classical computers. Some of these cryptographic systems are the Key Encapsulation Mechanisms (KEM) based on Ring-LWE problem. Some Ring-LWE problem-based KEMs include a public global parameter that is random and uniformly chosen. This parameter is used to generatea public key using in the process one secret key. In this work, we analyze some values of the public global parameter that leak information about the secret key.

DOI
10.5753/sbseg.2022.223952

Related papers

Ataques e vulnerabilidades no NewHope KEM e no problema Ring-LWE

Reynaldo Caceres Villena

There are cryptographic systems that are secure against attacks by both classical and quantum computers. One of these systems is the NewHope key encapsulation mechanism (KEM) based on the Ring-learning with error problem (Ring-LWE problem). The Ring-LWE problem is presumed to be hard to solve even on a quantum computer. A KEM scheme allows sharing of a common key between two parts (Alice & Bob). This thesis presents original contributions to the security and analysis of key mismatch and information leakage attacks on NewHope KEM and some vulnerabilities on (small)-Ring-LWE problem (a variant of Ring-LWE problem). The first contribution contains some improvements on key mismatch attacks proposed by Bauer et al. and Qin et al. (Bauer et al., 2019; Qin et al., 2019). These key mismatch attacks retrieve Alices secret key. And, we propose two new methods named Fast Qin and Double Qin. The methods Fast Qin and Double Qin require around 240k and 34k oracle queries, respectively; instead of 840k queries of the Qin et al.s method. Moreover, these two new methods are adapted to retrieve Alices secret key on NewHope-512 (a variant of NewHope). The second contribution analyzes the information leakage of Bobs secret key on NewHope when it is reused. Our result corroborates that Bobs secret key must not be reused since with two communications to Bob, his secret key is leaked. In Ring-LWE problem, a polynomial a is selected randomly and a polynomial b is calculated as b = a.s+e where s is the secret polynomial (selected randomly) and the e is a noise polynomial. Our third contribution shows that in small-Ring-LWE, a variant where polynomials s and e are small, there are values of the public parameter a that leak a large percentage of the coefficients of the secret s. And, the last contribution shows that the secret s can be retrieved successfully if at least 50% of the random known coefficients of s and e are known.

•Oct 18, 2024•0 citations

Lattice-based PKEs/KEMs

Xianhui Lu, Jiang Zhang

The invention of public-key cryptography (PKC) by Diffie and Hellman in 1976 is one of two milestones marking the beginning of modern cryptography. The security of a PKC system requires that it should be infeasible to compute the private key from a given public key, which in turn is typically guaranteed by the difficulty in solving some cryptographic-friendly mathematical problems. Among those problems, the integer factorization and discrete logarithm problems play pivotal roles in the development of public-key cryptography. In particular, the assumption that there is no polynomial time (classical) algorithm that solves the above two problems constitutes the basis for the security of almost all currently used public-key cryptosystems, such as RSA and ElGamal. However, Shor [1] found an efficient quantum solving algorithm for the integer factorization and discrete logarithm problems in 1994, which would destroy the security basis for most real deployed PKC systems if large-scale quantum computers become available. The rapid development of quantum technology in recent years suggests that we are getting closer to the quantum crisis of current PKC systems. As a response to the quantum crisis, the research community has made many efforts to post-quantum cryptography (PQC) that are believed to resist quantum computer attacks. Lattice-based cryptography is one of the main directions in this area, and has become the most promising PQC candidate for standardization. The research of lattice-based cryptography dates back to the seminal work of Ajtai [2], which first based the security of cryptographic primitives on the difficulty of solving some lattice problems such as the approximate shortest vector problem and the closest vector problem. After more than two decades of development, lattice-based cryptography has gained substantial progress. In theory, we have witnessed the construction of many powerful cryptographic primitives that were not known before. In practice, the public key size of lattice-based cryptosystems has been significantly reduced from several gigabytes to a few kilobytes. For current applications and standardization, key exchanges, public-key encryptions (PKEs) and signatures are the most desired lattice-based cryptosystems, where the first two are often used to ensure information secrecy, while the last provides information authentication. Note that public-key encryptions are equivalent to two-round key exchanges, also known as the key encapsulation mechanism (KEM). In the following, we focus on lattice-based PKEs/KEMs. The design principle of lattice-based PKEs/KEMs follows two approaches: a trapdoor one-way function and an approximate commutative one-way function. In the first approach, a trapdoor one-way function f and its trapdoor f−1 are generated as the public key and private key. A plaintext m is encrypted as c = f(m), and the ciphertext is decrypted as m = f−1(c). The NTRU scheme and its variants follow such an approach. In the second approach, an approximate commutative function fs and a random input a are generated, the public key is (a, b = fs(a)) and the private key is s. A plaintext m is encrypted as c1 = gr(a), c2 = gr(b) + E(m), where r is a random element, g is an approximate commutative one-way function and E is the encoding of an error-correction code. The ciphertext (c1, c2) is decrypted as m = D(c2 − fs(c1)), where D is the decoding of an error-correction code. The correctness of decryption is guaranteed by the approximate commutative property (gr(b) = gr(fs(a)) ≈ fs(gr(a)) = fs(c1)) and the error-correction code. Learning with errors (LWE) problem-based PKE/KEM schemes and their variants follow such an approach. The standardization of PQC has received substantial support from national funding agencies, such as the European Union projects PQCrypto and SAFEcrypto. The USA National Institute of Standard and Technology (NIST) started the post-quantum standardization project in 2012, organized a worldwide ‘competition’ in 2016 and plans to deliver draft standards before 2024. After two rounds of evaluation, seven schemes were accepted as the round-three candidates on 22 July 2020, of which five are lattice-based schemes. In 2017, the International organization for standardization started a study project of post-quantum cryptography named SD8. Most LWE-based PKE schemes such as Kyber and LAC follow the Lindner-Peikert framework [3] up to the choices of ring structure, noise distribution and parameters. As the size of noise in lattice-based PKEs/EKMs is typically larger than the lower bits of the ciphertext, many schemes often artificially drop a few lower bits to optimize the practical performance without significantly increasing the final decryption noise. Kyber [4] is one of the most promising PKE/KEM candidates in the NIST PQC standardization, whose security is provably based on the difficulty of so-called module LWE (MLWE) problems. The use of MLWE allowed Kyber to obtain additional flexibility and security advantages, while keeping the same efficiency as those based on the ring-LWE problems. The strategy of dropping some lower bits is used to compress both the public-key and ciphertext sizes. For a targeted 128-bit quantum security, the public-key and ciphertext sizes of Kyber is around a single kilobyte. LAC [5] uses several techniques to reduce the modulus as small as possible: it uses a byte-level modulus, embeds powerful error-correcting codes to maximize the noise-modulus rate, provides a different style of modulus to avoid potential attacks for special polynomial ring structures and optimizes the polynomial multiplication algorithm of the bit-level secret and noise. Based on these techniques, LAC reduces the public key to 544–1056 bytes and the ciphertext to 664–1464 bytes. Meanwhile, it achieves similar computational performance compared with NTT technique schemes. By observing the asymmetries in lattice-based cryptosystems, Zhang and Yu et al. [6] proposed asymmetric MLWE and asymmetric MSIS problems, which yield further size-optimized KEMs and signature schemes to those from standard counterparts. Compared to the seven NIST round-three candidates at Category III security, their KEM scheme has parameters (public key + ciphertext size) smaller than Classic McEliece, CRYSTALS-Kyber, NTRU and Saber; their signature scheme has parameters (public key + signature size) smaller than CRYSTALS-Dilithium and Rainbow, but slightly larger than FALCON, where CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium and FALCON are lattice-based schemes. One important application of lattice-based PKEs/KEMs is to build authenticated key exchange (AKE), which could provide additional authentication to the established session key. There are several generic ways to construct AKE from lattice-based PKEs/KEMs. In the PKE setting, Xue and Lu et al. [7] proposed a more compact KEM-based framework via a new primitive named ‘2-key KEM’, which shares some item between different ciphertexts. In the only password setting, Zhang and Yu [8] presented a two-round PAKE framework from the splittable-PKEs that can be instantiated from lattices. The only known AKE that does not rely on lattice-based PKEs/KEMs was given in Ref. [9], which has two-round messages and provides implicit authentication. This work was supported by the National Natural Science Foundation of China (6197239 to X.L.; 62022018 and 61932019 to J.Z.) and the National Key Research and Development Program of China (2018YFB0804105 to J.Z.). Conflict of interest statement. None declared.

National Science Review•May 20, 2021•1 citation

Design and Analysis of Post Quantum Secure Ideal Lattice Based Key Encapsulation Mechanism for Mobile Communication System

Pradeep Kumar Dadsena, Madireddy H. V. S. P. Reddy, Saurabh Rana +3 more

Post Quantum Key Encapsulation Mechanism (PKEM) is used to securely exchange symmetric keys over an insecure channel. It allows two parties to establish a shared secret key, which can then be used for symmetric encryption, ensuring confidentiality against quantum attacks. By encapsulating the key, it reduces the need to directly encrypt large amounts of data with the public key, which is computationally expensive. Traditional cryptographic tools, while effective, are complex and susceptible to quantum attacks. This paper contains a robust and lightweight post-quantum security solution, and their performance analysis. The authentication scheme, based on Ring-Learning with Errors (Ring-LWE), uses Bernstein reconstruction in polynomial multiplication to significantly lower computational costs, enabling even resource-limited mobile devices to achieve secure mutual authentication. This paper also contains an analysis of post-quantum key encapsulation mechanism (PKEM), and it also covers design, security, and real-world implementation issues and provides a prospective outlook on PKEM, taking into account current investigations, possible innovations, and the changing field of quantum computing. The proposed work also offers a thorough investigation of the security features of post-quantum KEMs, together with theoretical and practical concerns.

International Conference on Innovative Sustainable Computational Technologies (CISCT)•Dec 27, 2024•0 citations

Keeping Up with the KEMs: Stronger Security Notions for KEMs and Automated Analysis of KEM-based Protocols

Cas J. F. Cremers, Alexander Dax, Niklas Medinger

Key Encapsulation Mechanisms (KEMs) are a critical building block for hybrid encryption and modern security protocols, notably in the post-quantum setting. Given the asymmetric public key of a recipient, the primitive establishes a shared secret key between sender and recipient. In recent years, a large number of abstract designs and concrete implementations of KEMs have been proposed, e.g., in the context of the NIST process for post-quantum primitives.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Dec 2, 2024•24 citations

Reconstructing Public-Key Cryptography: Lattice Foundations for a Post-Quantum Future Beyond RSA

Revista, Zen, MATH, 10

The imminent threat posed by the advent of quantum computers to contemporary public-key cryptographic schemes, such as RSA and Elliptic Curve Cryptography (ECC), necessitates a fundamental shift in cryptographic paradigms. Shor's algorithm, specifically, presents a catastrophic vulnerability to these foundational security protocols, underpinning global digital communication and commerce. This paper provides a comprehensive exploration into lattice-based cryptography as a robust and promising candidate for a post-quantum cryptographic future. We delve into the mathematical underpinnings of lattices, elucidating the computational hardness of problems like the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, which form the bedrock of their security. The paper reviews the historical development of lattice-based schemes, their theoretical advantages, and their practical implications, particularly in the context of the ongoing NIST Post-Quantum Cryptography standardization process. We analyze the construction of key encapsulation mechanisms (KEMs) and digital signature schemes from lattice problems, comparing their performance characteristics and security guarantees against classical methods. The work argues that lattice-based cryptography offers a compelling alternative to RSA, providing not only quantum resistance but also presenting attractive features in terms of efficiency, design simplicity, and versatility for various cryptographic primitives. The discussion extends to implementation challenges, security analysis, and the broader implications for the global migration towards a quantum-secure cryptographic infrastructure.

•Dec 5, 2025•0 citations

Post-Quantum Hybrid Encryption from Correlated Randomness: QKEM and Biometric KEMs

Reihaneh Safavi–Naini

The Key Encapsulation Mechanism (KEM) is a widely used public-key cryptographic primitive that has evolved into numerous variants and found diverse applications in recent years. In this talk, we explore KEMs in the setting of correlated randomness, where Alice and Bob, instead of using public keys, have access to correlated samples from a shared random source.

•Oct 13, 2025•0 citations
There are cryptographic systems that are secure against attacks by both quantum and classical computers. Some of these cryptographic systems are the Key Encapsulation Mechanisms (KEM) based on Ring-LWE problem. Some Ring-LWE problem-based KEMs include a public global parameter that is random and uniformly chosen. This parameter is used to generatea public key using in the process one secret key. In this work, we analyze some values of the public global parameter that leak information about the secret key.
There are cryptographic systems that are secure against attacks by both classical and quantum computers. One of these systems is the NewHope key encapsulation mechanism (KEM) based on the Ring-learning with error problem (Ring-LWE problem). The Ring-LWE problem is presumed to be hard to solve even on a quantum computer. A KEM scheme allows sharing of a common key between two parts (Alice & Bob). This thesis presents original contributions to the security and analysis of key mismatch and information leakage attacks on NewHope KEM and some vulnerabilities on (small)-Ring-LWE problem (a variant of Ring-LWE problem). The first contribution contains some improvements on key mismatch attacks proposed by Bauer et al. and Qin et al. (Bauer et al., 2019; Qin et al., 2019). These key mismatch attacks retrieve Alices secret key. And, we propose two new methods named Fast Qin and Double Qin. The methods Fast Qin and Double Qin require around 240k and 34k oracle queries, respectively; instead of 840k queries of the Qin et al.s method. Moreover, these two new methods are adapted to retrieve Alices secret key on NewHope-512 (a variant of NewHope). The second contribution analyzes the information leakage of Bobs secret key on NewHope when it is reused. Our result corroborates that Bobs secret key must not be reused since with two communications to Bob, his secret key is leaked. In Ring-LWE problem, a polynomial a is selected randomly and a polynomial b is calculated as b = a.s+e where s is the secret polynomial (selected randomly) and the e is a noise polynomial. Our third contribution shows that in small-Ring-LWE, a variant where polynomials s and e are small, there are values of the public parameter a that leak a large percentage of the coefficients of the secret s. And, the last contribution shows that the secret s can be retrieved successfully if at least 50% of the random known coefficients of s and e are known.
The invention of public-key cryptography (PKC) by Diffie and Hellman in 1976 is one of two milestones marking the beginning of modern cryptography. The security of a PKC system requires that it should be infeasible to compute the private key from a given public key, which in turn is typically guaranteed by the difficulty in solving some cryptographic-friendly mathematical problems. Among those problems, the integer factorization and discrete logarithm problems play pivotal roles in the development of public-key cryptography. In particular, the assumption that there is no polynomial time (classical) algorithm that solves the above two problems constitutes the basis for the security of almost all currently used public-key cryptosystems, such as RSA and ElGamal. However, Shor [1] found an efficient quantum solving algorithm for the integer factorization and discrete logarithm problems in 1994, which would destroy the security basis for most real deployed PKC systems if large-scale quantum computers become available. The rapid development of quantum technology in recent years suggests that we are getting closer to the quantum crisis of current PKC systems. As a response to the quantum crisis, the research community has made many efforts to post-quantum cryptography (PQC) that are believed to resist quantum computer attacks. Lattice-based cryptography is one of the main directions in this area, and has become the most promising PQC candidate for standardization. The research of lattice-based cryptography dates back to the seminal work of Ajtai [2], which first based the security of cryptographic primitives on the difficulty of solving some lattice problems such as the approximate shortest vector problem and the closest vector problem. After more than two decades of development, lattice-based cryptography has gained substantial progress. In theory, we have witnessed the construction of many powerful cryptographic primitives that were not known before. In practice, the public key size of lattice-based cryptosystems has been significantly reduced from several gigabytes to a few kilobytes. For current applications and standardization, key exchanges, public-key encryptions (PKEs) and signatures are the most desired lattice-based cryptosystems, where the first two are often used to ensure information secrecy, while the last provides information authentication. Note that public-key encryptions are equivalent to two-round key exchanges, also known as the key encapsulation mechanism (KEM). In the following, we focus on lattice-based PKEs/KEMs. The design principle of lattice-based PKEs/KEMs follows two approaches: a trapdoor one-way function and an approximate commutative one-way function. In the first approach, a trapdoor one-way function f and its trapdoor f−1 are generated as the public key and private key. A plaintext m is encrypted as c = f(m), and the ciphertext is decrypted as m = f−1(c). The NTRU scheme and its variants follow such an approach. In the second approach, an approximate commutative function fs and a random input a are generated, the public key is (a, b = fs(a)) and the private key is s. A plaintext m is encrypted as c1 = gr(a), c2 = gr(b) + E(m), where r is a random element, g is an approximate commutative one-way function and E is the encoding of an error-correction code. The ciphertext (c1, c2) is decrypted as m = D(c2 − fs(c1)), where D is the decoding of an error-correction code. The correctness of decryption is guaranteed by the approximate commutative property (gr(b) = gr(fs(a)) ≈ fs(gr(a)) = fs(c1)) and the error-correction code. Learning with errors (LWE) problem-based PKE/KEM schemes and their variants follow such an approach. The standardization of PQC has received substantial support from national funding agencies, such as the European Union projects PQCrypto and SAFEcrypto. The USA National Institute of Standard and Technology (NIST) started the post-quantum standardization project in 2012, organized a worldwide ‘competition’ in 2016 and plans to deliver draft standards before 2024. After two rounds of evaluation, seven schemes were accepted as the round-three candidates on 22 July 2020, of which five are lattice-based schemes. In 2017, the International organization for standardization started a study project of post-quantum cryptography named SD8. Most LWE-based PKE schemes such as Kyber and LAC follow the Lindner-Peikert framework [3] up to the choices of ring structure, noise distribution and parameters. As the size of noise in lattice-based PKEs/EKMs is typically larger than the lower bits of the ciphertext, many schemes often artificially drop a few lower bits to optimize the practical performance without significantly increasing the final decryption noise. Kyber [4] is one of the most promising PKE/KEM candidates in the NIST PQC standardization, whose security is provably based on the difficulty of so-called module LWE (MLWE) problems. The use of MLWE allowed Kyber to obtain additional flexibility and security advantages, while keeping the same efficiency as those based on the ring-LWE problems. The strategy of dropping some lower bits is used to compress both the public-key and ciphertext sizes. For a targeted 128-bit quantum security, the public-key and ciphertext sizes of Kyber is around a single kilobyte. LAC [5] uses several techniques to reduce the modulus as small as possible: it uses a byte-level modulus, embeds powerful error-correcting codes to maximize the noise-modulus rate, provides a different style of modulus to avoid potential attacks for special polynomial ring structures and optimizes the polynomial multiplication algorithm of the bit-level secret and noise. Based on these techniques, LAC reduces the public key to 544–1056 bytes and the ciphertext to 664–1464 bytes. Meanwhile, it achieves similar computational performance compared with NTT technique schemes. By observing the asymmetries in lattice-based cryptosystems, Zhang and Yu et al. [6] proposed asymmetric MLWE and asymmetric MSIS problems, which yield further size-optimized KEMs and signature schemes to those from standard counterparts. Compared to the seven NIST round-three candidates at Category III security, their KEM scheme has parameters (public key + ciphertext size) smaller than Classic McEliece, CRYSTALS-Kyber, NTRU and Saber; their signature scheme has parameters (public key + signature size) smaller than CRYSTALS-Dilithium and Rainbow, but slightly larger than FALCON, where CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium and FALCON are lattice-based schemes. One important application of lattice-based PKEs/KEMs is to build authenticated key exchange (AKE), which could provide additional authentication to the established session key. There are several generic ways to construct AKE from lattice-based PKEs/KEMs. In the PKE setting, Xue and Lu et al. [7] proposed a more compact KEM-based framework via a new primitive named ‘2-key KEM’, which shares some item between different ciphertexts. In the only password setting, Zhang and Yu [8] presented a two-round PAKE framework from the splittable-PKEs that can be instantiated from lattices. The only known AKE that does not rely on lattice-based PKEs/KEMs was given in Ref. [9], which has two-round messages and provides implicit authentication. This work was supported by the National Natural Science Foundation of China (6197239 to X.L.; 62022018 and 61932019 to J.Z.) and the National Key Research and Development Program of China (2018YFB0804105 to J.Z.). Conflict of interest statement. None declared.
Post Quantum Key Encapsulation Mechanism (PKEM) is used to securely exchange symmetric keys over an insecure channel. It allows two parties to establish a shared secret key, which can then be used for symmetric encryption, ensuring confidentiality against quantum attacks. By encapsulating the key, it reduces the need to directly encrypt large amounts of data with the public key, which is computationally expensive. Traditional cryptographic tools, while effective, are complex and susceptible to quantum attacks. This paper contains a robust and lightweight post-quantum security solution, and their performance analysis. The authentication scheme, based on Ring-Learning with Errors (Ring-LWE), uses Bernstein reconstruction in polynomial multiplication to significantly lower computational costs, enabling even resource-limited mobile devices to achieve secure mutual authentication. This paper also contains an analysis of post-quantum key encapsulation mechanism (PKEM), and it also covers design, security, and real-world implementation issues and provides a prospective outlook on PKEM, taking into account current investigations, possible innovations, and the changing field of quantum computing. The proposed work also offers a thorough investigation of the security features of post-quantum KEMs, together with theoretical and practical concerns.
The imminent threat posed by the advent of quantum computers to contemporary public-key cryptographic schemes, such as RSA and Elliptic Curve Cryptography (ECC), necessitates a fundamental shift in cryptographic paradigms. Shor's algorithm, specifically, presents a catastrophic vulnerability to these foundational security protocols, underpinning global digital communication and commerce. This paper provides a comprehensive exploration into lattice-based cryptography as a robust and promising candidate for a post-quantum cryptographic future. We delve into the mathematical underpinnings of lattices, elucidating the computational hardness of problems like the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, which form the bedrock of their security. The paper reviews the historical development of lattice-based schemes, their theoretical advantages, and their practical implications, particularly in the context of the ongoing NIST Post-Quantum Cryptography standardization process. We analyze the construction of key encapsulation mechanisms (KEMs) and digital signature schemes from lattice problems, comparing their performance characteristics and security guarantees against classical methods. The work argues that lattice-based cryptography offers a compelling alternative to RSA, providing not only quantum resistance but also presenting attractive features in terms of efficiency, design simplicity, and versatility for various cryptographic primitives. The discussion extends to implementation challenges, security analysis, and the broader implications for the global migration towards a quantum-secure cryptographic infrastructure.