Paper 2022/1457
Secure Non-Interactive Reducibility is Decidable
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2022
- Keywords
- 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 - History
- 2022-10-25: approved
- 2022-10-25: received
- See all versions
- Short URL
- https://ia.cr/2022/1457
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1457,
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{https://eprint.iacr.org/2022/1457}},
url = {https://eprint.iacr.org/2022/1457}
}
