License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.57
URN: urn:nbn:de:0030-drops-156534
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15653/
Go to the corresponding LIPIcs Volume Portal

Döttling, Nico ; Goyal, Vipul ; Malavolta, Giulio ; Raizes, Justin

Interaction-Preserving Compilers for Secure Computation

pdf-format:
LIPIcs-ITCS-2022-57.pdf (0.7 MB)

Abstract

In this work we consider the following question: What is the cost of security for multi-party protocols? Specifically, given an insecure protocol where parties exchange (in the worst case) Γ bits in N rounds, is it possible to design a secure protocol with communication complexity close to Γ and N rounds? We systematically study this problem in a variety of settings and we propose solutions based on the intractability of different cryptographic problems.
For the case of two parties we design an interaction-preserving compiler where the number of bits exchanged in the secure protocol approaches Γ and the number of rounds is exactly N, assuming the hardness of standard problems over lattices. For the more general multi-party case, we obtain the same result assuming either (i) an additional round of interaction or (ii) the existence of extractable witness encryption and succinct non-interactive arguments of knowledge. As a contribution of independent interest, we construct the first multi-key fully homomorphic encryption scheme with message-to-ciphertext ratio (i.e., rate) of 1 - o(1), assuming the hardness of the learning with errors (LWE) problem.
We view our work as a support for the claim that, as far as interaction and communication are concerned, one does not need to pay a significant price for security in multi-party protocols.

BibTeX - Entry

@InProceedings{dottling_et_al:LIPIcs.ITCS.2022.57,
  author =	{D\"{o}ttling, Nico and Goyal, Vipul and Malavolta, Giulio and Raizes, Justin},
  title =	{{Interaction-Preserving Compilers for Secure Computation}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15653},
  URN =		{urn:nbn:de:0030-drops-156534},
  doi =		{10.4230/LIPIcs.ITCS.2022.57},
  annote =	{Keywords: Multiparty Computation, Communication Complexity, Fully Homomorphic Encryption}
}

Keywords: Multiparty Computation, Communication Complexity, Fully Homomorphic Encryption
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI