International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Secure Non-Interactive Reducibility is Decidable

Kaartik Bhushan , IIT Bombay
Ankit Kumar Misra , IIT Bombay
Varun Narayanan , Technion Haifa
Manoj Prabhakaran , IIT Bombay
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
Abstract: Secure Non-Interactive Reductions (SNIR) is a recently introduced, but fundamental cryp- tographic primitive. The basic question about SNIRs is how to determine if there is a 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 a 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.
  title={Secure Non-Interactive Reducibility is Decidable},
  author={Kaartik Bhushan and Ankit Kumar Misra and Varun Narayanan and Manoj Prabhakaran},