Paper 2020/1341
Zero-Communication Reductions
Varun Narayanan, Manoj Prabhakaran, and Vinod M. Prabhakaran
Abstract
We introduce a new primitive in information-theoretic cryptography, namely zero-communication reductions (ZCR), with different levels of security. We relate ZCR to several other important primitives, and obtain new results on upper and lower bounds. In particular, we obtain new upper bounds for PSM, CDS and OT complexity of functions, which are exponential in the information complexity of the functions. These upper bounds complement the results of Beimel et al. (2014) which broke the circuit-complexity barrier for ``high complexity'' functions; our results break the barrier of input size for ``low complexity'' functions. We also show that lower bounds on secure ZCR can be used to establish lower bounds for OT-complexity. We recover the known (linear) lower bounds on OT-complexity by Beimal and Malkin (2004) via this new route. We also formulate the lower bound problem for secure ZCR in purely linear-algebraic terms, by defining the invertible rank of a matrix. We present an Invertible Rank Conjecture, proving which will establish super-linear lower bounds for OT-complexity (and if accompanied by an explicit construction, will provide explicit functions with super-linear circuit lower bounds).
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. TCC 2020
- Keywords
- secure multiparty computationOT complexityPSMCDSzero-communication protocolsoblivious transferzero-communicationinvertible rankMPC lower bounds
- Contact author(s)
-
varun narayanan @ tifr res in
vinodmp @ tifr res in
mp @ cse iitb ac in - History
- 2020-11-13: revised
- 2020-10-26: received
- See all versions
- Short URL
- https://ia.cr/2020/1341
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1341,
author = {Varun Narayanan and Manoj Prabhakaran and Vinod M. Prabhakaran},
title = {Zero-Communication Reductions},
howpublished = {Cryptology ePrint Archive, Paper 2020/1341},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1341}},
url = {https://eprint.iacr.org/2020/1341}
}
