Constant-rate oblivious transfer from noisy channels

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, Jürg Wullschleger

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


A binary symmetric channel (BSC) is a noisy communication channel that flips each bit independently with some fixed error probability 0 < p < 1/2. Crépeau and Kilian (FOCS 1988) showed that oblivious transfer, and hence general secure two-party computation, can be unconditionally realized by communicating over a BSC. There has been a long line of works on improving the efficiency and generality of this construction. However, all known constructions that achieve security against malicious parties require the parties to communicate poly(k) bits over the channel for each instance of oblivious transfer (more precisely, -bit-OT) being realized, where k is a statistical security parameter. The question of achieving a constant (positive) rate was left open, even in the easier case of realizing a single oblivious transfer of a long string. We settle this question in the affirmative by showing how to realize n independent instances of oblivious transfer, with statistical error that vanishes with n, by communicating just O(n) bits over a BSC. As a corollary, any boolean circuit of size s can be securely evaluated by two parties with O(s)+poly(k) bits of communication over a BSC, improving over the O(s)·poly(k) complexity of previous constructions.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings
Number of pages18
ISBN (Print)9783642227912
StatePublished - 2011
Externally publishedYes
Event31st Annual International Cryptology Conference, CRYPTO 2011 - Santa Barbara, CA, United States
Duration: Aug 14 2011Aug 18 2011

Publication series

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


Other31st Annual International Cryptology Conference, CRYPTO 2011
Country/TerritoryUnited States
CitySanta Barbara, CA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Constant-rate oblivious transfer from noisy channels'. Together they form a unique fingerprint.

Cite this