International Association for Cryptologic Research

International Association
for Cryptologic Research


Hamidreza Amini Khorasgani


Secure Non-interactive Simulation: Feasibility \& Rate 📺
Hamidreza Amini Khorasgani Hemanta K. Maji Hai H. Nguyen
A natural solution to increase the efficiency of secure computation will be to non-interactively and securely transform diverse inexpensive-to-generate correlated randomness, like, joint samples from noise sources, into correlations useful for secure computation protocols. Motivated by this general application for secure computation, our work introduces the notion of {\em secure non-interactive simulation} (\snis). Parties receive samples of correlated randomness, and they, without any interaction, securely convert them into samples from another correlated randomness. Our work presents a simulation-based security definition for \snis and initiates the study of the feasibility and efficiency of \snis. We also study \snis among fundamental correlated randomnesses like random samples from the binary symmetric and binary erasure channels, represented by \BSC and \BEC, respectively. We show the impossibility of interconversion between \BSC and \BEC samples. Next, we prove that a \snis of a $\BEC(\eps')$ sample (a \BEC with noise characteristic $\eps'$) from $\BEC(\eps)$ is feasible if and only if $(1-\eps') = (1-\eps)^k$, for some $k\in\NN$. In this context, we prove that all \snis constructions must be linear. Furthermore, if $(1-\eps') = (1-\eps)^k$, then the rate of simulating multiple independent $\BEC(\eps')$ samples is at most $1/k$, which is also achievable using (block) linear constructions. Finally, we show that a \snis 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\NN$. Interestingly, there are linear as well as non-linear \snis constructions. When $(1-2\eps')=(1-2\eps)^k$, we prove that the rate of a {\em perfectly secure} \snis is at most $1/k$, which is achievable using linear and non-linear constructions. Our technical approach algebraizes the definition of \snis and proceeds via Fourier analysis. Our work develops general analysis methodologies for Boolean functions, explicitly incorporating cryptographic security constraints. Our work also proves strong forms of {\em statistical-to-perfect security} transformations: one can error-correct a statistically secure \snis to make it perfectly secure. We show a connection of our research with {\em homogeneous Boolean functions} and {\em distance-invariant codes}, which may be of independent interest.
Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness
Hamidreza Amini Khorasgani Hemanta K. Maji Tamalika Mukherjee
Consider the representative task of designing a distributed coin-tossing protocol for n processors such that the probability of heads is $$X_0\in [0,1]$$. This protocol should be robust to an adversary who can reset one processor to change the distribution of the final outcome. For $$X_0=1/2$$, in the information-theoretic setting, no adversary can deviate the probability of the outcome of the well-known Blum’s “majority protocol” by more than $$\frac{1}{\sqrt{2\pi n}}$$, i.e., it is $$\frac{1}{\sqrt{2\pi n}}$$ insecure.In this paper, we study discrete-time martingales $$(X_0,X_1,\dotsc ,X_n)$$ such that $$X_i\in [0,1]$$, for all $$i\in \{0,\dotsc ,n\}$$, and $$X_n\in {\{0,1\}} $$. These martingales are commonplace in modeling stochastic processes like coin-tossing protocols in the information-theoretic setting mentioned above. In particular, for any $$X_0\in [0,1]$$, we construct martingales that yield $$\frac{1}{2}\sqrt{\frac{X_0(1-X_0)}{n}}$$ insecure coin-tossing protocols. For $$X_0=1/2$$, our protocol requires only 40% of the processors to achieve the same security as the majority protocol.The technical heart of our paper is a new inductive technique that uses geometric transformations to precisely account for the large gaps in these martingales. For any $$X_0\in [0,1]$$, we show that there exists a stopping time $$\tau $$ such that The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, i.e., a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that any stopping time $$\tau $$ has Our lower-bound holds for all $$X_0\in [0,1]$$; while the previous bound of Cleve and Impagliazzo (1993) exists only for positive constant $$X_0$$. Conceptually, our approach only employs elementary techniques to analyze these martingales and entirely circumvents the complex probabilistic tools inherent to the approaches of Cleve and Impagliazzo (1993) and Beimel, Haitner, Makriyannis, and Omri (2018).By appropriately restricting the set of possible stopping-times, we present representative applications to constructing distributed coin-tossing/dice-rolling protocols, discrete control processes, fail-stop attacking coin-tossing/dice-rolling protocols, and black-box separations.