Cryptology ePrint Archive: Report 2020/1341

Zero-Communication Reductions

Varun Narayanan and 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).

Category / Keywords: foundations / secure multiparty computation, OT complexity, PSM, CDS, zero-communication protocols, oblivious transfer, zero-communication, invertible rank, MPC lower bounds

Original Publication (with minor differences): TCC 2020

Date: received 25 Oct 2020, last revised 13 Nov 2020

Contact author: varun narayanan at tifr res in,vinodmp@tifr res in,mp@cse iitb ac in

Available format(s): PDF | BibTeX Citation

Version: 20201113:172218 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]