You are looking at a specific version 20200225:224557 of this paper. See the latest version.

Paper 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örner (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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Non-interactive SimulationSecure SimulationBinary Erasure SampleBinary Symmetric SampleRate of Reduction
Contact author(s)
haminikh @ purdue edu,hmaji @ purdue edu,nguye245 @ purdue edu
History
2022-02-07: last of 5 revisions
2020-02-25: received
See all versions
Short URL
https://ia.cr/2020/252
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.