Paper 2018/506

Secure Two-Party Computation over Unreliable Channels

Ran Gelles, Anat Paskin-Cherniavsky, and Vassilis Zikas

Abstract

We consider information-theoretic secure two-party computation in the plain model where no reliable channels are assumed, and all communication is performed over the binary symmetric channel (BSC) that flips each bit with fixed probability. In this reality-driven setting we investigate feasibility of communication-optimal noise-resilient semi-honest two-party computation i.e., efficient computation which is both private and correct despite channel noise. We devise an information-theoretic technique that converts any correct, but not necessarily private, two-party protocol that assumes reliable channels, into a protocol which is both correct and private against semi-honest adversaries, assuming BSC channels alone. Our results also apply to other types of noisy-channels such as the elastic-channel. Our construction combines tools from the cryptographic literature with tools from the literature on interactive coding, and achieves, to our knowledge, the best known communication overhead. Specifically, if $f$ is given as a circuit of size $s$, our scheme communicates $O(s + \kappa)$ bits for $\kappa$ a security parameter. This improves the state of the art (Ishai et al., CRYPTO' 11) where the communication is $O(s) + \text{poly}(\kappa \cdot \text{depth}(s))$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Secure multiparty computationUnreliable ChannelsError-CorrectionInteractive coding
Contact author(s)
ran gelles @ biu ac il
History
2018-05-26: received
Short URL
https://ia.cr/2018/506
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/506,
      author = {Ran Gelles and Anat Paskin-Cherniavsky and Vassilis Zikas},
      title = {Secure Two-Party Computation over Unreliable Channels},
      howpublished = {Cryptology ePrint Archive, Paper 2018/506},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/506}},
      url = {https://eprint.iacr.org/2018/506}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.