CS Paper Radar

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate

Hai H. Nguyen

cs.CR ·submitted 2026-10-13 04:37 UTC · v1
theory

Abstract

We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following. (1) There is an absolute constant $c_{\mathrm{bh}}<1/2$ such that, for $k\ge c_{\mathrm{bh}}n$, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was $0.668n$. (2) For every fixed $0<δ<1/2$ and $k\ge(1/2+δ)n$, Shamir sharing is resilient to $\left\lfloor\fracδ{24}\log_2 n\right\rfloor$ bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on $δ$. (3) For every fixed threshold rate $c>0$ and $k\ge cn$, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to $η_c\log_2 p$ bits, for a constant $η_c>0$. All three results follow from one analytic framework, which we develop for generalized Reed--Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron--Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.

Closest papers

Nearest neighbours by meaning across the whole index.

An Explicit Below Half Threshold Bound for the Local Leakage Resilience of Shamir's Secret Sharing Scheme

cs.CR cs.IT ·2026-11-09 ·Cheng Zhang, Xin Wang, Xiangliang Kong
similarity 0.82
Abstract

As a fundamental cryptographic primitive, secret sharing distributes a secret among multiple parties and allows certain authorized parties to recover the secret while preventing unauthorized parties from knowing the secret. However, local leakage from each party member allows an adversary to learn partial information from each share, which is not guaranteed by traditional security. In this paper, we study bounds on the reconstruction threshold of Shamir's secret sharing scheme over prime fields against arbitrary 1-bit local leakage. We show that, for all sufficiently large $n$ and every prime $p>n$, the $(n,t)$-Shamir's scheme is $\exp(-Ω(n))$-resilient whenever $t/n\geq 0.489$, for any choice of distinct nonzero evaluation points. Our proof refines the dual-code list recovery analysis and combines complementary Fourier estimates according to the support sizes and biases of the leakage functions, yielding an improved explicit reconstruction threshold bound.

0.17

Quantum Leakage Resilience of Shamir Secret Sharing

cs.CR quant-ph ·2026-09-29 ·Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
similarity 0.79
Abstract · 38 pages, 2 tables

We initiate the study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields. A well-studied leakage model for Shamir's secret sharing classically is single-bit local leakage from each share. We consider its quantum analogue where, for each party, a local leakage channel takes as input the party's share and outputs a leaked qubit. Without preshared entanglement, we show that the distinguishing advantage is $2^{-Ω(n)}$ when the threshold rate $t/n=τ$ exceeds $τ_\star\approx0.73339$ by a fixed positive margin. More generally, we allow disjoint entangled blocks of any fixed maximum size where there is no entanglement between different blocks or with the adversary, and each block emits at most a fixed number of qubits. Security holds when the threshold rate is high enough (sufficiently close to one). We then allow a specified set of devices to share entanglement with the adversary. We show that security holds even when a linear number of devices ($αn$ for small $α>0$) share entanglement with each other and with the adversary for a large enough threshold rate. As a complementary negative result, we also show that even classical single-bit leakage makes Shamir scheme insecure if we allow arbitrarily large entanglement between the leakage devices. A GHZ state shared by exactly $t$ leakage devices makes even classical one-bit leakage insecure, without any entanglement with the adversary. In this attack, each participating device emits only one classical bit, and their joint parity distinguishes any chosen pair of secrets with a constant advantage. Thus, for fixed threshold rates above $τ_\star$, the maximum number of devices that may share arbitrary entanglement with one another and with the adversary while preserving security is linear in $n$ up to constant factors, although the optimal support fraction remains open.

0.61

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

cs.CR quant-phcs.DMcs.IT ·2026-10-08 ·Yihang Sun, Mary Wootters
similarity 0.70
Abstract · 82 pages, 3 figures; v2 adds near-optimal OPI discrepancy for random Reed-Solomon codes

We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI), over a prime field $\mathbb{F}_p$. For a polynomial $Q(X)$ of degree less than $k$, LLR for Shamir secret sharing asks what a few leaked bits from each of the $n$ shares $Q(α_1), \ldots, Q(α_n)$ reveal about $Q(0)$. Given (worst-case) input lists $S_1, \ldots, S_n \subset \mathbb{F}_p$, OPI seeks a polynomial $Q(X)$ so that $Q(α_i) \in S_i$ for as many $i$ as possible. Leveraging recent connections between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant $δ> 0$ so that Shamir secret-sharing is one-bit LLR (only a negligible amount about $Q(0)$ is learned) whenever $R := k/n \geq 1/2 - δ$. This is the first result to break the so-called ``one-half barrier'' for LLR, and improves over the previous best known result, requiring $R \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_ρ(R)-\varepsilon$ fraction of the lists, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_ρ$ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results for all OPI instances; and when the evaluation points $α_i$ are chosen at random, for every rate $R > 0$ we show that, with high probability, for worst-case $S_i$ there exists \emph{perfect} solution. Finally, we adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.

0.50

Leakage-Resilient Computation via Matrix Refreshing

cs.CR ·2026-11-03 ·Stefan Dziembowski, Sebastian Faust
theory similarity 0.68
Abstract

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $λ$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6λ-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18λ-n/27}$ for $S$ operations and at most $λ$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

0.20

Secret Sharing at the Shannon Ceiling

cs.CC ·2026-08-17 ·Christopher Williamson
similarity 0.65
Abstract

For every $n\geq 9$ that is a multiple of 3, we construct an explicit access structure on $n$ participants. In every perfect secret-sharing scheme realising this access structure, if $S$ denotes the random secret, then the sum of the share entropies is at least $\left(\frac{n^2}{9}+\frac{2n}{3}\right)H(S)$, and some participant has share entropy at least $\left(\frac{n}{6}+\frac12\right)H(S)$. After normalisation by $H(S)$, these are respectively $Ω(n^2)$ and $Ω(n)$ lower bounds and also give the same asymptotic lower bounds on the total and largest expected binary lengths of the shares. This improves by a logarithmic factor the longstanding general lower bounds of $Ω(n^2/\log n)$ for total share size and $Ω(n/\log n)$ for maximum share size due to Csirmaz. The proof uses only elementary Shannon inequalities, together with some averaging arguments. The Shannon-information method has universal $O(n^2)$ and $O(n)$ ceilings for the total and maximum normalised entropy lower bounds it can certify, so our construction reaches both ceilings up to constant factors.

0.42

Secret Sharing Despite Non-Extractable Randomness

cs.CR ·2026-10-14 ·Divesh Aggarwal
similarity 0.64
Abstract

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.

0.23

Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys

cs.IT ·2026-10-29 ·Maryam Keshvari, Remi A. Chou
published similarity 0.64
Abstract · A preliminary version of this work was presented at the 2023 Allerton Conference on Communication, Control, and Computing

We study distributed storage over public communication channels where privacy is realized using shared secret keys. Specifically, a user wishes to store a file across $L$ servers such that any subset of at least $t$ servers can reconstruct the file, while any subset of at most $z$ colluding servers learns no more than a fraction $α$ of the file. Unlike classical secret-sharing models that assume secure communication channels between the user and each server, we consider a setting where all transmissions occur over a public channel and the user shares an individual secret key of length $n$ bits with each server. For a fixed key length $n$, we characterize the trade-off between the privacy leakage parameter $α$ and the maximum file size that can be securely stored. Additionally, we determine the minimum local randomness, public communication, and storage required to achieve this optimal trade-off.

0.27

SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders

cs.CR cs.IT ·2026-11-12 ·Muhammad Arzaki, Muhammed F. Esgin, Amin Sakzad, Ron Steinfeld
theory similarity 0.63
Abstract · 84 pages, 3 figures. Also available as Cryptology ePrint Archive, Paper 2026/2841: https://eprint.iacr.org/2026/2841

We introduce SEC, an expander-code-based ramp secret sharing scheme over $\mathbb{Z}$-modules, particularly suitable for lattice-based distributed cryptography. It is everywhere-short: bounded secret coefficients yield bounded share coefficients, and the integer reconstruction vectors have bounded entries. Moreover, each participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds. This improves on prior schemes with bounded share coefficients and bounded entries in the integer reconstruction vectors, in which the number of sub-shares or shares per participant grows either with the number of parties and the threshold or with the security parameter. The construction rests on a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix. We prove correctness, everywhere-shortness, and linearity, and give a publicly computable entrywise bound on the reconstruction vector our algorithm returns for each authorized set. For privacy, we introduce hard-core local leakage resilience, which strengthens the leakage-resilience notion of Nielsen and Simkin (EUROCRYPT 2020) to protect a hard-core function of the secret, and we prove that SEC satisfies it against correlated multi-query local leakage under the MatrixHint-MLWE problem, which admits a reduction from the standard MLWE problem. For $n=60$ participants and security parameter $κ=128$, SEC achieves privacy threshold 6 against $2^{64}$ leakage queries and empirical reconstruction threshold 46. The ideal entropy-coded secret and share sizes are about 3.5 KiB and 6.4 KiB, respectively.

0.31