Cryptology ePrint Archive: Report 2016/497

Secure Computation from Elastic Noisy Channels

Dakshita Khurana and Hemanta K. Maji and Amit Sahai

Abstract: 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.

Category / Keywords: foundations / elastic noisy channels, unfair noisy channels, secure computation, completeness

Original Publication (with major differences): IACR-EUROCRYPT-2016

Date: received 21 May 2016

Contact author: dakshita at cs ucla edu

Available format(s): PDF | BibTeX Citation

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

Version: 20160522:162812 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]