CryptoDB
Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions
| Authors: |
|
|---|---|
| Download: | |
| 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
}