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.

Advanced methods for repairing Reed-Solomon codes, exemplified by the work of Guruswami and Wooters (STOC 2016), can be exploited to launch local leakage attacks against Shamir secret-sharing schemes over characteristic-2 fields. Conversely, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO 2018) proved that high-threshold instances of Shamir's secret sharing over prime fields are resilient to one-bit local leakage. Since then, extensive efforts have been made to lower the threshold. However, even for simple leakage such as quadratic residue, it remains uncertain whether Shamir's scheme is leakage-resilient when the reconstruction threshold $n$ is less than half the number of parties $k$. As highlighted by Maji, Paskin-Cherniavsky, Suad, and Wang (CRYPTO 2021), the common approach fails to establish the leakage resilience of Shamir's scheme against quadratic residue leakage when $k < n/2$. In many applications, the threshold must not exceed half the number of parties. This work develops a new framework for studying the local leakage resilience of Shamir's secret sharing over a finite field of prime order $p$. Our work demonstrates that Shamir secret sharing remains leakage resilient against almost all 1-bit local leakages, including quadratic residue leakage, even when $k = cn$ for any constant $c$, provided the prime field is sufficiently large. This result extends to any MDS code-based secret sharing. For the hardness of computation, we propose an explicit 2-bit leakage attack capable of determining the secret in Shamir secret sharing with a reconstruction threshold $k = O(\sqrt{n})$ when $p = \Theta(n)$. Our attack translates into a repairing algorithm for Reed-Solomon codes. Technically, our framework relies on additive combinatorics and character sums, specifically higher-order Fourier analysis. These connections may be of independent interest.

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.

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.