Cryptology ePrint Archive: Report 2022/262

Secure Non-Interactive Reduction and Spectral Analysis of Correlations

Pratyush Agarwal and Varun Narayanan and Shreya Pathak and Manoj Prabhakaran and Vinod M. Prabhakaran and Mohammad Ali Rehan

Abstract: Correlated pairs of random variables are a central concept in information-theoretically secure cryptography. Secure reductions between different correlations have been studied, and completeness results are known. Further, the complexity of such reductions is intimately connected with circuit complexity and efficiency of locally decodable codes. As such, making progress on these complexity questions faces strong barriers. Motivated by this, in this work, we study a restricted form of secure reductions --- namely, Secure Non-Interactive Reductions (SNIR) --- which is still closely related to the original problem, and establish several fundamental results and relevant techniques for it.

We uncover striking connections between SNIR and linear algebraic properties of correlations. Specifically, we define the spectrum of a correlation, and show that a target correlation has a SNIR to a source correlation only if the spectrum of the latter contains the entire spectrum of the former. We also establish a ``mirroring lemma'' that shows an unexpected symmetry between the two parties in a SNIR, when viewed through the lens of spectral analysis. We also use cryptographic insights and elementary linear algebraic analysis to fully characterize the role of common randomness as well as local randomness in SNIRs. We employ these results to resolve several fundamental questions about SNIRs, and to define future directions.

Category / Keywords: foundations / Information-theoretic security, Mathematical aspects of cryptography, Secure multiparty computation, cryptographic complexity.

Date: received 26 Feb 2022, last revised 27 Feb 2022

Contact author: varunnkv at gmail com, vinodmp at tifr res in, pratyush at cse iitb ac in, shreyapathak at cse iitb ac in, mp at cse iitb ac in, alirehan at cse iitb ac in

Available format(s): PDF | BibTeX Citation

Version: 20220302:141139 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]