Paper 2022/1457

Secure Non-Interactive Reducibility is Decidable

Kaartik Bhushan, Indian Institute of Technology Bombay
Ankit Kumar Misra, Indian Institute of Technology Bombay
Varun Narayanan, Technion – Israel Institute of Technology
Manoj Prabhakaran, Indian Institute of Technology Bombay

Secure Non-Interactive Reductions (SNIR) is a recently introduced, but fundamental cryptographic primitive. The basic question about SNIRs is how to determine if there is an SNIR from one 2-party correlation to another. While prior work provided answers for several pairs of correlations, the possibility that this is an undecidable problem in general was left open. In this work we show that the existence of an SNIR between any pair of correlations can be determined by an algorithm. At a high-level, our proof follows the blueprint of a similar (but restricted) result by Khorasgani et al. But combining the spectral analysis of SNIRs by Agrawal et al. (Eurocrypt 2022) with a new variant of a "junta theorem" by Kindler and Safra, we obtain a complete resolution of the decidability question for SNIRs. The new junta theorem that we identify and prove may be of independent interest.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2022
Secure Reductions Fourier Analysis Decidability Cryptographic Complexity Junta Theorem
Contact author(s)
kbhushan @ cse iitb ac in
190050020 @ iitb ac in
varunnkv @ gmail com
mp @ cse iitb ac in
2022-10-25: approved
2022-10-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kaartik Bhushan and Ankit Kumar Misra and Varun Narayanan and Manoj Prabhakaran},
      title = {Secure Non-Interactive Reducibility is Decidable},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1457},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.