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

Lecture notes in computer science

A Key Exchange Based on the Short Integer Solution Problem and the Learning with Errors Problem

Jíntai Ding, Kevin Schmitt, Zheng Zhang

Published Jan 1, 2019• 7 citations
Publisher
DOI
10.1007/978-3-030-16458-4_8

Related papers

Lattice-based key exchange on small integer solution problem

Shanbiao Wang, Yan Zhu, Di Ma +1 more

Science China Information Sciences•Sep 17, 2014•57 citations

Cryptanalysis of lattice-based key exchange on small integer solution problem and its improvement

Zhengjun Jing, Chunsheng Gu, Zhimin Yu +2 more

Cluster Computing•Mar 5, 2018•15 citations

a key exchange scheme based on lattice

Wulu Li

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.

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)•Dec 1, 2013•2 citations

Improved Attacks Against Key Reuse in Learning with Errors Key Exchange

Nina Bindel, Douglas Stebila, Shannon Veitch

Lecture notes in computer science•Jan 1, 2021•10 citations

On the Quantum Equivalence between S|LWE⟩ and ISIS

André Chailloux, Paul Hermouet

Chen, Liu, and Zhandry [CLZ22] introduced the problems S|LWE⟩ and C|LWE⟩ as quantum analogues of the Learning with Errors problem, designed to construct quantum algorithms for the Inhomogeneous Short Integer Solution (ISIS) problem. Several later works have used this framework for constructing new quantum algorithms in specific cases. However, the general relation between all these problems is still unknown. In this paper, we investigate the equivalence between S|LWE⟩ and ISIS. We present the first fully generic reduction from ISIS to S|LWE⟩, valid even in the presence of errors in the underlying algorithms. We then explore the reverse direction, introducing an inhomogeneous variant of C|LWE⟩, denoted IC|LWE⟩, and show that IC|LWE⟩ reduces to S|LWE⟩. Finally, we prove that, under certain recoverability conditions, an algorithm for ISIS can be transformed into one for S|LWE⟩. We instantiate this reverse reduction by tweaking a known algorithm for (I)SIS∞ in order to construct quantum algorithm for S|LWE⟩ when the alphabet size q is a small power of 2, recovering some results of Bai et al. [BJK + 25]. Our results thus clarify the landscape of reductions between S|LWE⟩ and ISIS, and we show both their strong connection as well as the remaining barriers for showing full equivalence.

•Oct 7, 2025•0 citations

Number-theoretic foundations of post-quantum cryptographic protocols

Osama Rawi, M. Thamizhsudar, N. Nivetha +4 more

Conventional cryptographic systems such as factorization and discrete logarithm problems are threatened by the quick development of quantum computing.This paper offers a thorough study of number-theoretic problems and structures underlying post-quantum cryptographic protocols based on modular arithmetic, algebraic structures, lattices and computational hardness assumptions.The research is based on the mathematical problems of Learning with Errors (LWE) and Short Integer Solution (SIS) which are used for secure quantum-resistant encryption, digital signature and key exchange mechanisms.In secure communication scenarios, a framework of structured protocol is analyzed, which combines lattice-based operations and modular polynomial transformations.Experimental comparisons show that these schemes are not only practically efficient in computation but also have a level of security greater than 95% @ E-mail:

Journal of Discrete Mathematical Sciences and Cryptography•Oct 31, 2026•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.
Chen, Liu, and Zhandry [CLZ22] introduced the problems S|LWE⟩ and C|LWE⟩ as quantum analogues of the Learning with Errors problem, designed to construct quantum algorithms for the Inhomogeneous Short Integer Solution (ISIS) problem. Several later works have used this framework for constructing new quantum algorithms in specific cases. However, the general relation between all these problems is still unknown. In this paper, we investigate the equivalence between S|LWE⟩ and ISIS. We present the first fully generic reduction from ISIS to S|LWE⟩, valid even in the presence of errors in the underlying algorithms. We then explore the reverse direction, introducing an inhomogeneous variant of C|LWE⟩, denoted IC|LWE⟩, and show that IC|LWE⟩ reduces to S|LWE⟩. Finally, we prove that, under certain recoverability conditions, an algorithm for ISIS can be transformed into one for S|LWE⟩. We instantiate this reverse reduction by tweaking a known algorithm for (I)SIS∞ in order to construct quantum algorithm for S|LWE⟩ when the alphabet size q is a small power of 2, recovering some results of Bai et al. [BJK + 25]. Our results thus clarify the landscape of reductions between S|LWE⟩ and ISIS, and we show both their strong connection as well as the remaining barriers for showing full equivalence.
Conventional cryptographic systems such as factorization and discrete logarithm problems are threatened by the quick development of quantum computing.This paper offers a thorough study of number-theoretic problems and structures underlying post-quantum cryptographic protocols based on modular arithmetic, algebraic structures, lattices and computational hardness assumptions.The research is based on the mathematical problems of Learning with Errors (LWE) and Short Integer Solution (SIS) which are used for secure quantum-resistant encryption, digital signature and key exchange mechanisms.In secure communication scenarios, a framework of structured protocol is analyzed, which combines lattice-based operations and modular polynomial transformations.Experimental comparisons show that these schemes are not only practically efficient in computation but also have a level of security greater than 95% @ E-mail: