2013 | OriginalPaper | Buchkapitel
Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications
verfasst von : San Ling, Khoa Nguyen, Damien Stehlé, Huaxiong Wang
Erschienen in: Public-Key Cryptography – PKC 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\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 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 of the
${\rm SIVP}_{{\widetilde{O}}(n^{1.5})}$
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.