Welcome to the resource topic for 2022/1457
Title:
Secure Non-Interactive Reducibility is Decidable
Authors: Kaartik Bhushan, Ankit Kumar Misra, Varun Narayanan, Manoj Prabhakaran
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.
ePrint: https://eprint.iacr.org/2022/1457
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .