Paper 2021/190
Decidability of Secure Noninteractive Simulation of Doubly Symmetric Binary Source
Hamidreza Amini Khorasgani, 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 any loss of round and communication complexity is the following strategy. Parties, beginning with multiple samples from an arbitrary noise source, noninteractively, albeit securely, simulate the BSS samples. After that, they can use customdesigned efficient multiparty solutions using these BSS samples. Khorasgani, Maji, and Nguyen (EPRINT2020) introduce the notion of secure noninteractive simulation (SNIS) as a natural cryptographic extension of concepts like noninteractive simulation and noninteractive correlation distillation in theoretical computer science and information theory. In SNIS, the parties apply local reduction functions to their samples to produce samples of another distribution. This work studies the decidability problem of whether samples from the noise $(X,Y)$ can securely and noninteractively simulate BSS samples. As is standard in analyzing noninteractive simulations, our work relies on Fourieranalytic techniques to approach this decidability problem. Our work begins by algebraizing the simulationbased security definition of SNIS. Using this algebraized definition of security, we analyze the properties of the Fourier spectrum of the reduction functions. Given $(X,Y)$ and BSS with noise parameter $\epsilon$, the 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 is a bounded computable time algorithm achieving this objective for the following cases. (1) $\delta=O{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 $\{1,1\}\times\{1,1\}$. Furthermore, given $(X,Y)$, we provide a sufficient test determining if simulating BSS samples incurs a constantinsecurity, irrespective of the number of samples of $(X,Y)$. Handling the security of the reductions in Fourier analysis presents unique challenges because the interaction of these analytical techniques with security is unexplored. Our technical approach diverges significantly from existing approaches to the decidability problem of (insecure) noninteractive reductions to develop analysis pathways that preserve security. Consequently, our work shows a new concentration of the Fourier spectrum of secure reduction functions, unlike their insecure counterparts. We show that nearly the entire weight of secure reduction functions' spectrum is concentrated on the lowerdegree components. The authors believe that examining existing analytical techniques through the facet of security and developing new analysis methodologies respecting security is of independent and broader interest.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Secure noninteractive simulationDoubly symmetric binary sourceBinary symmetric sourceDecidability characterizationBiased discrete Fourier analysisEfronStein decompositionJunta theoremDimension reductionMarkov operator
 Contact author(s)

haminikh @ purdue edu
hmaji @ purdue edu
nguye245 @ purdue edu  History
 20210614: revised
 20210224: received
 See all versions
 Short URL
 https://ia.cr/2021/190
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/190, author = {Hamidreza Amini Khorasgani and Hemanta K. Maji and Hai H. Nguyen}, title = {Decidability of Secure Noninteractive Simulation of Doubly Symmetric Binary Source}, howpublished = {Cryptology ePrint Archive, Paper 2021/190}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/190}}, url = {https://eprint.iacr.org/2021/190} }