Zero-Knowledge Proofs with Low Amortized Communication from Lattice Assumptions

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskningpeer review

We construct zero-knowledge proofs of plaintext knowledge (PoPK) and correct multiplication (PoPC) for the Regev encryption scheme with low amortized communication complexity. Previous constructions of both PoPK and PoPC had communication cost linear in the size of the public key (roughly quadratic in the lattice dimension, ignoring logarithmic factors). Furthermore, previous constructions of PoPK suffered from one of the following weaknesses: either the message and randomness space were restricted, or there was a super-polynomial gap between the size of the message and randomness that an honest prover chose and the size of which an accepting verifier would be convinced. The latter weakness was also present in the existent PoPC protocols.

In contrast, O(n) proofs (for lattice dimension n) in our PoPK and PoPC protocols have communication cost linear in the public key. Thus, we improve the amortized communication cost of each proof by a factor linear in the lattice dimension. Furthermore, we allow the message space to be ℤp and the randomness distribution to be the discrete Gaussian, both of which are natural choices for the Regev encryption scheme. Finally, in our schemes there is no gap between the size of the message and randomness that an honest prover chooses and the size of which an accepting verifier is convinced.

Our constructions use the “MPC-in-the-head” technique of Ishai et al. (STOC 2007). At the heart of our constructions is a protocol for proving that a value is bounded by some publicly known bound. This uses Lagrange’s Theorem that states that any positive integer can be expressed as the sum of four squares (an idea previously used by Boudot (EUROCRYPT 2000)), as well as techniques from Cramer and Damgård (CRYPTO 2009).
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind7485
Sider (fra-til)38-56
Antal sider19
ISSN0302-9743
DOI
StatusUdgivet - 2012
BegivenhedInternational Conference on Security and Cryptography for Networks - Amalfi, Italien
Varighed: 5 sep. 20127 sep. 2012
Konferencens nummer: 8

Konference

KonferenceInternational Conference on Security and Cryptography for Networks
Nummer8
LandItalien
ByAmalfi
Periode05/09/201207/09/2012

Se relationer på Aarhus Universitet Citationsformater

ID: 52186925