## 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 Search ePrint Search Google Slides TCC 2022 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
}