Paper 2021/1503

Interaction-Preserving Compilers for Secure Computation

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


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) $\Gamma$ bits in $N$ rounds, is it possible to design a secure protocol with communication complexity close to $\Gamma$ 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 $\Gamma$ 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ITCS 2022
Multiparty ComputationCommunication ComplexityFully Homomorphic Encryption
Contact author(s)
nico doettling @ gmail com
vipul @ cmu edu
giulio malavolta @ hotmail it
jraizes @ andrew cmu edu
2021-11-15: received
Short URL
Creative Commons Attribution


      author = {Nico Döttling and Vipul Goyal and Giulio Malavolta and Justin Raizes},
      title = {Interaction-Preserving Compilers for Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1503},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.