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 security parameter. Furthermore, we allow the message space to be \Z_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 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).Category / Keywords: cryptographic protocols / Publication Info: SCN 2012 Date: received 27 Jun 2012 Contact author: lopez at cs nyu edu Available format(s): PDF | BibTeX Citation Version: 20120629:144253 (All versions of this report) Discussion forum: Show discussion | Start new discussion