The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution ${P_{{U_d},{V_d}}},$ such that ${P_{{U_d},{V_d}}}$ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets ${\mathcal{U}}{\text{and}}{\mathcal{V}}$ have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution ${P_{{U_d},{V_d}}},$ such that ${P_{{U_d},{V_d}}}$ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets ${\mathcal{U}}{\text{and}}{\mathcal{V}}$ have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.

arXiv:2212.09239IEEE Information Theory Workshop (ITW)Apr 23, 20233 citations

Secure Non-interactive Simulation: Feasibility and Rate

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

Lecture notes in computer scienceJan 1, 20226 citations

Non interactive simulation of correlated distributions is decidable

Anindya De, Elchanan Mossel, Joe Neeman

A basic problem in information theory is the following: Let P = (X, Y) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples {xi}i≥1 and Bob gets samples {yi}i≥i and for all i, (xi,yi) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction? Classical works in information theory by Gács-Körner and Wyner answer this question when at least one of P or Q is the distribution Eq (Eq is defined as uniform over the points (0, 0) and (1, 1)). However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.A basic problem in information theory is the following: Let P = (X, Y) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples {xi}i≥1 and Bob gets samples {yi}i≥i and for all i, (xi,yi) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction? Classical works in information theory by Gács-Körner and Wyner answer this question when at least one of P or Q is the distribution Eq (Eq is defined as uniform over the points (0, 0) and (1, 1)). However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.

arXiv:1701.01485Society for Industrial and Applied Mathematics eBooksJan 1, 201821 citations

Non-Interactive Secure Computation Based on Cut-and-Choose

Arash Afshar, Payman Mohassel, Benny Pinkas B +1 more

Lecture notes in computer scienceJan 1, 201487 citations

On Non-Interactive Simulation of Distributed Sources With Finite Alphabets

Hojat Allah Salehi, Farhad Shirani

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences $X^{d}$ and $Y^{d}$ drawn according to a joint distribution $P_{X^{d}Y^{d}}$ . The agents aim to generate outputs $U=f_{d}(X^{d})$ and $V=g_{d}(Y^{d})$ with a joint distribution sufficiently close in total variation to a target distribution $Q_{UV}$ . Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is $O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)$ . In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is $\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)$ , thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions $(f_{d}(X^{d}),g_{d}(Y^{d}))$ . The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences$X^{d}$and$Y^{d}$drawn according to a joint distribution$P_{X^{d}Y^{d}}$. The agents aim to generate outputs$U=f_{d}(X^{d})$and$V=g_{d}(Y^{d})$with a joint distribution sufficiently close in total variation to a target distribution$Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is$O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)$. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is$\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)$, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions$(f_{d}(X^{d}),g_{d}(Y^{d}))$. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.

arXiv:2403.00989IEEE Transactions on Information TheoryAug 11, 20250 citations

Secure Non-interactive Simulation: Feasibility & Rate

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

Jan 1, 20200 citations

{P_{{U_d},{V_d}}},

such that

{P_{{U_d},{V_d}}}

converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets

{\mathcal{U}}{\text{and}}{\mathcal{V}}

have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences

X^{d}

and

Y^{d}

drawn according to a joint distribution

P_{X^{d}Y^{d}}

. The agents aim to generate outputs

U=f_{d}(X^{d})

and

V=g_{d}(Y^{d})

with a joint distribution sufficiently close in total variation to a target distribution

Q_{UV}

. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is

O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)

. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is

\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)

, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions

(f_{d}(X^{d}),g_{d}(Y^{d}))

. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.