International Association
for Cryptologic Research

Probing physical bits in hardware has compromised cryptographic systems. This work investigates how to instantiate Shamir's secret sharing so that the physical probes into its shares reveal statistically insignificant information about the secret. Over prime fields, Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT 2021) proved that choosing random evaluation places achieves this objective with high probability. Our work extends their randomized construction to composite order fields -- particularly for fields with characteristic 2. Next, this work presents an algorithm to classify evaluation places as secure or vulnerable against physical-bit probes for some specific cases. Our security analysis of the randomized construction is Fourier-analytic, and the classification techniques are combinatorial. Our analysis relies on (1) contemporary Bezout-theorem-type algebraic complexity results that bound the number of simultaneous zeroes of a system of polynomial equations over composite order fields and (2) characterization of the zeroes of an appropriate generalized Vandermonde determinant.

Consider two-party secure function evaluation against an honest-but-curious adversary in the information-theoretic plain model. We study the round complexity of securely realizing a given secure function evaluation functionality. Chor-Kushilevitz-Beaver (1989) proved that the round complexity of securely evaluating a deterministic function depends solely on the cardinality of its domain and range. A folklore conjecture asserts that this phenomenon extends to functions with randomized output. Our work falsifies this folklore conjecture -- revealing intricate subtleties even for this elementary security notion. For every $r$, there is a function $f_r$ with binary inputs and five output alphabets that has round complexity $r$. Previously, such a construction was known using $(r+1)$ output symbols. This counter-example is optimal -- we prove that any securely realizable function with binary inputs and four output alphabets has round complexity at most four. We work in the geometric framework Basu-Khorasgani-Maji-Nguyen (FOCS--2022) introduced to investigate randomized functions' round complexity. Our work establishes a connection between secure computation and the lamination hull (geometric object originally motivated by applications in hydrodynamics). Our counterexample constructions are related to the ``tartan square'' construction in the lamination hull literature.

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.

{\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.

Motivated by leakage-resilient secure computation of circuits with addition and multiplication gates, this work studies the leakage-resilience of linear secret-sharing schemes with a small reconstruction threshold against any {\em bounded-size} family of joint leakage attacks, \ie, the leakage function can leak {\em global} information from all secret shares. We first prove that, with high probability, the Massey secret-sharing scheme corresponding to a random linear code over a finite field $F$ is leakage-resilient against any $\ell$-bit joint leakage family of size at most $\abs{F}^{k-2.01}/8^\ell $, where $k$ is the reconstruction threshold. Our result (1) bypasses the bottleneck due to the existing Fourier-analytic approach, (2) enables secure multiplication of secrets, and (3) is near-optimal. We use combinatorial and second-moment techniques to prove the result. Next, we show that the Shamir secret-sharing scheme over a prime-order field $F$ with randomly chosen evaluation places and with threshold $k$ is leakage-resilient to any $\ell$-bit joint leakage family of size at most $\abs{F}^{2k-n-2.01}/(k!\cdot 8^\ell)$ with high probability. We prove this result by marrying our proof techniques for the first result with the existing Fourier analytical approach. Moreover, it is unlikely that one can extend this result beyond $k/n\leq0.5$ due to the technical hurdle of the Fourier-analytic approach.

Efficient Reed-Solomon code reconstruction algorithms, for example, by Guruswami and Wooters (STOC--2016), translate into local leakage attacks on Shamir secret-sharing schemes over characteristic-2 fields. However, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO--2018) showed that the Shamir secret sharing scheme over prime-fields is leakage resilient to one-bit local leakage if the reconstruction threshold is roughly 0.87 times the total number of parties. In several application scenarios, like secure multi-party multiplication, the reconstruction threshold must be at most half the number of parties. Furthermore, the number of leakage bits that the Shamir secret sharing scheme is resilient to is also unclear. Towards this objective, we study the Shamir secret-sharing scheme's leakage-resilience over a prime-field $F$. The parties' secret-shares, which are elements in the finite field $F$, are naturally represented as $\lambda$-bit binary strings representing the elements $\{0,1,\dotsc,p-1\}$. In our leakage model, the adversary can independently probe $m$ bit-locations from each secret share. The inspiration for considering this leakage model stems from the impact that the study of oblivious transfer combiners had on general correlation extraction algorithms, and the significant influence of protecting circuits from probing attacks has on leakage-resilient secure computation. Consider arbitrary reconstruction threshold $k\geq 2$, physical bit-leakage parameter $m\geq 1$, and the number of parties $n\geq 1$. We prove that Shamir's secret-sharing scheme with random evaluation places is leakage-resilient with high probability when the order of the field $F$ is sufficiently large; ignoring polylogarithmic factors, one needs to ensure that $\log \abs F \geq n/k$. Our result, excluding polylogarithmic factors, states that Shamir's scheme is secure as long as the total amount of leakage $m\cdot n$ is less than the entropy $k\cdot\lambda$ introduced by the Shamir secret-sharing scheme. Note that our result holds even for small constant values of the reconstruction threshold $k$, which is essential to several application scenarios. To complement this positive result, we present a physical-bit leakage attack for $m=1$ physical bit-leakage from $n=k$ secret shares and any prime-field $F$ satisfying $\abs F=1\mod k$. In particular, there are (roughly) $\abs F^{n-k+1}$ such vulnerable choices for the $n$-tuple of evaluation places. We lower-bound the advantage of this attack for small values of the reconstruction threshold, like $k=2$ and $k=3$, and any $\abs F=1\mod k$. In general, we present a formula calculating our attack's advantage for every $k$ as $\abs F\rightarrow\infty.$ Technically, our positive result relies on Fourier analysis, analytic properties of proper rank-$r$ generalized arithmetic progressions, and B\'ezout's theorem to bound the number of solutions to an equation over finite fields. The analysis of our attack relies on determining the ``discrepancy'' of the Irwin-Hall distribution. A probability distribution's discrepancy is a new property of distributions that our work introduces, which is of potential independent interest.

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, guaranteeing output delivery to honest parties when the adversarial parties may abort the protocol has been a challenging objective. As a representative task, this work considers two-party coin-tossing protocols with guaranteed output delivery, a.k.a., fair coin-tossing. In the information-theoretic plain model, as in two-party zero-sum games, one of the parties can force an output with certainty. In the commitment-hybrid, any $r$-message coin-tossing protocol is ${1/\sqrt r}$-unfair, i.e., the adversary can change the honest party's output distribution by $1/\sqrt r$ in the statistical distance. Moran, Naor, and Segev (TCC--2009) constructed the first $1/r$-unfair protocol in the oblivious transfer-hybrid. No further security improvement is possible because Cleve (STOC--1986) proved that $1/r$-unfairness is unavoidable. Therefore, Moran, Naor, and Segev's coin-tossing protocol is optimal. However, is oblivious transfer necessary for optimal fair coin-tossing? Maji and Wang (CRYPTO--2020) proved that any coin-tossing protocol using one-way functions in a black-box manner is at least $1/\sqrt r$-unfair. That is, optimal fair coin-tossing is impossible in Minicrypt. Our work focuses on tightly characterizing the hardness of computation assumption necessary and sufficient for optimal fair coin-tossing within Cryptomania, outside Minicrypt. Haitner, Makriyannia, Nissim, Omri, Shaltiel, and Silbak (FOCS--2018 and TCC--2018) proved that better than $1/\sqrt r$-unfairness, for any constant $r$, implies the existence of a key-agreement protocol. We prove that any coin-tossing protocol using public-key encryption (or, multi-round key agreement protocols) in a black-box manner must be $1/\sqrt r$-unfair. Next, our work entirely characterizes the additional power of secure function evaluation functionalities for optimal fair coin-tossing. We augment the model with an idealized secure function evaluation of $f$, \aka, the $f$-hybrid. If $f$ is complete, that is, oblivious transfer is possible in the $f$-hybrid, then optimal fair coin-tossing is also possible in the $f$-hybrid. On the other hand, if $f$ is not complete, then a coin-tossing protocol using public-key encryption in a black-box manner in the $f$-hybrid is at least $1/\sqrt r$-unfair.

Innovative side-channel attacks have repeatedly falsified the assumption that cryptographic implementations are opaque black-boxes. Therefore, it is essential to ensure cryptographic constructions' security even when information leaks via unforeseen avenues. One such fundamental cryptographic primitive is the secret-sharing schemes, which underlies nearly all threshold cryptography. Our understanding of the leakage-resilience of secret-sharing schemes is still in its preliminary stage. This work studies locally leakage-resilient linear secret-sharing schemes. An adversary can leak $m$ bits of arbitrary local leakage from each $n$ secret shares. However, in a locally leakage-resilient secret-sharing scheme, the leakage's joint distribution reveals no additional information about the secret. For every constant $m$, we prove that the Massey secret-sharing scheme corresponding to a random linear code of dimension $k$ (over sufficiently large prime fields) is locally leakage-resilient, where $k/n > 1/2$ is a constant. The previous best construction by Benhamouda, Degwekar, Ishai, Rabin (CRYPTO--2018) needed $k/n > 0.907$. A technical challenge arises because the number of all possible $m$-bit local leakage functions is exponentially larger than the number of random linear codes. Our technical innovation begins with identifying an appropriate pseudorandomness-inspired family of tests; passing them suffices to ensure leakage-resilience. We show that most linear codes pass all tests in this family. This Monte-Carlo construction of linear secret-sharing scheme that is locally leakage-resilient has applications to leakage-resilient secure computation. Furthermore, we highlight a crucial bottleneck for all the analytical approaches in this line of work. Benhamouda et al. introduced an analytical proxy to study the leakage-resilience of secret-sharing schemes; if the proxy is small, then the scheme is leakage-resilient. However, we present a one-bit local leakage function demonstrating that the converse is false, motivating the need for new analytically well-behaved functions that capture leakage-resilience more accurately. Technically, the analysis involves probabilistic and combinatorial techniques and (discrete) Fourier analysis. The family of new ``tests'' capturing local leakage functions, we believe, is of independent and broader interest.

A two-party fair coin-tossing protocol guarantees output delivery to the honest party even when the other party aborts during the protocol execution. Cleve (STOC--1986) demonstrated that a computationally bounded fail-stop adversary could alter the output distribution of the honest party by (roughly) $1/r$ (in the statistical distance) in an $r$-message coin-tossing protocol. An optimal fair coin-tossing protocol ensures that no adversary can alter the output distribution beyond $1/r$. In a seminal result, Moran, Naor, and Segev (TCC--2009) constructed the first optimal fair coin-tossing protocol using (unfair) oblivious transfer protocols. Whether the existence of oblivious transfer protocols is a necessary hardness of computation assumption for optimal fair coin-tossing remains among the most fundamental open problems in theoretical cryptography. The results of Impagliazzo and Luby (FOCS–1989) and Cleve and Impagliazzo (1993) prove that optimal fair coin-tossing implies the necessity of one-way functions' existence; a significantly weaker hardness of computation assumption compared to the existence of secure oblivious transfer protocols. However, the sufficiency of the existence of one-way functions is not known. Towards this research endeavor, our work proves a black-box separation of optimal fair coin-tossing from the existence of one-way functions. That is, the black-box use of one-way functions cannot enable optimal fair coin-tossing. Following the standard Impagliazzo and Rudich (STOC--1989) approach of proving black-box separations, our work considers any $r$-message fair coin-tossing protocol in the random oracle model where the parties have unbounded computational power. We demonstrate a fail-stop attack strategy for one of the parties to alter the honest party's output distribution by $1/\sqrt r$ by making polynomially-many additional queries to the random oracle. As a consequence, our result proves that the $r$-message coin-tossing protocol of Blum (COMPCON--1982) and Cleve (STOC--1986), which uses one-way functions in a black-box manner, is the best possible protocol because an adversary cannot change the honest party's output distribution by more than $1/\sqrt r$. Several previous works, for example, Dachman--Soled, Lindell, Mahmoody, and Malkin (TCC--2011), Haitner, Omri, and Zarosim (TCC--2013), and Dachman--Soled, Mahmoody, and Malkin (TCC--2014), made partial progress on proving this black-box separation assuming some restrictions on the coin-tossing protocol. Our work diverges significantly from these previous approaches to prove this black-box separation in its full generality. The starting point is the recently introduced potential-based inductive proof techniques for demonstrating large gaps in martingales in the information-theoretic plain model. Our technical contribution lies in identifying a global invariant of communication protocols in the random oracle model that enables the extension of this technique to the random oracle model.

This paper constructs high-rate non-malleable codes in the information-theoretic plain model against tampering functions with bounded locality. We consider $$\delta $$-local tampering functions; namely, each output bit of the tampering function is a function of (at most) $$\delta $$ input bits. This work presents the first explicit and efficient rate-1 non-malleable code for $$\delta $$-local tampering functions, where $$\delta =\xi \lg n$$ and $$\xi <1$$ is any positive constant. As a corollary, we construct the first explicit rate-1 non-malleable code against NC$$^0$$ tampering functions.Before our work, no explicit construction for a constant-rate non-malleable code was known even for the simplest 1-local tampering functions. Ball et al. (EUROCRYPT–2016), and Chattopadhyay and Li (STOC–2017) provided the first explicit non-malleable codes against $$\delta $$-local tampering functions. However, these constructions are rate-0 even when the tampering functions have 1-locality. In the CRS model, Faust et al. (EUROCRYPT–2014) constructed efficient rate-1 non-malleable codes for $$\delta = O(\log n)$$ local tampering functions.Our main result is a general compiler that bootstraps a rate-0 non-malleable code against leaky input and output local tampering functions to construct a rate-1 non-malleable code against $$\xi \lg n$$-local tampering functions, for any positive constant $$\xi < 1$$. Our explicit construction instantiates this compiler using an appropriate encoding by Ball et al. (EUROCRYPT–2016).

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.

Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by adversarial parties, which can compromise the security of the secure computation protocol. The objective, therefore, is to preserve the security of the honest party despite the leakage performed by the adversary on her share.Prior solutions, starting with n-bit leaky shares, either used 4 messages or enabled the secure computation of only sub-linear size circuits. Our work presents the first 2-message secure computation protocol for 2-party functionalities that have $$\varTheta (n)$$ circuit-size despite $$\varTheta (n)$$-bits of leakage, a qualitatively optimal result. We compose a suitable 2-message secure computation protocol in parallel with our new 2-message correlation extractor. Correlation extractors, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS–2009) as a natural generalization of privacy amplification and randomness extraction, recover “fresh” correlations from the leaky ones, which are subsequently used by other cryptographic protocols. We construct the first 2-message correlation extractor that produces $$\varTheta (n)$$-bit fresh correlations even after $$\varTheta (n)$$-bit leakage.Our principal technical contribution, which is of potential independent interest, is the construction of a family of multiplication-friendly linear secret sharing schemes that is simultaneously a family of small-bias distributions. We construct this family by randomly “twisting then permuting” appropriate Algebraic Geometry codes over constant-size fields.