Paper 2021/186
Leakageresilience of the Shamir Secretsharing Scheme against Physicalbit Leakages
Hemanta K. Maji, Hai H. Nguyen, Anat PaskinCherniavsky, Tom Suad, and Mingyuan Wang
Abstract
Efficient ReedSolomon code reconstruction algorithms, for example, by Guruswami and Wootters (STOC2016), translate into local leakage attacks on Shamir secretsharing schemes over characteristic2 fields. However, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO2018) showed that the Shamir secret sharing scheme over primefields is leakage resilient to onebit local leakage if the reconstruction threshold is roughly 0.87 times the total number of parties. In several application scenarios, like secure multiparty 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 secretsharing scheme's leakageresilience over a primefield $F$. The parties' secretshares, which are elements in the finite field $F$, are naturally represented as $\lambda$bit binary strings representing the elements $\{0,1,\dotsc,p1\}$. In our leakage model, the adversary can independently probe $m$ bitlocations 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 leakageresilient secure computation. Consider arbitrary reconstruction threshold $k\geq 2$, physical bitleakage parameter $m\geq 1$, and the number of parties $n\geq 1$. We prove that Shamir's secretsharing scheme with random evaluation places is leakageresilient 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 secretsharing 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 physicalbit leakage attack for $m=1$ physical bitleakage from $n=k$ secret shares and any primefield $F$ satisfying $\abs F=1\mod k$. In particular, there are (roughly) $\abs F^{nk+1}$ such vulnerable choices for the $n$tuple of evaluation places. We lowerbound 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ézout'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 IrwinHall distribution. A probability distribution's discrepancy is a new property of distributions that our work introduces, which is of potential independent interest.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. EUROCRYPT 2021
 Keywords
 Random Punctured ReedSolomon CodesPhysicalbit LeakageLocal Leakage ResilienceDiscrete Fourier AnalysisExponential SumsGeneralized Arithmetic ProgressionBezout TheoremIrwinHall Distribution
 Contact author(s)
 wang1929 @ purdue edu
 History
 20210302: revised
 20210220: received
 See all versions
 Short URL
 https://ia.cr/2021/186
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/186, author = {Hemanta K. Maji and Hai H. Nguyen and Anat PaskinCherniavsky and Tom Suad and Mingyuan Wang}, title = {Leakageresilience of the Shamir Secretsharing Scheme against Physicalbit Leakages}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/186}, year = {2021}, url = {https://eprint.iacr.org/2021/186} }