CryptoDB
Towards Breaking the Half-barrier of Local Leakage-resilient Shamir's Secret Sharing
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| Abstract: | 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. |
BibTeX
@inproceedings{crypto-2024-34307,
title={Towards Breaking the Half-barrier of Local Leakage-resilient Shamir's Secret Sharing},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68388-6_10},
author={Hai H. Nguyen},
year=2024
}