Secure Two-Party Computation over Unreliable Channels

Ran Gelles, Anat Paskin-Cherniavsky, Vassilis Zikas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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+κ) bits for κ a security parameter. This improves the state of the art (Ishai et al., CRYPTO’ 11) where the communication is O(s)+poly(κ⋅depth(s)) .
Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks
EditorsDario Catalano, Roberto De Prisco
Place of PublicationCham
PublisherSpringer International Publishing AG
Number of pages19
ISBN (Electronic)978-3-319-98113-0
ISBN (Print)978-3-319-98112-3
Publication statusPublished - 2018
Event11th Conference on Security and Cryptography for Networks - Amalfi, Italy
Duration: 5 Sept 20187 Sept 2018

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th Conference on Security and Cryptography for Networks
Abbreviated titleSCN 2018
Internet address


Dive into the research topics of 'Secure Two-Party Computation over Unreliable Channels'. Together they form a unique fingerprint.

Cite this