Cryptology ePrint Archive: Report 2018/506

Secure Two-Party Computation over Unreliable Channels

Ran Gelles and 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))$.

Category / Keywords: cryptographic protocols / Secure multiparty computation, Unreliable Channels, Error-Correction, Interactive coding

Date: received 24 May 2018

Contact author: ran gelles at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20180526:142356 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]