TY - GEN
T1 - Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications
AU - Ling, San
AU - Nguyen, Khoa
AU - Stehlé, Damien
AU - Wang, Huaxiong
PY - 2013
Y1 - 2013
N2 - 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 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 SIVP Õ(n1.5) of the 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.
AB - 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 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 SIVP Õ(n1.5) of the 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.
UR - http://www.scopus.com/inward/record.url?scp=84873972951&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36362-7_8
DO - 10.1007/978-3-642-36362-7_8
M3 - Conference proceeding contribution
AN - SCOPUS:84873972951
SN - 9783642363610
VL - 7778 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 107
EP - 124
BT - Public-Key Cryptography, PKC 2013 - 16th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
PB - Springer, Springer Nature
CY - Heidelberg
T2 - 16th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2013
Y2 - 26 February 2013 through 1 March 2013
ER -