Paper 2020/252

Secure Non-interactive Simulation: Feasibility & Rate

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

Abstract

A natural solution to increase the efficiency of secure computation will be to non-interactively and securely transform diverse inexpensive-to-generate correlated randomness, like, joint samples from noise sources, into correlations useful for the secure computation while incurring low computational overhead. Motivated by this general application for secure computation, our work introduces the notion of \textit{secure non-interactive simulation} (SNIS). Parties receive samples of correlated randomness, and they, without any interaction, securely convert them into samples from another correlated randomness. SNIS is an extension of \textit{non-interactive simulation of joint distributions} (NIS), and \textit{non-interactive correlation distillation} (NICD) to the cryptographic context. It is a non-interactive version of \textit{one-way secure computation} (OWSC). Our work presents a simulation-based security definition for SNIS and initiates the study of the feasibility and efficiency of SNIS. We also study SNIS among fundamental correlated randomnesses like random samples from the binary symmetric and binary erasure channels, represented by BSS and BES, respectively. The impossibility of realizing a BES sample from BSS samples in NIS and OWSC extends to SNIS. Additionally, we prove that a SNIS of BSS sample from BES samples is impossible, which remains an open problem in NIS and OWSC. Next, we prove that a SNIS of a BES$(\varepsilon')$ sample (a BES with noise characteristic $\varepsilon'$) from BES$(\varepsilon)$ is feasible if and only if $(1-\varepsilon')=(1-\varepsilon)^k$, for some $k\in N$. In this context, we prove that all SNIS constructions must be linear. Furthermore, if $(1-\varepsilon') = (1-\varepsilon)^k$, then the rate of simulating multiple independent BES$(\varepsilon')$ samples is at most $1/k$, which is also achievable using (block) linear constructions. Finally, we show that a SNIS of a BSS$(\varepsilon')$ sample from BSS$(\varepsilon)$ samples is feasible if and only if $(1-2\varepsilon')=(1-2\varepsilon)^k$, for some $k\in N$. Interestingly, there are linear as well as non-linear SNIS constructions. When $(1-2\varepsilon')=(1-2\varepsilon)^k$, we prove that the rate of a \textit{perfectly secure} SNIS is at most $1/k$, which is achievable using linear and non-linear constructions. Our results leave open the fascinating problem of determining the rate of \textit{statistically secure} SNIS among BSS samples. Our technical approach algebraizes the definition of SNIS and proceeds via Fourier analysis. Our work develops general analysis methodologies for Boolean functions, explicitly incorporating cryptographic security constraints. Our work also proves strong forms of \textit{statistical-to-perfect security} transformations: one can error-correct a statistically secure SNIS to make it perfectly secure. We show a connection of our research with \textit{homogeneous Boolean functions} and \textit{distance-invariant codes}, which may be of independent interest.