Cryptology ePrint Archive: Report 2020/252

Secure Non-interactive Simulation: Hardness & Feasibility

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

Abstract: Network latency is a significant source of inefficiency in interactive protocols. This work contributes towards the possibility of reducing the round complexity and communication complexity of secure computation protocols to a minimum. We introduce the concept of secure non-interactive simulation of joint distributions.

Two parties begin with multiple independent samples from a correlated randomness source. Next, our objective is to investigate what forms of joint distributions can Alice and Bob securely simulate without any further communication. This offline preprocessing step fits perfectly within the offline-online paradigm of secure computation, which enables general secure computation even against parties with unbounded computational power.

One may interpret this concept as imbuing the notion of non-interactive simulation of joint distributions, which initiated from the seminal works of Gács and K\"orner (1972), and Wyner (1975), in information theory with cryptographic security. This concept is 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, secure non-interactive simulation is a natural restriction of performing cryptography with one-way communication introduced by Garg, Ishai, Kushilevitz, Ostrovsky, and Sahai (2015), which also serves as a naturally arising base case for inductively building cryptographic primitives with minimum communication complexity.

In this work, we study samples from (1) $\mathsf{BSS}(\epsilon)$, that is the joint distribution $(X,Y)$, where $X$ is a uniform random bit and $Y$ is correlated bit such that $X\neq Y$ with probability $\epsilon\in(0,1/2)$, and (2) $\mathsf{BES}(\epsilon)$, that is the joint distribution $(X,Y)$, where $X$ is a uniform random bit, and $Y=X$ with probability $(1-\epsilon)$; otherwise $Y=\perp$, where $\epsilon\in(0,1)$.

Note that the reverse hypercontractivity and hardness of cryptography with one-way messages both rule out the possibility of realizing any $\mathsf{BES}$ sample from $\mathsf{BSS}$ samples. This impossibility result carries over to our secure non-interactive simulation as well. Furthermore, we prove that it is also impossible to securely and non-interactively simulate samples of $\mathsf{BSS}$ from $\mathsf{BES}$ samples as well. Note that this impossibility result both in the setting of non-interactive simulation and cryptography with one-way communication remains open.

Next, we prove that we can simulate a sample of $\mathsf{BES}(\epsilon')$ from multiple samples of $\mathsf{BES}(\epsilon)$ if and only if $(1-\epsilon')=(1-\epsilon)^k,$ for some $k\in \mathbb{N}$. We proceed by proving that all secure constructions must be linear, and, after that, the rate of the simulation is at most $1/k$.

Finally, we show the existence of securely and non-interactively simulating a sample of $\mathsf{BSS}(\epsilon')$ from $\mathsf{BSS}(\epsilon)$ if and only if $(1-2\epsilon')=(1-2\epsilon)^k,$ for some $k\in\mathbb{N}$. Interestingly, there are linear as well as (comparatively inefficient) non-linear constructions.

Category / Keywords: foundations / Non-interactive Simulation, Secure Simulation, Binary Erasure Sample, Binary Symmetric Sample, Rate of Reduction

Date: received 24 Feb 2020, last revised 25 Feb 2020

Contact author: haminikh at purdue edu,hmaji@purdue edu,nguye245@purdue edu

Available format(s): PDF | BibTeX Citation

Version: 20200225:224557 (All versions of this report)

Short URL: ia.cr/2020/252


[ Cryptology ePrint archive ]