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

San Ling, Khoa Nguyen, Damien Stehle, and 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.

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2013
Keywords
Lattice-based cryptographyzero knowledge proofproof of plaintext knowledgeISIS problemID-based identification
Contact author(s)
khoantt @ ntu edu sg
History
2014-01-12: last of 5 revisions
See all versions
Short URL
https://ia.cr/2012/569

CC BY

BibTeX

@misc{cryptoeprint:2012/569,
author = {San Ling and Khoa Nguyen and Damien Stehle and Huaxiong Wang},
title = {Improved Zero-knowledge Proofs of Knowledge for the ISIS Problem, and Applications},
howpublished = {Cryptology ePrint Archive, Paper 2012/569},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/569}},
url = {https://eprint.iacr.org/2012/569}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.