International Association for Cryptologic Research

International Association
for Cryptologic Research

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
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
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.
Video from EUROCRYPT 2022
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
}