Welcome to the resource topic for 2012/569
Title:
Improved Zero-knowledge Proofs of Knowledge for the ISIS Problem, and Applications
Authors: San Ling, Khoa Nguyen, Damien Stehle, Huaxiong Wang
Abstract:In all existing efficient proofs of knowledge of a solution to the infinity norm Inhomogeneous Small Integer Solution (\mathrm{ISIS}^{\infty}) problem, the knowledge extractor outputs a solution vector that is only guaranteed to be~\widetilde{O}(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 \mathrm{ISIS}^{\infty} 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 \mathrm{ISIS}^{\infty} 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 \mathrm{SIVP}_{\widetilde{O}(n^{1.5})} problem (in the \ell_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.
ePrint: https://eprint.iacr.org/2012/569
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .