CryptoDB
Secure Non-interactive Simulation from Arbitrary Joint Distributions
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| Abstract: | {\em Secure non-interactive simulation} (SNIS), introduced in {EUROCRYPT} 2022, is the information-theoretic analog of {\em pseudo-correlation generators}. SNIS allows parties, starting with samples of a source correlated private randomness, to non-interactively and securely transform them into samples from a different correlated private randomness. Determining the feasibility, rate, and capacity of SNIS is natural and essential for the efficiency of secure computation. This work initiates the study of SNIS, where the target distribution $(U,V)$ is a random sample from the {\em binary symmetric or erasure channels}; however, the source distribution can be arbitrary. In this context, our work presents: \begin{enumerate} \item The characterization of all sources that facilitate such SNIS, \item An upper and lower bound on their maximum achievable rate, and \item Exemplar SNIS instances where non-linear reductions achieve optimal efficiency; however, any linear reduction is insecure. \end{enumerate} These results collectively yield the fascinating instances of {\em computer-assisted search} for secure computation protocols that identify ingenious protocols that are more efficient than all known constructions. Our work generalizes the algebraization of the simulation-based definition of SNIS as an approximate eigenvector problem. The following foundational and general technical contributions of ours are the underpinnings of the results mentioned above. \begin{enumerate} \item Characterization of Markov and adjoint Markov operators' effect on the Fourier spectrum of reduction functions. \item A new concentration phenomenon in the Fourier spectrum of reduction functions. \item A powerful statistical-to-perfect lemma with broad consequences for feasibility and rate characterization of SNIS. \end{enumerate} Our technical analysis relies on Fourier analysis over large alphabets with arbitrary measure, the orthogonal Efron-Stein decomposition, and junta theorems of Kindler-Safra and Friedgut. Our work establishes a fascinating connection between the rate of SNIS and the maximal correlation, a prominent information-theoretic property. Our technical approach motivates the new problem of ``security-preserving dimension reduction'' in harmonic analysis, which may be of independent and broader interest. |
BibTeX
@inproceedings{tcc-2022-32605,
title={Secure Non-interactive Simulation from Arbitrary Joint Distributions},
publisher={Springer-Verlag},
author={Hamidreza Amini Khorasgani and Hemanta K. Maji and Hai H. Nguyen},
year=2022
}