Paper 2021/190

Decidability of Secure Non-interactive Simulation of Doubly Symmetric Binary Source

Hamidreza Amini Khorasgani and Hemanta K. Maji and Hai H. Nguyen

Abstract

Noise, which cannot be eliminated or controlled by parties, is an incredible facilitator of cryptography. For example, highly efficient secure computation protocols based on independent samples from the doubly symmetric binary source (BSS) are known. A modular technique of extending these protocols to diverse forms of other noise without incurring any loss of round and communication complexity is the following strategy. Parties, beginning with multiple samples from an arbitrary noise source, non-interactively, albeit, securely, simulate the BSS samples. After that, they can use custom-designed efficient multi-party solutions for BSS. Khorasgani, Maji, and Nguyen (EPRINT--2020) introduce the notion of secure non-interactive simulation (SNIS) as a natural cryptographic extension of concepts like non-interactive simulation and non-interactive correlation distillation in theoretical computer science and information theory. In SNIS, the parties apply local reduction functions to their samples to produce the samples of another distribution. This work studies the decidability problem of whether a sample from the noise $(X,Y)$ can securely and non-interactively simulate BSS samples. As is standard in analyzing non-interactive simulations, our work relies on Fourier analytic techniques to approach this decidability problem. Our work begins by algebraizing the simulation-based security definition of SNIS. Then, using this algebraized definition of security, we analyze the properties of the Fourier spectrum of the reduction functions. Given $(X,Y)$ and BSS with parameter $\epsilon$, our objective is to distinguish between the following two cases. (A) Does there exist a SNIS from BSS$(\epsilon)$ to $(X,Y)$ with $\delta$-insecurity? (B) Do all SNIS from BSS$(\epsilon)$ to $(X,Y)$ incur $\delta'$-insecurity, where $\delta'>\delta$? We prove that there exists a bounded computable time algorithm achieving this objective for the following cases. (1) $\delta=\bigO{1/n}$ and $\delta'=$ positive constant, and (2) $\delta=$ positive constant, and $\delta'=$ another (larger) positive constant. We also prove that $\delta=0$ is achievable only when $(X,Y)$ is another BSS, where $(X,Y)$ is an arbitrary distribution over $\minusoo\times\minusoo$. Furthermore, given $(X,Y)$, we provide a sufficient test determining if simulating BSS samples incurs a constant-insecurity, irrespective of the number of samples of $(X,Y)$. Technically, our work proceeds by demonstrating that the weight of the Fourier spectrum of the reduction functions is at most $\bigO{\delta}$ on higher-order components, where $\delta$ is the insecurity of the SNIS.