Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-review

- Ivan Bjerre Damgård
- Adriana López-Alt, New York University, United States

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).

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).

Original language | English |
---|---|

Book series | Lecture Notes in Computer Science |

Volume | 7485 |

Pages (from-to) | 38-56 |

Number of pages | 19 |

ISSN | 0302-9743 |

DOIs | |

Publication status | Published - 2012 |

Event | International Conference on Security and Cryptography for Networks - Amalfi, Italy Duration: 5 Sep 2012 → 7 Sep 2012 Conference number: 8 |

Conference | International Conference on Security and Cryptography for Networks |
---|---|

Number | 8 |

Country | Italy |

City | Amalfi |

Period | 05/09/2012 → 07/09/2012 |

Title of the vol.: Security and Cryptography for Networks : 8th International Conference, SCN 2012, Amalfi, Italy, September 5-7, 2012. Proceedings /eds.: Ivan Visconti, Roberto De Prisco.

ISBN: 978-3-642-32927-2, 978-3-642-32928-9

See relations at Aarhus University Citationformats

ID: 52186925