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

Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge

Keita Xagawa, Keisuke Tanaka

Published Jan 1, 2009• 13 citations
Publisher
DOI
10.1007/978-3-642-04642-1_17

Related papers

Efficient and Non-malleable Proofs of Plaintext Knowledge and Applications

Jonathan I. Katz

Lecture notes in computer science•Jan 1, 2003•41 citations

Efficient and Non-malleable Proofs of Plaintext Knowledge and Applications (Extended Abstract)

Jonathan I. Katz

•Jan 1, 2003•1 citation

Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem

Shafi Goldwasser, Dmitriy Kharchenko

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

Leakage-Resilient Identification Schemes from Zero-Knowledge Proofs of Storage

Giuseppe Ateniese, Antonio Faonio, Seny Kamara

Lecture notes in computer science•Jan 1, 2015•11 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

Strengthening Zero-Knowledge Protocols Using Signatures

Juan A. Garay, PHILIP D. MACKENZIE, Ke Yang

Lecture notes in computer science•Jan 1, 2003•76 citations
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.