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

Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems

Akinori Kawachi, Keisuke Tanaka, Keita Xagawa

Published Jan 1, 2008• 217 citations
Publisher
DOI
10.1007/978-3-540-89255-7_23

Related papers

Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems

亮周 河内, Akinori Kawachi, KEISUKE TANAKA +2 more

•Dec 1, 2008•0 citations

Lattice-Based Identification Schemes Secure Under Active Attacks

Vadim Lyubashevsky

Springer eBooks•Feb 26, 2008•183 citations

Lattice-based Blind Signatures

Markus Rückert

Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.

Dagstuhl Seminar Proceedings•Jan 1, 2009•1 citation

Adaptively Secure Identity-Based Identification from Lattices without Random Oracles

Markus Rückert

Lecture notes in computer science•Jan 1, 2010•20 citations

Improved Zero-knowledge Proofs of Knowledge for the ISIS Problem, and Applications.

San Ling, Khoa Nguyen, Damien Stehlé +1 more

Abstract. In all existing efficient proofs of knowledge of a solution to the infinity norm Inhomogeneous Small Integer Solution (ISIS ∞ ) problem, the knowledge extractor outputs a solution vector that is only guaranteed to be Õ(n) times longer than the witness possessed by the prover. As a consequence, in many cryptographic schemes that use these proof systems as building blocks, there exists a gap between the hardness of solving the underlying ISIS ∞ problem and the hardness underlying the security reductions. In this paper, we generalize Stern’s protocol to obtain two statistical zero-knowledge proofs of knowledge for the ISIS ∞ problem that remove this gap. Our result yields the potential of relying on weaker security assumptions for various lattice-based cryptographic constructions. As applications of our proof system, we introduce a concurrently secure identity-based identification scheme based on the worst-case hardness of the SIVPÕ(n1.5) problem (in the ℓ2 norm) in general lattices in the random oracle model, and an efficient statistical zero-knowledge proof of plaintext knowledge with small constant gap factor for Regev’s encryption scheme.

•Jan 1, 2012•1 citation

Towards Compact Identity-Based Encryption on Ideal Lattices

Huiwen Jia, Yupu Hu, Chunming Tang +1 more

Lecture notes in computer science•Jan 1, 2024•7 citations
Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.
Abstract. In all existing efficient proofs of knowledge of a solution to the infinity norm Inhomogeneous Small Integer Solution (ISIS ∞ ) problem, the knowledge extractor outputs a solution vector that is only guaranteed to be Õ(n) times longer than the witness possessed by the prover. As a consequence, in many cryptographic schemes that use these proof systems as building blocks, there exists a gap between the hardness of solving the underlying ISIS ∞ problem and the hardness underlying the security reductions. In this paper, we generalize Stern’s protocol to obtain two statistical zero-knowledge proofs of knowledge for the ISIS ∞ problem that remove this gap. Our result yields the potential of relying on weaker security assumptions for various lattice-based cryptographic constructions. As applications of our proof system, we introduce a concurrently secure identity-based identification scheme based on the worst-case hardness of the SIVPÕ(n1.5) problem (in the ℓ2 norm) in general lattices in the random oracle model, and an efficient statistical zero-knowledge proof of plaintext knowledge with small constant gap factor for Regev’s encryption scheme.