Paper 2022/1539

Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions

Saumya Goyal, Stanford University
Varun Narayanan, Technion – Israel Institute of Technology
Manoj Prabhakaran, Indian Institute of Technology Bombay

In p-noisy coin-tossing, Alice and Bob obtain fair coins which are of opposite values with probability p. Its Oblivious-Transfer (OT) complexity refers to the least number of OTs required by a semi-honest perfectly secure 2-party protocol for this task. We show a tight bound of Θ(log 1/p) for the OT complexity of p-noisy coin-tossing. This is the first instance of a lower bound for OT complexity that is independent of the input/output length of the function. We obtain our result by providing a general connection between the OT complexity of randomized functions and the complexity of Secure Zero Communication Reductions (SZCR), as recently de- fined by Narayanan et al. (TCC 2020), and then showing a lower bound for the complexity of an SZCR from noisy coin-tossing to (a predicate corresponding to) OT.

Available format(s)
Publication info
Published by the IACR in TCC 2022
Oblivious Transfer Complexity randomized functionality noisy coin-tossing secure zero-communication reduction
Contact author(s)
saumyagoyal01 @ gmail com
varunnkv @ gmail com
mp @ cse iitb ac in
2022-11-07: approved
2022-11-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saumya Goyal and Varun Narayanan and Manoj Prabhakaran},
      title = {Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1539},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.