Paper 2020/252

Secure Non-interactive Simulation: Feasibility & Rate

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

Abstract

General secure computation is a powerful cryptographic primitive that allows mutually distrusting parties to compute securely over their private data. Random samples from noisy channels, like, binary erasure and binary symmetric channel, enable general secure computations using interactive protocols. A key research objective is to realize these constructions as efficiently as possible. For example, to realize a secure computation task, one strives to use the minimum number of samples of these noisy channels. Additionally, reducing the round and communication complexity of these interactive protocols is a well-established objective to minimize the impact of network latency. Even for elementary secure computation tasks, like converting one form of noisy channel samples into samples from another noisy channel, the precise characterization of achievable efficiency objectives mentioned above is not well-understood. Towards this endeavor of understanding the limits of secure computation under limited interaction, this work introduces the concept of secure non-interactive simulation of joint distributions (SNIS), which reduces the round and communication complexity of secure computation protocols to the absolute minimum, and studies feasibility and rate characterization. In this setting, two parties begin with multiple independent samples from a correlated randomness source. This setup is akin to the preprocessing step of the offline-online paradigm of secure computation using sources of noise, which enables general secure computation even against parties with unbounded computational power. The objective of the parties is to non-interactively simulate samples of another joint distribution without any further communication. A non-interactive simulation is secure if a party's output samples are roughly as informative about the other party's output samples as its input samples. We define this security notion using standard simulation-based security. The fundamental research problem is to characterize the feasibility and the achievable rate of SNIS. One may interpret SNIS as imbuing the notion of non-interactive simulation of joint distributions (NIS) in information theory, which initiated from the seminal works of G'acs and K"orner (1972), and Wyner (1975), with cryptographic security. In particular, SNIS is strictly stronger than merely a secure version of non-interactive correlation distillation, as introduced by Mossel, O’Donnell, Regev, Steif, and Sudakov (2004) because secure private keys alone do not suffice to facilitate general secure computation. Alternatively, SNIS is a natural strengthening of one-way secure computation (OWSC) introduced by Garg, Ishai, Kushilevitz, Ostrovsky, and Sahai (2015). Our notion of SNIS also serves as the base case for inductively building cryptographic primitives with minimum communication complexity. In this work, we study samples from the following two families of joint distributions. (1) $\BSC(\eps)$: A joint distribution $(X,Y)$, where $X$ is a uniform random bit and $Y$ is a correlated bit such that $X\neq Y$ with probability $\eps\in(0,1/2)$, and (2) $\BEC(\eps)$ (\aka, (randomized) Rabin OT samples): A joint distribution $(X,Y)$, where $X$ is a uniform random bit, and $Y=X$ with probability $(1-\eps)$; otherwise $Y=\perp$, where $\eps\in(0,1)$. These joint distributions are some of the most fundamental distributions that enable general secure computation at a constant rate using interactive protocols. However, even for these fundamental cryptographic resources, characterization of the optimal rate of enabling general secure computation is relatively not well explored. Our work completely resolves the feasibility and rate of SNIS between these families of joint distributions. Note that the reverse hypercontractivity and OWSC already rule out the possibility of realizing any $\BEC$ sample from $\BSC$ samples. This impossibility transfers to SNIS as well because it is a strictly stronger primitive. Furthermore, we prove the impossibility of a SNIS realization of any BSS sample from any BES samples. We highlight that this characterization problem remains open for NIS and OWSC. Next, we prove that a SNIS realization of a $\BEC(\eps')$ sample from $\BEC(\eps)$ samples is feasible if and only if $(1-\eps')=(1-\eps)^k,$ for some $k\in N$. Additionally, in this context, we prove that all SNIS constructions must be linear. Next, if $(1-\eps')=(1-\eps)^k$, then the rate of simulating multiple independent $\BEC(\eps')$ samples from $\BEC(\eps)$ samples is at most $1/k$, which is also achievable using (block) linear constructions. Finally, we show that a SNIS realization of a $\BSC(\eps')$ sample from $\BSC(\eps)$ samples is feasible if and only if $(1-2\eps')=(1-2\eps)^k,$ for some $k\in N$. Interestingly, there are linear as well as (comparatively inefficient) non-linear SNIS constructions. However, if $(1-2\eps')=(1-2\eps)^k,$ then the rate of simulating $\BSC(\eps')$ samples is at most $1/k$ (irrespective of linear or non-linear constructions), and this rate is achievable using (block) linear constructions. Overall, our constructions and hardness of computation results are the strongest possible in the following sense. All our constructions are perfectly secure (even against malicious adversaries), that is, they realize SNIS with zero insecurity, and admit computationally efficient simulators. Moreover, all our feasibility and rate-achieving constructions hold whenever the number of input samples is sufficiently large. Additionally, our hardness of computation results extend to infinite families of reductions where (infinitely often) the insecurity falls faster than some appropriate inverse-polynomial of the number of input samples. Consequently, our results encompass the typical cryptographic contexts where the insecurity decays faster than all inverse-polynomials. Lastly, all our impossibility results hold against semi-honest adversaries and extend to the weaker game-based security definitions as well. Technically, our analysis relies on discrete Fourier analysis and an isoperimetric-type result on the Boolean hypercube.