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

IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech)

a key exchange scheme based on lattice

Wulu Li

Published Dec 1, 2013• 2 citations
Publisher

Abstract

We construct a key exchange scheme with session key security and Alice's privacy, assuming the hardness of "small integer solution" (SIS) problem and "learning with errors" (LWE) problem, which have worst-case to average-case reductions from lattice problems. Our key exchange scheme is the first lattice-based key exchange scheme with provable security. Moreover, our scheme can be modified to be secure under impersonation attack by adding an authentication step, also, it can be modified to be more efficient using a new variant of LWE.

DOI
10.1109/dasc.2013.45

Related papers

Lattice - Based Cryptography - Security Foundations and Constructions

Adeline Roux-Langlois

Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013.

•Jan 1, 2014•1 citation

New Authenticated Key Exchange Scheme Based on Ring Learning with Errors Problem

Xiaopeng Yang, Wenping Ma, Chengli Zhang

Using the hard assumption of Ring-Decision Learning With Errors (Ring-DLWE) in the lattice, a new Authenticated Key Exchange (AKE) scheme is proposed, which is based on the Peikert's reconciliation technique. Under the standard model, the proposed scheme is provably secure in the CK model, which is additionally achieves weak Perfect Forward Secrecy (wPFS). Compared with the current Key Exchange (KE) schemes based on the LWE, the proposed scheme not only protects the shared session key with balanced key derivation function but also resists quantum attacks because of the hard assumption on lattice problem.

•Jan 1, 2015•1 citation

A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem.

Jíntai Ding

Abstract. We use a variant of learning with errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which we call a small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear pairing with errors (PE). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem. 1

•Jan 1, 2012•216 citations

Robustly Secure Two-Party Authenticated Key Exchange from Ring-LWE

Xiaopeng Yang, Wenping Ma, Zhang Cheng-li

Using the hard assumption of Ring-Decision Learning With Errors (DLWE) in the lattice, we propose a new authenticated key exchange (AKE) scheme which is based on Peikert’s reconciliation technique. Under the CK+ model, the proposed scheme is provably secure. Compared with the traditional Diffie-Hellman (DH) authenticated key exchange (AKE) schemes, the proposed scheme not only has better efficiency and stronger security but also resists quantum attacks because of the hard assumption on lattice problem. The comparisons between Ring-LWE based ones shows that the proposed scheme protects the shared session key with balanced key derivation function (KDF) compared with those current AKE schemes from LWE.

•Jan 1, 2014•0 citations

A Decade of Lattice Cryptography

Chris Peikert

Lattice-based cryptography is the use of conjectured hard problems on point lattices in ℝn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This work surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.

Foundations and Trends® in Theoretical Computer Science•Mar 24, 2016•521 citations

R-LWE Based Secure Proxy Signature Scheme

Swati Thakur, Hemlal Sahu

In the present scenario where thousands and millions of digital documents are transferred every day, the security of data has become a topic of global concern. Along with other cryptographic primitives, the proxy signature scheme is also widely used in various applications. The main part of our paper is a lattice-based proxy signature scheme. A Proxy Signature scheme is an arrangement that allows the transfer of singing rights from one entity or person to another on behalf of the original signer. Our scheme is based on the Ring-Learning with Error(R-LWE) problem which provides strong security with the worst-case to average-case reduction problem. Key construction and operations in our scheme are based on a ring of polynomials due to which both public and private keys are reduced and the size of the proxy signature also shrunk, while the security of our proposed scheme is based on the Short Integer Solution (SIS) problem.

International Journal of Mathematics And its Applications•Mar 15, 2025•0 citations
We construct a key exchange scheme with session key security and Alice's privacy, assuming the hardness of "small integer solution" (SIS) problem and "learning with errors" (LWE) problem, which have worst-case to average-case reductions from lattice problems. Our key exchange scheme is the first lattice-based key exchange scheme with provable security. Moreover, our scheme can be modified to be secure under impersonation attack by adding an authentication step, also, it can be modified to be more efficient using a new variant of LWE.
Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013.
Using the hard assumption of Ring-Decision Learning With Errors (Ring-DLWE) in the lattice, a new Authenticated Key Exchange (AKE) scheme is proposed, which is based on the Peikert's reconciliation technique. Under the standard model, the proposed scheme is provably secure in the CK model, which is additionally achieves weak Perfect Forward Secrecy (wPFS). Compared with the current Key Exchange (KE) schemes based on the LWE, the proposed scheme not only protects the shared session key with balanced key derivation function but also resists quantum attacks because of the hard assumption on lattice problem.
Abstract. We use a variant of learning with errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which we call a small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear pairing with errors (PE). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem. 1
Using the hard assumption of Ring-Decision Learning With Errors (DLWE) in the lattice, we propose a new authenticated key exchange (AKE) scheme which is based on Peikert’s reconciliation technique. Under the CK+ model, the proposed scheme is provably secure. Compared with the traditional Diffie-Hellman (DH) authenticated key exchange (AKE) schemes, the proposed scheme not only has better efficiency and stronger security but also resists quantum attacks because of the hard assumption on lattice problem. The comparisons between Ring-LWE based ones shows that the proposed scheme protects the shared session key with balanced key derivation function (KDF) compared with those current AKE schemes from LWE.
Lattice-based cryptography is the use of conjectured hard problems on point lattices in ℝn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This work surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.
In the present scenario where thousands and millions of digital documents are transferred every day, the security of data has become a topic of global concern. Along with other cryptographic primitives, the proxy signature scheme is also widely used in various applications. The main part of our paper is a lattice-based proxy signature scheme. A Proxy Signature scheme is an arrangement that allows the transfer of singing rights from one entity or person to another on behalf of the original signer. Our scheme is based on the Ring-Learning with Error(R-LWE) problem which provides strong security with the worst-case to average-case reduction problem. Key construction and operations in our scheme are based on a ring of polynomials due to which both public and private keys are reduced and the size of the proxy signature also shrunk, while the security of our proposed scheme is based on the Short Integer Solution (SIS) problem.