Secure computation from elastic noisy channels

Dakshita Khurana, Hemanta K. Maji, Amit Sahai

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


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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsJean-Sebastien Coron, Marc Fischlin
Number of pages29
ISBN (Print)9783662498958
StatePublished - 2016
Externally publishedYes
Event35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 - Vienna, Austria
Duration: May 8 2016May 12 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016


  • Elastic noisy channel
  • Information-theoretic security
  • Noisy channel
  • Oblivious transfer
  • Secure computation
  • Unfair noisy channel

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Secure computation from elastic noisy channels'. Together they form a unique fingerprint.

Cite this