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.#R##N##R##N#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.#R##N##R##N#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.
['Dakshita Khurana', 'Hemanta K. Maji', 'Amit Sahai']
Secure Computation from Elastic Noisy Channels