Paper 2022/262
Secure Non-Interactive Reduction and Spectral Analysis of Correlations
Pratyush Agarwal, Varun Narayanan, Shreya Pathak, Manoj Prabhakaran, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Information-theoretic securityMathematical aspects of cryptographySecure multiparty computationcryptographic complexity.
- Contact author(s)
-
varunnkv @ gmail com
vinodmp @ tifr res in
pratyush @ cse iitb ac in
shreyapathak @ cse iitb ac in
mp @ cse iitb ac in
alirehan @ cse iitb ac in - History
- 2022-03-02: received
- Short URL
- https://ia.cr/2022/262
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/262,
author = {Pratyush Agarwal and Varun Narayanan and Shreya Pathak and Manoj Prabhakaran and Vinod M. Prabhakaran and Mohammad Ali Rehan},
title = {Secure Non-Interactive Reduction and Spectral Analysis of Correlations},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/262},
year = {2022},
url = {https://eprint.iacr.org/2022/262}
}