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

Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings

Vadim Lyubashevsky

Published Jan 1, 2016• 39 citations
Publisher
DOI
10.1007/978-3-662-53890-6_7

Related papers

Identification Scheme Based on the Hardness of Ideal Lattice Problems in all Rings.

Kaoru Takemure, Bagus Santoso

IEICE Technical Report; IEICE Tech. Rep.•Feb 28, 2019•0 citations

A lattice-based digital signature from the Ring-LWE

Yanfang Wu, Zheng Huang, Jie Zhang +1 more

We propose a variant version of ring learning with errors (R-LWE) assumption. Under the modified slightly assumption which is reducible to the worst-case problems on ideal lattice, we present a construction of digital signatures. So the scheme is provably secure based on the hardness of lattice problems (such as approximating the length of the shortest vector within a fixed poly(n) factor). Compared with some existing typical lattice-based signature schemes, the construction enjoys many advantages, including simple and efficient key generation algorithm, signing algorithm and verification algorithm to improve the efficiency of the scheme as well as to reduce the overhead. The sizes of the secret and public keys and the signature are almost linear O(n log n) (up to poly-logarithmic factors) in the dimension n of the lattice.

IEEE International Conference on Network Infrastructure and Digital Content (IC-NIDC)•Sep 1, 2012•8 citations

Lattice signatures using NTRU on the hardness of worst‐case ideal lattice problems

Dipayan Das, Vishal Saraswat, Kajla Basu

Recently, lattice signatures based on the Fiat‐Shamir framework have seen a lot of improvements which are efficient in practice. The security of these signature schemes depends mainly on the hardness of solving short integer solutions (SIS) and/or learning with errors problem in the random oracle model. The authors propose an alternative lattice‐based signature scheme on the Fiat‐Shamir framework over the ring . The key generation in the signature scheme is based on the combination of NTRU and Ring SIS like key generation. Both the signature and the verification are done efficiently by doing polynomial convolutions in the ring . The proposed signature scheme is provably secure based on the hardness of the Ring SIS problem in the random oracle model. The scheme is also efficient up to constant factors as the highly practical schemes which have provable secure instantiation.

IET Information Security•Jun 2, 2020•5 citations

Short Lattice-Based One-out-of-Many Proofs and Applications to Ring Signatures

Muhammed F. Esgin, Ron Steinfeld, Amin Sakzad +2 more

Lecture notes in computer science•Jan 1, 2019•75 citations

Quantum-Secure Primitives from Ideal Lattices: Beyond Factoring for Asymmetric Cryptography

Revista, Zen, MATH, 10

The advent of quantum computing poses a significant threat to the security foundations of current asymmetric cryptographic schemes, which primarily rely on the perceived difficulty of integer factorization and discrete logarithm problems. Shor's algorithm, in particular, demonstrates that a sufficiently powerful quantum computer could break these schemes efficiently, necessitating the development of quantum-resistant alternatives. This paper explores the construction of quantum-secure primitives utilizing ideal lattices, a specialized class of lattices that offer enhanced efficiency and structural advantages compared to general lattices. We delve into the theoretical underpinnings of ideal lattices, including the Ring Learning With Errors (Ring-LWE) problem and the NTRU problem, which are believed to be hard even for quantum computers. The paper reviews the evolution of lattice-based cryptography, analyzes the security reductions from worst-case lattice problems to average-case problem instances relevant for cryptographic constructions, and discusses the practical implications for key encapsulation mechanisms and digital signatures. We examine the current state of ideal lattice-based schemes, such as those standardized by NIST, and consider their performance characteristics, key sizes, and resistance to known attacks, including side-channel vulnerabilities. Our analysis highlights that ideal lattices provide a robust and efficient foundation for building the next generation of asymmetric cryptographic primitives, moving beyond the vulnerabilities inherent in factoring-based systems.

•Dec 3, 2025•0 citations

Improved lattice-based ring signature schemes from basis delegation

Wen Gao, Yupu Hu, Baocang Wang +1 more

中国邮电高校学报:英文版•Jun 1, 2016•4 citations
We propose a variant version of ring learning with errors (R-LWE) assumption. Under the modified slightly assumption which is reducible to the worst-case problems on ideal lattice, we present a construction of digital signatures. So the scheme is provably secure based on the hardness of lattice problems (such as approximating the length of the shortest vector within a fixed poly(n) factor). Compared with some existing typical lattice-based signature schemes, the construction enjoys many advantages, including simple and efficient key generation algorithm, signing algorithm and verification algorithm to improve the efficiency of the scheme as well as to reduce the overhead. The sizes of the secret and public keys and the signature are almost linear O(n log n) (up to poly-logarithmic factors) in the dimension n of the lattice.
Recently, lattice signatures based on the Fiat‐Shamir framework have seen a lot of improvements which are efficient in practice. The security of these signature schemes depends mainly on the hardness of solving short integer solutions (SIS) and/or learning with errors problem in the random oracle model. The authors propose an alternative lattice‐based signature scheme on the Fiat‐Shamir framework over the ring . The key generation in the signature scheme is based on the combination of NTRU and Ring SIS like key generation. Both the signature and the verification are done efficiently by doing polynomial convolutions in the ring . The proposed signature scheme is provably secure based on the hardness of the Ring SIS problem in the random oracle model. The scheme is also efficient up to constant factors as the highly practical schemes which have provable secure instantiation.
The advent of quantum computing poses a significant threat to the security foundations of current asymmetric cryptographic schemes, which primarily rely on the perceived difficulty of integer factorization and discrete logarithm problems. Shor's algorithm, in particular, demonstrates that a sufficiently powerful quantum computer could break these schemes efficiently, necessitating the development of quantum-resistant alternatives. This paper explores the construction of quantum-secure primitives utilizing ideal lattices, a specialized class of lattices that offer enhanced efficiency and structural advantages compared to general lattices. We delve into the theoretical underpinnings of ideal lattices, including the Ring Learning With Errors (Ring-LWE) problem and the NTRU problem, which are believed to be hard even for quantum computers. The paper reviews the evolution of lattice-based cryptography, analyzes the security reductions from worst-case lattice problems to average-case problem instances relevant for cryptographic constructions, and discusses the practical implications for key encapsulation mechanisms and digital signatures. We examine the current state of ideal lattice-based schemes, such as those standardized by NIST, and consider their performance characteristics, key sizes, and resistance to known attacks, including side-channel vulnerabilities. Our analysis highlights that ideal lattices provide a robust and efficient foundation for building the next generation of asymmetric cryptographic primitives, moving beyond the vulnerabilities inherent in factoring-based systems.