Towards Breaking the Half-Barrier of Local Leakage-Resilient Shamir's Secret Sharing
METADATA ONLY
Author / Producer
Date
2024
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 codebased 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( √n) when p = Θ(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.
Permanent link
Publication status
published
External links
Book title
Advances in Cryptology – CRYPTO 2024
Journal / series
Volume
14924
Pages / Article No.
257 - 285
Publisher
Springer
Event
44th Annual International Cryptology Conference (CRYPTO 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Shamir's secret sharing; leakage resilience; higher order Fourier analysis; character sums; leakage attacks; repairing Reed-Solomon codes
Organisational unit
03338 - Maurer, Ueli (emeritus) / Maurer, Ueli (emeritus)