Paper 2016/497

Secure Computation from Elastic Noisy Channels

Dakshita Khurana, Hemanta K. Maji, and Amit Sahai


Noisy channels enable unconditionally secure multi-party computation even against parties with unbounded computational power. But inaccurate noise estimation and adversarially determined channel characteristics render known protocols insecure. Such channels are known as unreliable noisy channels. A large body of work in the last three decades has attempted to construct secure multi-party computation from unreliable noisy channels, but this previous work has not been able to deal with most parameter settings. In this work, we study a form of unreliable noisy channels where the unreliability is one-sided, that we name elastic noisy channels: thus, in one form of elastic noisy channel, an adversarial receiver can increase the reception reliability unbeknown to the sender, but the sender cannot change the channel characteristic. Our work shows feasibility results for a large set of parameters for the elastic binary symmetric channel, significantly improving upon the best results obtainable using prior techniques. In a key departure from existing approaches, we use a more elemental correlated private randomness as an intermediate cryptographic primitive that exhibits only a rudimentary essence of oblivious transfer. Toward this direction, we introduce new information-theoretic techniques that are potentially applicable to other cryptographic settings involving unreliable noisy channels.

Note: This is the full version of the original publication.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
elastic noisy channelsunfair noisy channelssecure computationcompleteness
Contact author(s)
dakshita @ cs ucla edu
2016-05-22: received
Short URL
Creative Commons Attribution


      author = {Dakshita Khurana and Hemanta K.  Maji and Amit Sahai},
      title = {Secure Computation from Elastic Noisy Channels},
      howpublished = {Cryptology ePrint Archive, Paper 2016/497},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.