Partial Derandomization for Leakage-Resilient Shamir’s Secret Sharing over Composite Order Fields* S. Venkitesh†
arXiv:2607.28757v1 [cs.CR] 30 Jul 2026
Abstract We make progress on the question of constructing explicit evaluation places for leakageresilient Shamir’s secret sharing, over composite order fields. Previously, Maji et al. (EUROCRYPT 2024) showed that random evaluation places yield Shamir’s secret sharing over the composite order field Fpd that is statistically secure against physical-bit leakage. Later, Nguyen (EUROCRYPT 2025) established a dichotomy that linear code-based secret-sharing scheme over the field Fpd is either statistically secure or completely insecure against such leakage. Building upon Nguyen’s dichotomy, we present a partial derandomization of evaluation places, improving upon the Maji et al. result for a restricted regime of parameters. We replace the random choice of n independent evaluation places by the iterates xj = Φj (x0 ) of a simple fixed rational function Φ, where the initial point x0 ∈ F∗pd is randomly chosen. The randomness in the evaluation places thus drops from nd log p bits to d log p bits. Our construction is valid for the regime n = O(d/ logp d), and any reconstruction threshold k ⩾ 2; in fact, the scheme attains perfect security (statistical distance exactly zero) against single-block leakage. Our technique is a partial fraction nondegeneracy argument that exploits the distinct poles of the rational iterates.
Contents 1 Introduction 1.1 Motivation; 1.2 Our results; 1.3 Comparison with prior work; 1.5 Technical overview; 1.6 Discussion and open problems
2 1.4 Related work;
2 Preliminaries 2.1 The field and coordinates; 2.2 Shamir’s secret sharing and leakage models; 2.3 The perfect dichotomy; 2.4 Surjectivity and the test matrix
7
3 The construction 3.1 The step operator; 3.2 Distinct poles, fixed points, and pole avoidance; 3.3 Classifier and choice of base point
10
4 Single-block security 4.1 Nondegeneracy via partial fractions;
14 4.2 Full rank of the test matrix;
5 Multi-block security 5.1 Setup; 5.2 Nondegeneracy with field coefficients;
4.3 Physical bit security 16
5.3 Multi-block theorems 20
A Alternative proof of the dichotomy
* A preliminary version of this work is due to appear at ITC 2026. † Institute for the Theory of Computing, The Stein Faculty of Computer and Information Science, Ben Gurion
University of the Negev, Beersheva, Israel. Email: [email protected]
1
1
Introduction
Threshold secret-sharing schemes, such as Shamir’s scheme [Sha79], distribute a secret among n parties so that any k of them can reconstruct the secret, while any fewer than k parties learn nothing about it. In the standard corruption model, an adversary obtains the complete shares of some parties and has no information about the remaining shares. Side-channel attacks have repeatedly circumvented this all-or-nothing assumption. Rather than corrupting entire shares, a side-channel adversary accumulates small amounts of information, like individual bits, power traces, and timing signals, from all shares simultaneously (see Ishai, Sahai, and Wagner [ISW03]). The mathematical abstraction of such threats is independent local leakage: the adversary applies a bounded function to each share independently and observes only the outputs. The study of locally leakage-resilient secret sharing was initiated by Benhamouda, Degwekar, Ishai, and Rabin [BD+ 21] and is also implicit in the work of Goyal and Kumar [GK18]. A particularly natural leakage model, introduced by [ISW03], probes physical bits in the memory storing each share. Since elements of a finite field Fpd are stored as d coordinates over Fp , each represented as a ⌈log2 p⌉-bit binary string, a physical bit probe extracts a single bit from this representation. Additive secret sharing is known to be vulnerable to such probes: the parity-ofparities attack of Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang [MN+ 21] leaks the least significant bit of each share and distinguishes secrets with advantage (2/π)n over any prime field Fp . Over characteristic-2 fields, this attack can distinguish secrets 0 and 1 with certainty. Shamir’s secret sharing inherits these vulnerabilities if its evaluation places are chosen carelessly ([MN+ 21], and Costes and Stam [CS21]). The question, then, is whether Shamir’s scheme can be instantiated to resist physical bit probes. Over prime fields, [MN+ 21] showed that choosing evaluation places uniformly at random yields a leakage-resilient scheme with high probability. Maji, Nguyen, Paskin-Cherniavsky, and Ye [MN+ 24] extended this randomized construction to composite order fields, particularly fields of characteristic 2, and also gave an exact security classifier for k = 2 against single-block leakage. However, no explicit evaluation places were known for k > 2 or for the general blockleakage regime over composite fields. Even for k = 2, the classifier of [MN+ 24] certifies individual evaluation-place tuples but does not produce a closed form family. Separately, Hwang, Maji, Nguyen, and Ye [HM+ 25] initiated the study of explicit constructions over prime fields, providing classifiers and derandomized evaluation places for Mersenne and Fermat primes in the full-threshold regime n = k. In this work, we present a partial derandomization of [MN+ 24]. Building on the dichotomy of Nguyen [Ngu25], which establishes that any linear code-based secret-sharing scheme over the field Fpd is either perfectly secure or completely insecure against physical-bit leakage, we replace the random choice of n independent evaluation places by a structured one-parameter family: the evaluation places are xj = Φj (x0 ), where Φ(x) := αx/(x + 1), α is a fixed multiplicative generator of F∗pd , and x0 ∈ F∗pd is a randomly chosen base point. As it turns out, Φ is a Möbius transformation, and the utility of such structured algebraic transformations in defining evaluation places seems unexplored so far. The randomness needed to specify the n evaluation places drops from nd log p bits to d log p bits, required to choose the base point x0 . The above mentioned dichotomy argument reduces the security question to a sufficient full-rank condition on a test matrix, which we verify for our chosen points by observing a nondegeneracy property that exploits the distinct poles of the iterates. The dichotomy itself is implicit, for the case k = 2, in the linear-algebraic arguments of [MN+ 24], 2
and [Ngu25] later extends this to the case of general k, as well as to general linear code-based secret sharing. We also give an alternative direct derivation of the dichotomy in our setting for completeness, in Section A.
1.1
Motivation
The problem of derandomization of evaluation places is the central motivation for our work. The randomized constructions of [MN+ 21; MN+ 24] demonstrate that most evaluation places are secure. In practice, however, they require trusted public randomness, for instance a randomness beacon, to select the places. An adversary who can influence the random seed may steer the construction toward vulnerable evaluation places, unbeknownst to the honest parties. This concern is not merely theoretical; the NIST standardization effort for threshold cryptographic schemes (see Brandão and Peralta [BP23]), and the practical deployment considerations studied by Faust, Masure, Micheli, Orlt, and Standaert [FM+ 24] both underscore the need for deterministic, verifiable instantiations. Ideally, one would like evaluation places that are fixed by the field specification alone, with a proof that they resist physical bit probes. Towards this, [HM+ 25] initiated the study of classifier and derandomization constructions over prime fields. Their techniques, however, are inherently tied to the structure of prime fields: they exploit square wave orthogonality and 2-adic valuations of rational approximations, both of which rely on the nonlinearity of the bit-extraction map over Fp . Over composite fields Fpd with d ⩾ 2, the analogous coordinate-extraction map is Fp -linear, and the Fourier-analytic machinery of [HM+ 25] does not apply. The present work exploits this linearity to make partial progress on the derandomization problem in the composite-field setting; the precise results are stated in Section 1.2.
1.2
Our results
We work over F = Fpd , where p is any prime and d ⩾ 2. Fix a primitive polynomial Π(t) ∈ Fp [t] of degree d, and let α be a root of Π in F, so that ord(α) = pd − 1 and F = Fp [α] with canonical basis B = {1, α, α2 , . . . , αd−1 }. Our construction is based on a rational function. Define the step operator Φ(x) =
αx , x+1
which is a Möbius transformation on the projective line P1 (F) := F ∪ {∞} with projective order pd − 1. Our evaluation places are the iterates xj = Φj (x0 ),
j = 0, 1, . . . , n − 1,
where Φj denotes the j-th iterate of Φ under composition, applied to a base point x0 ∈ F∗ . The choice of Φ is not arbitrary. The single structural property of the orbit that drives the entire security analysis is that the iterates Φ0 , Φ1 , . . . , Φn−1 , viewed as Möbius transformations on the projective line P1 (F), have pairwise distinct poles: the pole of Φ0 = id is ∞, and the pole of Φj for j ⩾ 1 is a point of F∗ , these being distinct for distinct j. This pole-distinctness is what powers the partial fraction nondegeneracy argument in Section 4. In fact, motivated from the construction of folded Reed-Solomon codes [GR08], which are polynomial codes that can be list decoded up to the information theoretic limit, a more obvious and simpler candidate is Ψ(x) = αx. Here, every iterate Ψj (x) = αj x is a pure dilation with its only pole at ∞. So the iterates share a single 3
common pole and the partial fraction argument collapses entirely. We make this contrast precise in Remark 3.6. The role of the +1 in the denominator of Φ is therefore not cosmetic; it moves the pole of every non-identity iterate to a distinct point of F∗ , placing the orbit in sufficiently generic position so that a good bad-set bound becomes possible. Our main results are as follows. Theorem 1.1 (Perfect security against single-block leakage). Let p be any prime, d ⩾ 2, k ⩾ 2, and k ⩽ n ⩽ d(k − 1) with n ⩽ pd − 1. Let α be a multiplicative generator of F∗pd and Φ(x) = αx/(x + 1). There exists a set Bad ⊂ F∗pd with |Bad| ⩽ n + n(dp)n ⃗ = (x0 , . . . , xn−1 ) give a scheme such that for any x0 ∈ F∗pd \ Bad, the evaluation places X ⃗ F that is perfectly secure against all single-Fp -block leakage patterns. ShamirSS(n, k, X) pd In particular, the scheme is perfectly secure against all single-physical-bit-per-share leakage (for any p), and against any leakage that applies an arbitrary function gj : Fp → Sj to a single Fp -block of each share, where S0 , . . . , Sn−1 are arbitrary nonempty finite sets. A good base point x0 exists whenever d > n(1 + logp d) + logp (2n), giving a practical range of n = O d/ logp (pd) parties.
Theorem 1.1 is proved in Section 4. The bad set and perfect security are Theorem 4.5, the existence claim is Corollary 4.6, and the two particular claims are Proposition 4.7 and Corollary 4.8. The security guarantee is perfect: the statistical distance is zero, not merely exponentially small. Within the parameter range n = O(d/ logp d), this is a qualitative strengthening of the statistical security ϵ = 2−Ω(d) achieved by the randomized constructions of [MN+ 24; Ngu25]. The trade-off is on party count: [MN+ 24; Ngu25] support n = O(dk/ logp d) parties versus our n = O(d/ logp d), reflecting the cost of restricting the evaluation places to a one-parameter family. The construction is a partial derandomization. Once a base point x0 is fixed, the evaluation places xj = Φj (x0 ) are determined by the field representation alone; the randomness needed to specify the n places thus drops from nd log p bits (for n independent random places, as in [MN+ 24]) to d log p bits needed to fix the single x0 ∈ F∗ . In the headline regime, x0 = α is a structured candidate; whether it is good depends on the choice of primitive polynomial Π and is certified by Algorithm 1 (Section 3.3), a sound test whose good verdict guarantees perfect security, with the same worst-case runtime as the classifying algorithm of [Ngu25]. For multi-block leakage, we prove the following. Theorem 1.2 (Multi-block leakage, improved bound). Under the hypotheses of Theorem 1.1, fix an admissible multi-block leakage pattern with M < d − logp (2n) total Fp -blocks leaked. Then the bad set has size ⩽ n + n · pM , and a good x0 always exists. For universality over all admissible multi-block patterns with ⩽ M blocks total, we get the bound |Bad| ⩽ n + n(dpe)M , and a good x0 exists when M = O(d/ logp d). For the proof, we observe that the Vandermonde has nontrivial kernel, and the direct bound from Theorem 5.4 is used; obtaining a polynomial bound for this regime remains open (Section 1.6).
1.3
Comparison with prior work
Table 1 summarizes the comparison with [MN+ 24; Ngu25], and a few gaps remain. First, there is a factor-k loss in the maximum number of parties for large k; we conjecture this loss is inherent to single-parameter constructions, but leave the question open (Section 1.6). Second, multi-block 4
universality is limited to M = O(d/ logp d) by the pattern enumeration bottleneck. Closing these gaps, particularly by obtaining a polynomial bad-set bound, is an interesting direction for future work; see Section 1.6. [MN+ 24]
[Ngu25]
This work
Random in (F∗ )n
Fixed; arbitrary
Φj (x0 ) orbit
All 1
Random in (F∗ )n
All 1
Security guarantee
ϵ = 2−Ω(d)
ϵ = 2−Ω(d)
SD = 0 for x0 ∈ / Bad
Max parties (general k)
O(dk/ logp d)
O(dk/ logp d)
O(d/ logp d)
Multi-block, M < d
ϵ = 2−Ω(d)
ϵ = 2−Ω(d)
Perfect (fixed pattern)
Random bits in evaluation places
nd log p
0
d log p (for x0 )
Random bits in multipliers
0
nd log p
0
Aspect Evaluation places Multipliers vi (in shares vi P(Xi ))
Table 1: Comparison of our results with the randomized results of [MN+ 24; Ngu25]. Here 2 ⩽ k ⩽ n.
1.4
Related work
We survey the most relevant prior results. Leakage-resilient secret sharing. [BD+ 18; BD+ 21] proved that Shamir’s scheme is leakage-resilient against arbitrary single-bit local leakage when k/n exceeds a constant threshold. Subsequent works [MN+ 22; KK23; Ngu24] improved this threshold, with the current best being k ⩾ 0.69n. These results hold for all evaluation places but require a large reconstruction-to-party ratio. Among other lines of work that bring linear algebraic structure to bear on these problems, Koga and Abe [KA26] determine tight bounds on the local leakage resilience of the additive (n, n)threshold scheme via the eigenvalues of circulant matrices. The complementary regime (small k relative to n) is where the choice of evaluation places becomes critical. [MN+ 21] initiated the study of this regime over prime fields, and [MN+ 24] extended it to composite fields. Other constructions of leakage-resilient (non-Shamir) secret sharing, including those based on algebraic geometry codes, appear in [KMS19; MP+ 21] and the references therein. Physical bit probing and the [MN+ 24] framework. The closest prior randomized construction we build upon is [MN+ 24]. Their construction works over Fpd for any prime p and combines three ingredients: (i) a Fourier-analytic upper bound on statistical distance in terms of dual GRS codewords and Fourier coefficients of block-indicator functions, (ii) a Bézout-type bound on simultaneous zeros of polynomial systems over composite fields [Zha12; BS+ 21], and (iii) a generalized Vandermonde determinant analysis.
5
They also proved an exact security classifier for k = 2. Both the dichotomy at k = 2 and its proof technique (linear algebra plus the cosets-of-subspaces structure) are the entry point for our test-matrix derivation. The dichotomy result of [Ngu25]. A perfect-or-completely-insecure dichotomy for any linear code-based secret-sharing scheme was given by [Ngu25], over a binary extension field against arbitrary physical-bit leakage, along with a complete characterization of the insecure leakages via minimal codewords of the dual of the binary image. A remark therein also explicitly extends both results to composite order fields Fpd and to subfield-coordinate leakage, which is the present setting. The work also gives a classifying algorithm whose worst-case cost matches our verification cost (Proposition 3.12). Beyond the dichotomy, [Ngu25] gives a Monte-Carlo construction of GRS-based linear code-based secret sharing with random multipliers and fixed evaluation places, achieving M ⩽ (k − 1)λ/poly(log λ) bits of physical-bit leakage tolerance with overwhelming probability over the multiplier choice. Our contribution is complementary to [Ngu25] on the construction side. We give a construction of evaluation places xj = Φj (x0 ) using a suitable rational function Φ, that fixes both the multipliers (all equal to 1, as in standard Shamir’s scheme) and the evaluation places to a oneparameter family, with the security question reducing (via the dichotomy of [Ngu25]) to a closed form bad-set bound on the base point x0 . The trade-off is on party count: [Ngu25] supports n = O(dk/ logp d) parties; we support n = O(d/ logp d), reflecting the cost of restricting to a single-parameter family. Explicit constructions over prime fields. [HM+ 25] constructed efficient classifiers for evaluation places over Mersenne and Fermat primes in the n = k regime, connecting leakage resilience to orthogonality of square wave functions and 2-adic valuations of rational approximations. They provide explicit secure evaluation places for n = k = 2 and lift to n = k > 2 via a Fourier-analytic theorem. Their techniques are specific to prime fields, where bit extraction is a nonlinear map. Over composite fields, the analogous map is Fp -linear, enabling a fundamentally different (and in several respects simpler) approach. Acknowledgment. The author thanks the anonymous reviewers of ITC 2026 for critical feedback, as well as for pointing to [Ngu25] and the dichotomy result therein.
1.5
Technical overview
The proof proceeds in three phases. We outline each in turn. Phase 1: The perfect dichotomy (Section 2). The key structural observation is that the coordinate extraction map (·)i : F → Fp , defined by (x)i = Tr(x · f∗i ) where {f∗i } is the dual basis with respect to the field trace, is Fp -linear. It follows that the leakage map L⃗i : Fk−1 → Fn p is Fp -linear. This has a clean consequence. By the structure of cosets of Fp -subspaces, the leakage distribution for secret s is uniform over a coset of Im(L⃗i ). Two cosets are either identical or disjoint, yielding the dichotomy SD ∈ {0, 1}. Consequently, surjectivity of L⃗i , equivalently a test matrix Θ⃗i having full column rank n over Fp , is a sufficient condition for perfect security against the pattern ⃗i, since it forces every coset to equal Fn ⃗ p . (Perfect security against i is in fact the weaker condition that the secret’s coordinate vector ((s)ij )j lies in Im(L⃗i ) for every s, which is the minimal codeword 6
characterization of [Ngu25, Theorem 6]; see also [MN+ 24, Theorem 5] for the k = 2 case. We use only the sufficient direction.) An alternative derivation of the dichotomy SD ∈ {0, 1} in our setting is given in Section A. The rank criterion is the working tool for the rest of the proof. Phase 2: partial fraction nondegeneracy (Section 4). The test matrix Θ⃗i encodes the map ⃗c 7→ P ( j cj η(ij ) xℓj )k−1 . To show full rank, we must prove that no nontrivial Fp -linear combination P ℓ=1 (i j Gℓ (x) = j cj η ) (Φj (x))ℓ vanishes identically. The argument is a partial fraction analysis. Since the Möbius transforms Φ0 , Φ1 , . . . , Φn−1 have pairwise distinct poles (Corollary 3.4), the residue of Gℓ at each pole is determined by a single summand. This pole-distinctness is the unique structural property of the orbit on which the entire argument hinges; Remark 3.6 shows that the naive alternative Ψ(x) = αx fails exactly here. If Gℓ ≡ 0, all coefficients must vanish. The resulting zero count ⩽ nℓ at the smallest power ℓ = 1 gives ⩽ n bad base points per coefficient vector, and a union bound over all patterns and coefficients yields the bad set of Theorem 1.1. Phase 3: Multi-block extension (Section 5). P
For multi-block leakage, the kernel condition in-
(r)
volves F-valued coefficients dj = r cj,r η arising from within-share linear combinations. The admissibility of the leakage pattern ensures that dj ̸= 0 whenever the corresponding cj,r are not all zero. Once this is established, the partial fraction argument extends directly to F-coefficients.
1.6
(ij )
Discussion and open problems
It is worth recording what our proofs will actually rely on regarding the step operator Φ. (1) Rational function structure: each Φj is a degree-1 rational function, which will enable the partial fraction analysis in Section 4. (2) Distinct poles: Φ0 , . . . , Φn−1 have pairwise distinct poles in P1 (F), which is the hypothesis driving our nondegeneracy lemma. Several natural questions remain. Open Question 1.3 (Universal multi-block for 2 ⩽ k ⩽ n and M = ω(d/ logp d)). The pattern enumeration bottleneck limits universality to M = O(d/ logp d). Can this be overcome? Open Question 1.4 (Polynomial-size bad set). For a fixed admissible pattern, the Vandermonde matrix of evaluation places has nontrivial kernel, and the bad-set bound ⩽ n · pM from Theorem 5.4 is exponential in M. Can this be improved to a polynomial bound? Open Question 1.5 (Factor-k gap). The randomized constructions of [MN+ 24; Ngu25] handle n = O(dk/ logp d) parties; our single-parameter construction handles n = O(d/ logp d). Can this be overcome?
2
Preliminaries
Throughout, p denotes a prime and d ⩾ 2 an integer. We write F = Fpd and F∗ = F \ {0}. The security parameter is λ = d log2 p.
7
2.1
The field and coordinates
Fix a primitive polynomial Π(t) ∈ Fp [t] of degree d. Then F = Fp [t]/Π(t), and a root α of Π satisfies ord(α) = pd − 1, i.e., α generates F∗ . The canonical basis of F over Fp is B = Pd−1 i {1, α, α2 , . . . , αd−1 }. Every x ∈ F is uniquely written as x = i=0 xi α with xi ∈ Fp , and we define the i-th Fp -coordinate of x by (x)i := xi . Definition 2.1 (Dual basis and shifting factors). Let Tr := TrF/Fp denote the field trace. The dual basis of B with respect to Tr is the unique basis {f∗0 , f∗1 , . . . , f∗d−1 } of F over Fp satisfying Tr(αi · f∗j ) = δij for all i, j. The shifting factors are η(i) := f∗i /f∗0 for i = 0, 1, . . . , d − 1. In particular, η(0) = 1. The dual basis exists and is unique because the Gram matrix Gij = Tr(αi · αj ) is invertible (by nondegeneracy of the trace form). Fact 2.2 (Coordinates via the trace). For all x ∈ F and all i ∈ {0, . . . , d − 1} we have (x)i = Tr(x · f∗i ). In particular each coordinate map (·)i : F → Fp is Fp -linear. P
m with (x) Proof. Write x = d−1 ∈ Fp . Since Tr is Fp -linear and Tr(αm · f∗i ) = δmi m=0 (x)m α Pd−1 m ∗ (Definition 2.1), we get Tr(x · fi ) = m=0 (x)m Tr(αm · f∗i ) = (x)i . Linearity is then immediate from that of Tr.
Proposition 2.3 (Shift property). For all x ∈ F and all i ∈ {0, . . . , d − 1}, (x)i = (x · η(i) )0 .
Proof. We compute (x · η(i) )0 = Tr(x · η(i) · f∗0 ) = Tr(x · (f∗i /f∗0 ) · f∗0 ) = Tr(x · f∗i ) = (x)i . Lemma 2.4 (Fp -independence of shifting factors). The shifting factors η(0) , η(1) , . . . , η(d−1) are Fp linearly independent. In fact, they form a basis of F over Fp . Proof. The dual basis {f∗0 , . . . , f∗d−1 } is a basis of F over Fp . The map f∗i 7→ η(i) = f∗i /f∗0 is multiplication by the nonzero scalar 1/f∗0 ∈ F∗ , hence an Fp -linear isomorphism of F.
2.2
Shamir’s secret sharing and leakage models
Definition 2.5 (Shamir’s scheme). Let 2 ⩽ k ⩽ n. Given distinct evaluation places x0 , . . . , xn−1 ∈ ⃗ F shares a secret s ∈ F as follows: sample P(x) = s + a1 x + F∗ , the scheme ShamirSS(n, k, X) k−1 · · · + ak−1 x with a1 , . . . , ak−1 ∈ F uniform and independent, and output shares sj = P(xj ) for j = 0, . . . , n − 1. Definition 2.6 (Block leakage). In the single-block leakage model, the adversary learns one Fp coordinate (sj )ij ∈ Fp from each share sj , where the block indices ⃗i = (i0 , . . . , in−1 ) ∈ {0, . . . , d − 1}n are adversary-chosen (non-adaptively). For p = 2, each Fp -block is a single bit, so block leakage coincides with physical bit leakage. Definition 2.7 (Multi-block leakage). In the multi-block leakage model, the adversary learns mj ⩾ 1 (m ) (1) distinct Fp -coordinates from share j, at positions ij , . . . , ij j ∈ {0, . . . , d − 1}. The total number Pn−1 of blocks leaked is M = j=0 mj . A multi-block pattern is admissible if the block positions within each share are distinct. ⃗ F against a leakage family F is Definition 2.8 (Insecurity). The insecurity of ShamirSS(n, k, X) ⃗ := max max SD(f(Share(0)), f(Share(s))), ϵF (X) ∗ f∈F s∈F
⃗ = 0. where SD denotes statistical distance. We say the scheme is perfectly secure against F if ϵF (X)
8
2.3
The perfect dichotomy
We now record the structural foundation that the rest of the analysis builds on: the coordinate map (·)i = Tr(· · f∗i ) is Fp -linear, which makes the leakage map linear, forces the leakage distribution to be uniform on a coset of an Fp -subspace, and yields a perfect dichotomy for statistical distance. Proposition 2.9 (Leakage map). For block leakage with indices ⃗i, the leakage vector ⃗ℓ = ((sj )ij )n−1 j=0 decomposes as ℓj = (s)ij +
k−1 X
Tr(at · xtj · f∗ij ),
t=1
where the map L⃗i : Fk−1 → Fn p defined by L⃗i (a1 , . . . , ak−1 )j = in Section A.)
Pk−1
t ∗ t=1 Tr(at · xj · fij ) is Fp -linear. (Proof
Proposition 2.10 (Perfect dichotomy). For block leakage with indices ⃗i and any two secrets s, s ′ ∈ F:
SD(⃗ℓ|s , ⃗ℓ|s ′ ) =
0
if ⃗v(s) − ⃗v(s ′ ) ∈ Im(L⃗i )
1
if ⃗v(s) − ⃗v(s ′ ) ∈ / Im(L⃗i )
where ⃗v(s) = ((s)i0 , . . . , (s)in−1 ). In particular, if L⃗i is surjective, then SD = 0 for all pairs of secrets. (Proof in Section A.) Remark 2.11 (More general result in previous work). [Ngu25, Theorem 6] establishes Proposition 2.10 in much greater generality: for any linear code-based secret-sharing scheme over an extension field Fpλ , against arbitrary physical-bit leakage. By a remark therein, the result also applies to composite order fields Fpd and to subfield-coordinate leakage, which is our present setting. The k = 2 case is also implicit, via linear algebra, in [MN+ 24, Theorem 5]. For completeness, proofs of Propositions 2.9 and 2.10 in our setting are deferred to Section A; the rest of the paper depends only on the conclusion of Proposition 2.10.
2.4
Surjectivity and the test matrix
Proposition 2.12 (Dual characterization). The map L⃗i is surjective if and only if the adjoint L⃗∗i : Fn p → k−1 F is injective. The adjoint is given by (L⃗∗i (⃗c))ℓ = f∗0 ·
n−1 X
cj · η(ij ) · xℓj ,
ℓ = 1, . . . , k − 1.
j=0
⃗ Since f∗0 ̸= 0, injectivity of L⃗∗i is equivalent to: for all ⃗c ∈ Fn p \ {0}, there exists ℓ ∈ {1, . . . , k − 1} with P (i ) ℓ j x ̸= 0. j cj η j
Proof. For an Fp -linear map L : V → W between finite-dimensional Fp -vector spaces, equipped with nondegenerate Fp -bilinear pairings, L is surjective if and only if its adjoint L∗ is injective. Indeed ker(L∗ ) = Im(L)⊥ , and nondegeneracy gives dim(Im(L)⊥ ) = dim(W) − dim(Im(L)), so Im(L) = W iff ker(L∗ ) = {0}. Both pairings below are nondegenerate. The standard one on Fn p, and the trace pairing on Fk−1 , because the trace form of F/Fp is nondegenerate.
9
For the formula, we compute the adjoint explicitly. The relevant inner products are the stanP P dard Fp -inner product ⟨⃗c, ⃗y⟩Fp = j cj yj on Fn a, ⃗b⟩ = k−1 p , and the trace pairing ⟨⃗ ℓ=1 Tr(aℓ bℓ ) on k−1 k−1 n F . For any a ⃗ ∈F and ⃗c ∈ Fp : a)⟩Fp = ⟨⃗c, L⃗i (⃗
=
n−1 X
k−1 X
cj
j=0
t=1
k−1 X
Tr(at xtj f∗ij )
Tr at
n−1 X
t=1
cj xtj f∗ij ,
j=0
where we used Fp -linearity of Tr and the fact that cj ∈ Fp can be moved inside Tr. Now substituting f∗ij = η(ij ) · f∗0 : =
k−1 X
Tr at · f∗0 ·
t=1
n−1 X
*
cj η(ij ) xtj =
a ⃗ , f∗0 ·
j=0
n−1 X
k−1 + cj η(ij ) xℓj
j=0
.
ℓ=1
P
Since this holds for all a ⃗ , we conclude (L⃗∗i (⃗c))ℓ = f∗0 · j cj η(ij ) xℓj . P Finally, since f∗0 ̸= 0 (it is a dual basis element), L⃗∗i (⃗c) = 0 in Fk−1 if and only if j cj η(ij ) xℓj = 0 for every ℓ = 1, . . . , k − 1.
d(k−1)×n
Definition 2.13 (Test matrix). For block indices ⃗i ∈ {0, . . . , d − 1}n , the test matrix Θ⃗i ∈ Fp is the Fp -coordinate representation of the map k−1
n−1 X
⃗c 7→
∼ Fp ∈ Fk−1 =
d(k−1)
cj η(ij ) xℓj
j=0
.
ℓ=1
Corollary 2.14. L⃗i is surjective if and only if rankFp (Θ⃗i ) = n. Since Θ⃗i has only d(k − 1) rows, this (sufficient) full-rank condition can hold only when n ⩽ d(k − 1), the regime in which we work. Proof. By Proposition 2.12, L⃗i is surjective if and only if L⃗∗i is injective, which holds if and only if the Fp -linear map encoded by Θ⃗i has trivial kernel, i.e., rankFp (Θ⃗i ) = n. Since Θ⃗i has d(k − 1) rows, full column rank requires n ⩽ d(k − 1).
3
The construction
We now define the step operator and establish the properties of the orbit {xj = Φj (x0 )} that will be needed for the security analysis. The required properties of this operator follow from elementary algebra, with no conditions to verify beyond x0 ∈ / {α − 1} ∪ Poles(n).
3.1
The step operator
Definition 3.1 (Step operator). Define Φ : P1 (F) → P1 (F) by Φ(x) =
αx , x+1
∗ where α is the ! generator of F from Section 2.1. As a Möbius transformation, Φ has matrix
MΦ =
α 0 1 1
with det(MΦ ) = α ̸= 0.
10
Proposition 3.2 (Projective order). The projective order of Φ equals ord(α) = pd − 1. Proof. The eigenvalues of MΦ =
α 0 1 1
!
are α and 1 (reading off the diagonal, since MΦ is lower
triangular). Hence MjΦ has eigenvalues αj and 1. Now Φj = id in PGL2 (F) if and only if MjΦ = λI for some λ ∈ F∗ (since projective transformations are defined up to scalar multiples of the matrix). The condition MjΦ = λI requires both eigenvalues to be equal, i.e., αj = 1. Conversely, if αj = 1, then both eigenvalues equal 1 and MjΦ must be the identity (since MΦ is diagonalizable over the algebraic closure: its eigenvalues α and 1 are distinct for d ⩾ 2, so MΦ , and hence MjΦ , is diagonalizable). The smallest positive j with αj = 1 is ord(α) = pd − 1. Proposition 3.3 (Explicit formula for iterates). For j ⩾ 1, Φj (x) =
αj x , Cj x + 1
αj − 1 X i = α. α−1 j−1
Cj :=
i=0
For j = 0 the formula holds with C0 = 0, giving Φ0 (x) = x. We use this convention throughout, so that Φ0 is the unique iterate whose pole is at ∞. Proof. By induction on j. For j = 1: C1 = 1 and Φ(x) = αx/(x + 1). For the inductive step: j
j+1
Φ
j
(x) = Φ(Φ (x)) =
x α · Cα j x+1 αj x Cj x+1 + 1
=
αj+1 x . (αj + Cj )x + 1
It remains to verify that αj + Cj = Cj+1 . Indeed, αj + (αj − 1)/(α − 1) = (αj+1 − αj + αj − 1)/(α − 1) = (αj+1 − 1)/(α − 1) = Cj+1 .
3.2
Distinct poles, fixed points, and pole avoidance
Corollary 3.4 (Pairwise distinct poles). For 0 ⩽ j ⩽ n − 1 with n ⩽ pd − 1, the Möbius transforms Φ0 , Φ1 , . . . , Φn−1 have pairwise distinct poles in P1 (F). More precisely, the pole of Φ0 = id is ∞, and the pole of Φj for j ⩾ 1 is −(α − 1)/(αj − 1). Proof. By Proposition 3.3, the pole of Φj for j ⩾ 1 is at x = −1/Cj = −(α − 1)/(αj − 1). For 1 ⩽ j < ′ j ′ ⩽ n − 1, these coincide if and only if αj = αj , i.e., j ≡ j ′ (mod pd − 1). Since 0 < j < j ′ < pd − 1, this is impossible. The pole of Φ0 = id is ∞, which is distinct from all finite poles. Remark 3.5 (No involution). The map Φ is never an involution for d ⩾ 2, regardless of characteristic. Indeed, Φ2 = id would require α2 = 1, but ord(α) = pd − 1 ⩾ p2 − 1 ⩾ 3. In particular, no special treatment is needed for p = 2. Remark 3.6 (A naive dilation fails). Deriving motivation from constructions of polynomial codes with optimal list decoding properties (folded Reed-Solomon codes [GR08]), the most obvious oneparameter candidate is the pure dilation Ψ(x) = αx, whose iterates Ψj (x) = αj x form an orbit xj = αj x0 on the multiplicative coset x0 ⟨α⟩. We record here that this choice fails the structural property driving our analysis, and consequently does not admit the bad-set bound of Theorem 4.5. The functions Ψj are affine, so each has its only pole at ∞. Hence all n iterates share a single common pole, and the pole-distinctness hypothesis of Corollary 3.4 fails completely (rather than failing for at most one j). The partial fraction argument of Section 4 therefore has no effect, since 11
P
P
the rational function Gℓ (x) = j cj η(ij ) (αj x)ℓ = xℓ · j cj η(ij ) αjℓ is a monomial in x, and Gℓ ≡ 0 is P equivalent to the x0 -independent condition j cj η(ij ) αjℓ = 0. The starting point x0 has dropped out of the rank condition entirely. In other words, the test matrix Θ⃗i is the same matrix for every x0 ∈ F∗ , so the dilation scheme is either secure for all nonzero x0 or for none – there is no parameter to optimize and no closed-form bad-set bound to prove. In particular, the central quantitative result |Bad| ⩽ n + n(dp)n of Theorem 4.5 has no analoguefor Ψ. The role of the +1 in the denominator of Φ is thus to perturb each nontrivial iterate’s pole away from ∞ to a distinct finite point of F∗ (Corollary 3.4), placing the orbit in generic position relative to the partial fraction decomposition. This is the essential algebraic feature that distinguishes Φ from its affine cousin and makes the closed-form bad-set bound possible. Lemma 3.7 (Fixed points). For each 1 ⩽ j < pd − 1, the fixed points of Φj in P1 (F) are exactly {0, α − 1}. In particular, ShortPeriod(n) := {x0 ∈ F∗ : ∃ 1 ⩽ j < n, Φj (x0 ) = x0 } = {α − 1}. Proof. Fix 1 ⩽ j < pd − 1, so that Φj ̸= id by Proposition 3.2. The fixed-point equation Φj (x) = x reads αj x/(Cj x + 1) = x. For x = 0: Φj (0) = 0, so 0 is a fixed point, but 0 ∈ / F∗ . For x ̸= 0: dividing both sides by x gives αj /(Cj x + 1) = 1, hence x = (αj − 1)/Cj . Since Cj = (αj − 1)/(α − 1), this gives x = α − 1. For x = ∞: Φj (∞) = αj /Cj ̸= ∞ (since Cj ̸= 0 for j < pd − 1). The fixed-point set {0, α − 1} is independent of j, so restricting to F∗ gives ShortPeriod(n) = {α − 1}. Definition 3.8 (Pole set). Define Poles(n) := {−1/Cj : 1 ⩽ j ⩽ n − 1} ⊂ F∗ . These are pairwise distinct by Corollary 3.4, so |Poles(n)| = n − 1. We note that Poles(n) ∩ {α − 1} = ∅: the equality α − 1 = −(α − 1)/(αj − 1) would require αj = 0, which is impossible. Proposition 3.9 (Distinct evaluation places). For x0 ∈ F∗ \ ({α − 1} ∪ Poles(n)) and n ⩽ pd − 1, the evaluation places x0 , x1 , . . . , xn−1 are pairwise distinct elements of F∗ . Proof. We verify three properties. (a) Each xj ∈ F∗ : xj = 0 if and only if x0 = 0 (since 0 is a fixed point of Φ), which is excluded by x0 ∈ F∗ . xj = ∞ if and only if x0 = −1/Cj ∈ Poles(n), which is excluded by hypothesis. (b) The orbit avoids α − 1: Since α − 1 is a fixed point of Φ itself (not just of Φj ), we have Φ−1 ({α − 1}) = {α − 1}, and hence xj = α − 1 if and only if x0 = α − 1, which is ′ excluded. (c) Pairwise distinct: xj = xj ′ for j < j ′ if and only if xj is a fixed point of Φj −j in F∗ . By Lemma 3.7, the only such point is α − 1, and by (b), xj ̸= α − 1. Remark 3.10. The total number of structural exclusions is |{α − 1} ∪ Poles(n)| = n. Remark 3.11 (Canonical base point). The generator α is a natural canonical candidate for the base point. Two layers of the goodness condition should be distinguished. Provably: α avoids the structural exclusion set {α − 1} ∪ Poles(n). Indeed, α ̸= α − 1 (since 1 ̸= 0), and α ∈ Poles(n) would require αj+1 = 1 for some 1 ⩽ j ⩽ n − 1, which is impossible whenever n ⩽ pd − 2. Verification is O(n). Not provably without verification: whether α avoids the security-bad set in the headline singleblock regime of Theorem 4.5 requires running the classifier of Algorithm 1.
3.3
Classifier and choice of base point
We now give an explicit classifier that, given a candidate base point x0 , tests the sufficient full-rank condition of Corollary 2.14 for the resulting evaluation places xj = Φj (x0 ): for each block-index tuple ⃗i ∈ {0, . . . , d − 1}n it checks whether the test matrix Θ⃗i has full column rank n over Fp , 12
returning good only if all of them do. A good verdict certifies perfect security against singleblock leakage, so the classifier is a sound tester. A bad (⃗i) verdict reports a pattern at which the full-rank certificate fails; since full rank is sufficient but not necessary (Proposition 2.10), this does not by itself certify insecurity. On the structured Möbius candidates we propose, this sound test is what we use to certify goodness; we do not claim it decides perfect security on arbitrary evaluation places, for which the exact criterion is the containment/minimal-codeword condition of [Ngu25, Theorem 6]. Input: prime p, integer d ⩾ 2, reconstruction threshold k ⩾ 2, number of parties n ⩽ d(k − 1), field representation F = Fp [α], candidate base point x0 ∈ F∗ . Output: good (certifies perfect security), or bad(⃗i) where ⃗i is a pattern at which the sufficient full-rank certificate fails. if x0 ∈ {α − 1} ∪ Poles(n) then return bad(⊥) // structural exclusion end Compute xj ← Φj (x0 ) for j = 0, . . . , n − 1 Compute the dual basis {f∗0 , . . . , f∗d−1 } and shifting factors η(i) = f∗i /f∗0 for ⃗i ∈ {0, . . . , d − 1}n do d(k−1)×n Build Θ⃗i ∈ Fp as in Definition 2.13 if rankFp (Θ⃗i ) < n then return bad(⃗i) end end return good Algorithm 1: Classify(p, d, k, n, x0 ): single-block-leakage classifier for the Möbius orbit xj = Φj (x0 ). Proposition 3.12 (Classifier complexity). Algorithm 1 performs O(dn · n2 · dk) arithmetic operations over Fp , after preprocessing costing poly(d, n, k, log p) operations. Proof. The structural exclusion check takes O(n) time. Preprocessing. Compute the orbit x0 , . . . , xn−1 , the dual basis, and the shifting factors, and then tabulate once the dn(k − 1) field elements η(i) xℓj (0 ⩽ i ⩽ d − 1, 0 ⩽ j ⩽ n − 1, 1 ⩽ ℓ ⩽ k − 1) together with their Fp -coordinate vectors. This costs O(dnk) multiplications in F, i.e. poly(d, n, k, log p) operations over Fp , and is performed outside the main loop. Main loop. Iterate dn times. Each iteration assembles Θ⃗i by table lookup in O(ndk) operations over Fp , and computes its rank by Gaussian elimination in O(n2 · d(k − 1)) = O(n2 dk) operations over Fp . No enumeration over coefficient vectors ⃗c ∈ Fn p is needed, since the rank test handles all ⃗c per pattern simultaneously. Algorithm 1 matches the cost of the classifying algorithm given by Nguyen [Ngu25, Fig. 1] on the corresponding inputs. Our contribution in this regard is therefore not a faster verification algorithm; rather, the classifier exists here as a tool to certify the structured Möbius candidates we propose, complementing the closed form bad-set bounds.
13
4
Single-block security
The goal of this section is to prove that for all but a small number of base points x0 , the test matrix Θ⃗i has full column rank for every block-index tuple ⃗i. The main tool is a partial fraction nondegeneracy lemma, which exploits the fact that the Möbius transforms Φ0 , . . . , Φn−1 have pairwise distinct poles. Throughout the section we write, for ⃗i ∈ {0, . . . , d − 1}n , ⃗c ∈ Fn p and ℓ ⩾ 1, Gℓ (x;⃗i, ⃗c) :=
n−1 X
cj η(ij ) (Φj (x))ℓ ∈ F(x),
j=0
which is the function Gℓ of Lemma 4.1 specialized to ψj = Φj and δj = η(ij ) .
4.1
Nondegeneracy via partial fractions
Lemma 4.1 (nondegeneracy). Let ψ0 , . . . , ψn−1 be Möbius transforms on P1 (F) with pairwise distinct poles. Let δ0 , . . . , δn−1 ∈ F∗ , c0 , . . . , cn−1 ∈ Fp with ⃗c ̸= ⃗0, and ℓ ⩾ 1. Then Gℓ (x) :=
n−1 X
cj δj (ψj (x))ℓ
j=0
is not identically zero as a rational function on P1 (F). Proof. Write ψj (x) = (Aj x + Bj )/(Cj x + Dj ) with Aj Dj − Bj Cj ̸= 0. The poles pj = −Dj /Cj (for Cj ̸= 0) or pj = ∞ (for Cj = 0) are pairwise distinct by hypothesis, so at most one equals ∞. Case A All poles are finite (Cj ̸= 0 for all j). Near the pole pj , ψj (x) has a simple pole with residue rj = −(Aj Dj − Bj Cj )/C2j ̸= 0. Consequently, (ψj (x))ℓ has a pole of order ℓ at pj with leading Laurent coefficient rℓj ̸= 0. Since the poles are pairwise distinct, the leading term of Gℓ at pj comes only from the j-th summand: Gℓ (x) ∼ cj δj rℓj /(x − pj )ℓ as x → pj . If Gℓ ≡ 0, then cj δj rℓj = 0 for all j. Since δj ̸= 0 and rj ̸= 0, this forces cj = 0 for all j, contradicting ⃗c ̸= ⃗0. Case B One pole is at ∞ (say C0 = 0, so that ψ0 is affine; all other Cj ̸= 0). The residue argument at each finite pole pj (j ⩾ 1) gives cj δj rℓj = 0, hence cj = 0 for all j ⩾ 1. Then Gℓ (x) = c0 δ0 (ψ0 (x))ℓ . Since ψ0 is nonconstant (A0 /D0 ̸= 0 because det(M0 ) ̸= 0 and C0 = 0), δ0 ̸= 0, and c0 ̸= 0 (as ⃗c ̸= ⃗0), this is not identically zero. At most one pole equals ∞, so Cases A and B are exhaustive. Corollary 4.2 (Zero bound). Under the hypotheses of Lemma 4.1, Gℓ has at most nℓ zeros in P1 (F). Proof. Write ψj (x) = (Aj x + Bj )/(Cj x + Dj ). Let S = {j : Cj ̸= 0} and T = {j : Cj = 0}, so |T | ⩽ 1 (at most one pole can be ∞). Define the common denominator D(x) =
Y (Cj x + Dj )ℓ , j∈S
and set N(x) = Gℓ (x) · D(x). We compute the degree of N(x). For j ∈ S: the j-th summand of Gℓ is cj δj (Aj x + Bj )ℓ /(Cj x + Dj )ℓ . After multiplying by D(x), the Q denominator (Cj x + Dj )ℓ cancels, contributing to N(x) the term cj δj (Aj x + Bj )ℓ j ′ ∈S, j ′ ̸=j (Cj ′ x + Dj ′ )ℓ , of degree at most ℓ + ℓ(|S| − 1) = ℓ|S|.
14
For j ∈ T : we have Cj = 0, so ψj (x) = (Aj /Dj )x + Bj /Dj is affine (with Aj /Dj ̸= 0). The j-th summand of Gℓ is cj δj ((Aj /Dj )x + Bj /Dj )ℓ , a polynomial of degree ℓ. After multiplying by Q D(x) = j ′ ∈S (Cj ′ x + Dj ′ )ℓ , which has degree ℓ|S|, the contribution is a polynomial of degree ℓ + ℓ|S|. Since |S| + |T | = n: if T = ∅, then |S| = n and deg(N) ⩽ ℓn. If |T | = 1, then |S| = n − 1 and deg(N) ⩽ max(ℓ(n − 1), ℓ + ℓ(n − 1)) = ℓn. In both cases deg(N) ⩽ nℓ, and deg(D) = ℓ|S| ⩽ nℓ. Since Gℓ ̸≡ 0 by Lemma 4.1, we have N ̸≡ 0. Every zero of Gℓ lying in F is a root of N (evaluate N = Gℓ D there), so Gℓ has at most deg(N) ⩽ nℓ zeros in F — which is all we use below. For the count in P1 (F), recall that a nonzero rational function R = N/D ∈ F(x) has exactly deg R = max(deg N, deg D) zeros in P1 (F), counted with multiplicity; here deg N ⩽ nℓ and deg D = ℓ|S| ⩽ nℓ, so Gℓ has at most nℓ zeros in P1 (F) as well.
4.2
Full rank of the test matrix
Theorem 4.3. Let p be any prime, d ⩾ 2, and 2 ⩽ k ⩽ n ⩽ d(k − 1) with n ⩽ pd − 1. For any ⃗i ∈ {0, . . . , d − 1}n and ⃗c ∈ Fn ⃗ p \ {0}, we have |{x0 ∈ F \ Poles(n) : ∗
n−1 X
cj η(ij ) (Φj (x0 ))ℓ = 0 ∀ ℓ = 1, . . . , k − 1}| ⩽ n.
j=0
Proof. Apply Lemma 4.1 with ℓ = 1, ψj = Φj , and δj = η(ij ) . By Corollary 3.4, the Φj have pairwise distinct poles. The shifting factors η(ij ) are nonzero (being ratios of dual basis elements). So P G1 (x) = j cj η(ij ) Φj (x) ̸≡ 0, and by Corollary 4.2, G1 has at most n zeros in P1 (F). The bad set is contained in {x0 ∈ F∗ : G1 (x0 ) = 0}, which has size ⩽ n. Remark 4.4. The bound ⩽ n comes from the ℓ = 1 case alone. The bad set requires Gℓ = 0 for all ℓ, and the containment in the zero set of G1 already suffices. Theorem 4.5 (Perfect security against single-block leakage). Let p be any prime, d ⩾ 2, and 2 ⩽ k ⩽ n ⩽ d(k − 1) with n ⩽ pd − 1. Define Bad := {α − 1} ∪ Poles(n) ∪
[
[
{x0 ∈ F∗ : G1 (x0 ;⃗i, ⃗c) = 0}.
⃗ ⃗i∈{0,...,d−1}n ⃗ c∈Fn p \{0}
Then |Bad| ⩽ n + n(dp)n . For any x0 ∈ F∗ \ Bad: (a) x0 , . . . , xn−1 are pairwise distinct elements of F∗ . ⃗ F is perfectly secure against all single-block leakage. (b) ShamirSS(n, k, X)
Proof. Part (a) follows from Proposition 3.9, since x0 ∈ / {α − 1} ∪ Poles(n). For part (b): by the security reduction (Corollary 2.14), we need rankFp (Θ⃗i ) = n for every block-index tuple ⃗i ∈ {0, . . . , d − 1}n . By Proposition 2.12, this fails for ⃗i if and only if there exists P (ij ) xℓ = 0 for all ℓ = 1, . . . , k − 1. For each such pair (⃗i, ⃗ ⃗ ⃗c ∈ Fn c), Theorem 4.3 p \ {0} with j cj η j bounds the set of bad base points by ⩽ n. We now count. The structural exclusion set {α − 1} ∪ Poles(n) has size n (by Remark 3.10). The number of block-index tuples is |{0, . . . , d − 1}n | = dn . The number of nonzero coefficient vectors n ⃗ is |Fn p \ {0}| = p − 1. By Theorem 4.3, each pair contributes at most n bad base points. By the union bound: |Bad| ⩽ n + dn · (pn − 1) · n ⩽ n + n · dn · pn = n + n(dp)n . 15
For any x0 ∈ F∗ \ Bad: by construction, x0 avoids the structural exclusion set (ensuring part (a)) and, for every ⃗i and every nonzero ⃗c, there exists ℓ with Gℓ (x0 ;⃗i, ⃗c) ̸= 0. This means Θ⃗i has trivial kernel for every ⃗i, i.e., full column rank n. By Corollary 2.14, L⃗i is surjective for all ⃗i, and by Proposition 2.10, SD = 0 for all pairs of secrets and all block-leakage patterns. n ; a sufficient condition is Corollary 4.6 (Existence). A good x0 exists whenever pd − 1 > n + n(dp) d > n 1 + logp d + logp (2n), which gives the range n = O d/ logp (pd) = O d/(1 + logp d) .
4.3
Physical bit security
Proposition 4.7 (Block security implies sub-block security). Let S0 , . . . , Sn−1 be arbitrary nonempty ⃗ F is finite sets, assume the hypotheses of Theorem 4.5, and let x0 ∈ F∗ \ Bad. Then ShamirSS(n, k, X) perfectly secure against any leakage that applies an arbitrary function gj : Fp → Sj to a single Fp -block of each share. Proof. By Theorem 4.5, for every block-index tuple (i0 , . . . , in−1 ) ∈ {0, . . . , d − 1}n , the map L⃗i is surjective. By Proposition 2.10, this means the leakage vector ((P(X0 ))i0 , . . . , (P(Xn−1 ))in−1 ) ∈ Fn p has the same distribution for every secret s ∈ F: it is uniform over Fn p. Now suppose the adversary applies deterministic functions gj : Fp → Sj to obtain (g0 ((P(X0 ))i0 ), . . . , gn−1 ((P(Xn−1 ))in−1 )). Since each gj is a fixed function, this post-processed leakage is a deterministic function of ((P(xj ))ij )n−1 j=0 . By the data processing inequality for statistical ′ distance, for any two secrets s, s : SD (gj ((P(xj ))ij ))j s, (gj ((P(xj ))ij ))j s ′ ⩽ SD ((P(xj ))ij )j s, ((P(xj ))ij )j s ′ = 0.
Hence perfect security is preserved under arbitrary post-processing. Corollary 4.8 (Physical bit security, all characteristics). Assume the hypotheses of Theorem 4.5 and let x0 ∈ F∗ \ Bad. For any prime p, if the adversary leaks one physical bit per share (from an arbitrary ⃗ F is perfectly secure. Fp -block, possibly a different block for each share), then ShamirSS(n, k, X) Proof. Each share is stored as d blocks over Fp , each block as a ⌈log2 p⌉-bit string, so a physical bit bitrj ((P(xj ))ij ) is a function gj : Fp → {0, 1} of the single block (P(xj ))ij . By Theorem 4.5, the scheme is perfectly secure against single-block leakage, so the claim follows from Proposition 4.7.
5
Multi-block security
We now extend the analysis to the multi-block setting, where the adversary probes multiple Fp coordinates from each share.
5.1
Setup P
For an admissible multi-block leakage pattern with M = n−1 j=0 mj ⩽ d(k − 1) total blocks, index the leaked coordinates by the M pairs (j, r), where 0 ⩽ j ⩽ n − 1 and 1 ⩽ r ⩽ mj . The development of Sections 2.3 and 2.4 goes through with the single index j replaced by the pair (j, r), the block (r) index ij replaced by ij , and n replaced by M. We record the outcome. Proposition 5.1 (Multi-block reduction). With the pattern as above, write ⃗ℓ = (sj )i(r) j,r ∈ FM p . Then:
j
16
(a) ℓj,r = (s)i(r) + L(⃗a)j,r , where L : Fk−1 → FM a)j,r = p , given by L(⃗
Pk−1
t ∗ t=1 Tr(at · xj · fi(r) ), is Fp -
j
j
linear; (b) SD(⃗ℓ|s , ⃗ℓ|s ′ ) ∈ {0, 1} for all s, s ′ ∈ F, and SD = 0 whenever L is surjective; d(k−1)×M
(c) L is surjective if and only if the test matrix Θ ∈ Fp tation of ⃗c 7→
n−1 mj XX
(r)
cj,r η(ij ) xℓj
k−1
, defined as the Fp -coordinate represen-
∼ Fp ∈ Fk−1 =
d(k−1)
,
ℓ=1
j=0 r=1
has full column rank M. Proof. The proofs of Propositions 2.9, 2.10 and 2.12 and Corollary 2.14 use only (i) the Fp -linearity of the coordinate maps (·)i (Fact 2.2), (ii) the F-linearity of a ⃗ 7→ (P(xj ))j in the randomness, and ∗ (i) ∗ ∗ (iii) fi = η f0 with f0 ̸= 0 (Definition 2.1). None of these depends on the leaked coordinates being one per share, so every step applies verbatim after replacing the index set {0, . . . , n − 1} by {(j, r)} and n by M. Full column rank rankFp (Θ) = M is thus a sufficient condition for perfect security, and is the criterion we establish below; as in the single-block case (Proposition 2.10) it need not be necessary. The structure of the kernel is as follows. A nonzero vector (cj,r )j,r ∈ ker(Θ) groups naturally by Pm
(r)
j shares, producing dj = r=1 cj,r η(ij ) ∈ F. By admissibility, the shifting factors within each share are Fp -independent, so dj = 0 if and only if all of the corresponding cj,r vanish. In particular, at least one dj must be nonzero.
Remark 5.2 (Admissibility gives within-share independence). Probing the same block position of a share twice returns the same symbol, so every pattern is equivalent to an admissible one, with mj ⩽ d. What admissibility buys is exactly the fact used in Theorem 5.4, which is that the (1)
(mj )
shifting factors η(ij ) , . . . , η(ij
)
attached to a single share are distinct members of the Fp -basis
{η(0) , . . . , η(d−1) } (Lemma 2.4), hence Fp -linearly independent, so that dj =
P
(r)
(ij ) = 0 forces r cj,r η
cj,1 = · · · = cj,mj = 0. Without distinctness, Θ has repeated columns and the full-rank certificate
fails for trivial reasons.
5.2
Nondegeneracy with field coefficients
Lemma 5.3. Let ψ0 , . . . , ψn−1 be Möbius transforms on P1 (F) with pairwise distinct poles. Let d0 , . . . , dn−1 ∈ P F with at least one dj ̸= 0, and ℓ ⩾ 1. Then j dj (ψj (x))ℓ ̸≡ 0 as a rational function, and has at most nℓ zeros in P1 (F).
Proof. Write ψj (x) = (Aj x + Bj )/(Cj x + Dj ) with det Mj = Aj Dj − Bj Cj ̸= 0, and let pj denote the pole of ψj . The poles are pairwise distinct by hypothesis. Let S = {j : Cj ̸= 0} (finite poles) and T = {j : Cj = 0} (pole at ∞), so |T | ⩽ 1. Case A All poles are finite (T = ∅). For each j, the residue of ψj at its pole pj = −Dj /Cj 2 is rj = − det Mj /Cj ̸= 0. Near pj , we have ψj (x) = rj /(x − pj ) + O(1), so (ψj (x))ℓ = rℓj /(x − P ℓ pj )ℓ + lower-order terms. Since pj ̸= pj ′ for j ̸= j ′ , the function j dj (ψj (x)) has a Laurent expansion near pj whose leading term is dj rℓj /(x − pj )ℓ ; all other summands are regular at pj . If P ℓ ℓ j dj (ψj (x)) ≡ 0, this leading coefficient must vanish: dj rj = 0. Since rj ̸= 0, we get dj = 0 for every j ∈ S. With T = ∅, this gives dj = 0 for all j, contradicting the hypothesis. 17
Case B One pole is at ∞ (say j = 0, so C0 = 0; all other Cj ̸= 0). The residue argument at each P finite pole pj (j ⩾ 1) gives dj rℓj = 0, hence dj = 0 for all j ⩾ 1. Then j dj (ψj (x))ℓ = d0 (ψ0 (x))ℓ . Since C0 = 0, ψ0 (x) = (A0 /D0 )x + B0 /D0 is a nonconstant affine function (A0 /D0 ̸= 0 because det(M0 ) = A0 D0 ̸= 0). Thus d0 (ψ0 (x))ℓ is a nonzero polynomial (since d0 ̸= 0 by hypothesis, as all other dj vanish). The zero bound ⩽ nℓ follows by the same degree argument as in Corollary 4.2: multiply Q P ℓ ℓ j∈S (Cj x + Dj ) to obtain a nonzero polynomial N(x) of degree ⩽ nℓ. j dj (ψj (x)) by D(x) =
5.3
Multi-block theorems
Theorem 5.4 (Multi-block, fixed pattern). Let p be any prime, d ⩾ 2, and 2 ⩽ k ⩽ n ⩽ d(k − 1) with n ⩽ pd − 1. Fix an admissible multi-block leakage pattern with M ⩽ d(k − 1) total blocks. The set of x0 ∈ F∗ for which the scheme is not perfectly secure against this pattern has size ⩽ n + n · pM . A good x0 exists when M < d − logp (2n). ⃗ Proof. A nonzero vector (cj,r )j,r ∈ FM p \ {0} lies in ker(Θ) if and only if mj n−1 XX
(r)
cj,r η(ij ) xℓj = 0
for all ℓ = 1, . . . , k − 1.
j=0 r=1
Grouping the inner sum by shares, this becomes
Pn−1
(1)
ℓ j=0 dj xj = 0 for all ℓ, where dj :=
P mj
(r)
(ij ) ∈ r=1 cj,r η
(mj )
F. By admissibility, the shifting factors η(ij ) , . . . , η(ij ) within share j are Fp -independent (Lemma 2.4), so dj = 0 if and only if cj,r = 0 for all r. Since ⃗c ̸= ⃗0, at least one dj ̸= 0. P By Lemma 5.3 with ℓ = 1 and ψj = Φj : the function G1 (x) = j dj Φj (x) is not identically zero and has at most n zeros in P1 (F). The set of x0 ∈ F∗ with G1 (x0 ) = 0 therefore has size ⩽ n. There are pM − 1 nonzero coefficient vectors in FM p . By the union bound over all such vectors, plus the n structural exclusions: |Bad| ⩽ n + (pM − 1) · n ⩽ n + n · pM .
A good x0 exists when |F∗ | = pd − 1 > n + n · pM , which holds when pd > 2n · pM , i.e., M < d − logp (2n). Theorem 5.5 (Universal multi-block). Let p be any prime, d ⩾ 2, and 2 ⩽ k ⩽ n ⩽ d(k − 1) with n ⩽ pd − 1, and let n ⩽ M ⩽ d(k − 1). To achieve perfect security against all admissible multi-block patterns with ⩽ M blocks simultaneously, we get |Bad| ⩽ n + n · (dpe)M . A good x0 exists when d > M 52 + logp d + logp (2n). Proof. We take a union bound over all admissible multi-block patterns with ⩽ M blocks total. An admissible pattern is specified by choosing, for each share j, a nonempty subset of {0, . . . , d − 1} of block positions. The total number of such patterns is at most md0 · · · md summed over all n−1 P (m0 , . . . , mn−1 ) with mj ⩽ M. Also note that by definition of admissible patterns, we have m0 , . . . , mn−1 ⩾ 1 and M ⩾ n. This gives us the total number as X m0 +···+mn−1 ⩽M m0 ,...,mn−1 ⩾1
X M d d nd nde M ··· ⩽ ⩽ ⩽ (de)M . m0 mn−1 t M t=n
18
where the first inequality is by the Chu-Vandermonde identity [Juk11, Exercise 1.9], the second inequality is the standard estimate on partial binomial sums [Juk11, Proposition 1.4] (valid since 1 ⩽ M ⩽ nd), and the third inequality is due to M ⩾ n. For each fixed pattern, Theorem 5.4 gives at most n · pM security-bad base points (beyond the structural exclusions). Taking the union bound over all ⩽ (de)M patterns, we get |Bad| ⩽ n + (n · pM ) · (de)M = n + n(dpe)M .
A good x0 exists when pd − 1 > n + n(dpe)M . Taking logarithms base p, we need d > logp (2n) + M(logp d + 1 + logp e), which is satisfied when d > M 52 + logp d + logp (2n).
19
A
Alternative proof of the dichotomy
The perfect-or-completely-insecure dichotomy used throughout this paper (Proposition 2.10) is a special case of the general dichotomy result of [Ngu25]. For completeness, we record here a direct derivation in our setting, working through the leakage map L⃗i and the cosets-of-subspaces structure. The proof depends only on Fp -linearity of coordinate extraction and on Shamir’s Flinearity in the randomness; it does not use any property of generalized Reed–Solomon codes or of binary images. Proof of Proposition 2.9. Since P(xj ) = s +
Pk−1
t t=1 at xj , the Fp -linearity of the coordinate map gives
ℓj = (P(xj ))ij = (s)ij +
k−1 X
(at xtj )ij .
t=1
By Fact 2.2, we have (at xtj )ij = Tr(at xtj · f∗ij ). This gives the decomposition ℓj = (s)ij + xtj · f∗ij ). It remains to verify that L⃗i is Fp -linear. For any λ ∈ Fp and a ⃗ , ⃗b ∈ Fk−1 : L⃗i (λ⃗ a + ⃗b)j =
k−1 X
Tr((λat + bt ) · xtj · f∗ij ) = λ
t=1
k−1 X t=1
Tr(at xtj f∗ij ) +
k−1 X
Pk−1
t=1 Tr(at ·
Tr(bt xtj f∗ij ),
t=1
where we used Tr(λ · y) = λ · Tr(y) for λ ∈ Fp (since the trace is Fp -linear) and Tr(y + z) = Tr(y) + Tr(z). Thus L⃗i (λ⃗a + ⃗b) = λL⃗i (⃗a) + L⃗i (⃗b). Proof of Proposition 2.10. Since a ⃗ = (a1 , . . . , ak−1 ) is uniform over Fk−1 and L⃗i is Fp -linear, the random variable L⃗i (⃗a) is uniform over the subspace Im(L⃗i ) ⊆ Fn p . By Proposition 2.9, the leakage for secret s is ⃗v(s) + L⃗i (⃗a), which is uniform over the coset ⃗v(s) + Im(L⃗i ). Two cosets of an Fp subspace of Fn p are either identical (when the difference of the shifts lies in the subspace, giving SD = 0) or disjoint (giving SD = 1, since uniform distributions on disjoint sets of equal size have n statistical distance 1). If L⃗i is surjective, then Im(L⃗i ) = Fn p , so every coset equals Fp .
20
References [BD+ 18] Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, and Tal Rabin. On the Local Leakage Resilience of Linear Secret Sharing Schemes. Advances in Cryptology – CRYPTO 2018. Vol. 10991. LNCS. Springer, 2018, pp. 531–561. 5
[ISW03] Yuval Ishai, Amit Sahai, and David Wagner. Private Circuits: Securing Hardware against Probing Attacks. Advances in Cryptology – CRYPTO 2003. Vol. 2729. LNCS. Springer, 2003, pp. 463–481. https: //doi.org/10.1007/978-3-540-45146-4_27. 2
[BD+ 21] Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, and Tal Rabin. On the Local Leakage Resilience of Linear Secret Sharing Schemes. Journal of Cryptology 34.2 (2021), p. 10. https://doi.org/10.1007/s00145-021-09375-2. 2, 5
[Juk11]
Stasys Jukna. Extremal combinatorics: with applications in computer science. Vol. 571. Springer, 2011. https://doi.org/10.1007/978-3-642-17364-6. 19
[KA26]
Hiroki Koga and Hiroto Abe. New Tight Bounds on The Local Leakage Resilience of The Additive (n, n)-Threshold Scheme Determined by The Eigenvalues of Circulant Matrices. Advances in Cryptology – ASIACRYPT 2025. Ed. by Goichiro Hanaoka and Bo-Yin Yang. Singapore: Springer Nature Singapore, 2026, pp. 34–66. https: //doi.org/10.1007/978-981-95-5125-5_2. 5
[KK23]
Ohad Klein and Ilan Komargodski. New Bounds on the Local Leakage Resilience of Shamir’s Secret Sharing Scheme. Advances in Cryptology – CRYPTO 2023. Vol. 14081. LNCS. Springer, 2023, pp. 139–170. https://doi.org/10.1007/978-3-031-385575_5. 5
[BP23]
Luís T. A. N. Brandão and René Peralta. NIST First Call for Multi-Party Threshold Schemes. 2023. https://csrc.nist.gov/publications/detail/ nistir/8214c/draft. 3
[BS+ 21] Mitali Bafna, Madhu Sudan, Santhoshini Velusamy, and Dain Xiang. Elementary Analysis of Isolated Zeroes of a Polynomial System. arXiv Peprint. 2021. https://doi.org/10.48550/arXiv.2102.00602. 5 [CS21]
Nicolas Costes and Martijn Stam. Redundant Code-Based Masking Revisited. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES). Vol. 2021. 1. 2021, pp. 426–450. https: //doi.org/10.46586/tches.v2021.i1.426-450. 2
[FM+ 24] Sebastian Faust, Loïc Masure, Elena Micheli, Maximilian Orlt, and François-Xavier Standaert. Connecting Leakage-Resilient Secret Sharing to Practice: Scaling Trends and Physical Dependencies of Prime Field Masking. Advances in Cryptology – EUROCRYPT 2024. Springer, 2024, pp. 316–344. https://doi.org/10.1007/978-3-031-587375_12. 3 [GK18]
[GR08]
Vipul Goyal and Ashutosh Kumar. Non-Malleable Secret Sharing. 50th ACM Symposium on Theory of Computing (STOC 2018). 2018, pp. 685–698. https://doi.org/10.1145/3188745.3188872. 2 Venkatesan Guruswami and Atri Rudra. Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy. IEEE Transactions on Information Theory 54.1 (2008), pp. 135–150. https://doi.org/10.1109/TIT.2007.911222. 3, 11
[HM+ 25] Jihun Hwang, Hemanta K. Maji, Hai H. Nguyen, and Xiuyu Ye. Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places. 6th Conference on Information-Theoretic Cryptography (ITC 2025). LIPIcs. 2025. https://doi.org/10.4230/LIPIcs.ITC.2025.3. 2, 3, 6
[KMS19] Ashutosh Kumar, Raghu Meka, and Amit Sahai. Leakage-Resilient Secret Sharing Against Colluding Parties. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 2019, pp. 636–660. https://doi.org/10.1109/FOCS.2019.00045. 5 [MN+ 21] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Leakage-Resilience of the Shamir Secret-Sharing Scheme against Physical-Bit Leakages. Advances in Cryptology – EUROCRYPT 2021. Vol. 12697. LNCS. Springer, 2021, pp. 344–374. https://doi.org/10.1007/978-3-030-778866_12. 2, 3, 5 [MN+ 22] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, and Mingyuan Wang. Improved Bound on the Local Leakage-resilience of Shamir’s Secret Sharing. 2022 IEEE International Symposium on Information Theory (ISIT). 2022, pp. 2678–2683. https: //doi.org/10.1109/ISIT50566.2022.9834695. 5 [MN+ 24] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, and Xiuyu Ye. Constructing Leakage-Resilient Shamir’s Secret Sharing: Over Composite Order Fields. Advances in Cryptology – EUROCRYPT 2024. Vol. 14654. LNCS. Springer, 2024, pp. 286–315. https: //doi.org/10.1007/978-3-031-58737-5_11. 2–5, 7, 9
21
[MP+ 21] Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Constructing Locally Leakage-Resilient Linear Secret-Sharing Schemes. Advances in Cryptology – CRYPTO 2021. Vol. 12827. LNCS. Springer, 2021, pp. 779–808. https://doi.org/10.1007/978-3-030-842529_26. 5 [Ngu24] Hai H. Nguyen. Towards Breaking the Half-Barrier for Shamir’s Secret Sharing Scheme. Advances in Cryptology – CRYPTO 2024. 2024. https: //doi.org/10.1007/978-3-031-68388-6_10. 5 [Ngu25] Hai H. Nguyen. Physical-Bit Leakage Resilience of Linear Code-Based Secret Sharing. Advances in
Cryptology – EUROCRYPT 2025. Ed. by Serge Fehr and Pierre-Alain Fouque. Cham: Springer Nature Switzerland, 2025, pp. 64–93. https: //doi.org/10.1007/978-3-031-91101-9_3. 2–7, 9, 13, 20 [Sha79]
Adi Shamir. How to Share a Secret. Communications of the ACM 22.11 (1979), pp. 612–613. https://doi.org/10.1145/359168.359176. 2
[Zha12] Xiaomei Zhao. A Note on Multiple Exponential Sums in Function Fields. Finite Fields and Their Applications 18.1 (2012), pp. 35–55. https://doi.org/10.1016/j.ffa.2011.06.003. 5
22