Paper 2022/1539 Original: eprint.iacr.org/2022/1539 ↗
Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions
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
- Preprint.
- History
- 2025-11-06: last updated
- 2022-11-07: published
- Short URL
- https://ia.cr/2022/1539
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2022/1539}
}