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

Saumya Goyal; Varun Narayanan; Manoj Prabhakaran

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in TCC 2022
Keywords: 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
History: 2022-11-07: approved; 2022-11-07: received; See all versions
Short URL: https://ia.cr/2022/1539
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1539,
      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{https://eprint.iacr.org/2022/1539}},
      url = {https://eprint.iacr.org/2022/1539}
}