International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Saumya Goyal , Stanford University
Varun Narayanan , Technion, Israel
Manoj Prabhakaran , Indian Institute of Technology, Bombay
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
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 $\Theta(\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 defined 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.
BibTeX
@inproceedings{tcc-2022-32561,
  title={Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions},
  publisher={Springer-Verlag},
  author={Saumya Goyal and Varun Narayanan and Manoj Prabhakaran},
  year=2022
}