Paper 2021/1503
Interaction-Preserving Compilers for Secure Computation
Nico Döttling, Vipul Goyal, Giulio Malavolta, and Justin Raizes
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) $\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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ITCS 2022
- Keywords
- Multiparty ComputationCommunication ComplexityFully Homomorphic Encryption
- Contact author(s)
-
nico doettling @ gmail com
vipul @ cmu edu
giulio malavolta @ hotmail it
jraizes @ andrew cmu edu - History
- 2021-11-15: received
- Short URL
- https://ia.cr/2021/1503
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1503, 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}, url = {https://eprint.iacr.org/2021/1503} }