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 -