2026-07-23T05:17:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15653 2024-03-06T10:55:52Z ddc:004 open_access

Interaction-Preserving Compilers for Secure Computation Döttling, Nico Goyal, Vipul Malavolta, Giulio Raizes, Justin Multiparty Computation Communication Complexity Fully Homomorphic Encryption 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nico Döttling and Vipul Goyal and Giulio Malavolta and Justin Raizes 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.57 urn:nbn:de:0030-drops-156534 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.57 eng https://creativecommons.org/licenses/by/4.0/legalcode