Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications

San Ling*, Khoa Nguyen, Damien Stehlé, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

72 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationPublic-Key Cryptography, PKC 2013 - 16th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Pages107-124
Number of pages18
Volume7778 LNCS
ISBN (Print)9783642363610
DOIs
Publication statusPublished - 2013
Event16th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2013 - Nara, Japan
Duration: 26 Feb 20131 Mar 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7778 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other16th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2013
CountryJapan
CityNara
Period26/02/131/03/13

Fingerprint Dive into the research topics of 'Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications'. Together they form a unique fingerprint.

Cite this