Improved Zero-knowledge Proofs of Knowledge for the ISIS
Problem, and Applications
San Ling, Khoa Nguyen, Damien
Stehlé and Huaxiong Wang
Abstract: In all existing efficient proofs of knowledge of a solution
to the infinity norm Inhomogeneous Small Integer Solution ISIS-oo
problem, the knowledge extractor outputs a solution vector that is
only guaranteed to be softO(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-oo 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-oo 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_softO(n^{1.5}) problem (in the l2 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.
Download: pdf.
Homepage