## CryptoDB

### Paper: Secure Non-Interactive Reduction and Spectral Analysis of Correlations

Authors: Pratyush Agarwal , Indian Institute of Technology, Bombay Varun Narayanan , Technion, Israel Shreya Pathak , Indian Institute of Technology, Bombay Manoj Prabhakaran , Indian Institute of Technology, Bombay Vinod M. Prabhakaran , Tata Institute of Fundamental Research, Mumbai Mohammad Ali Rehan , Indian Institute of Technology, Bombay Search ePrint Search Google Slides EUROCRYPT 2022 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.
##### BibTeX
@inproceedings{eurocrypt-2022-31859,
title={Secure Non-Interactive Reduction and Spectral Analysis of Correlations},
publisher={Springer-Verlag},
author={Pratyush Agarwal and Varun Narayanan and Shreya Pathak and Manoj Prabhakaran and Vinod M. Prabhakaran and Mohammad Ali Rehan},
year=2022
}
`