Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

Technical Summary: Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

1. Problem Statement

The paper addresses the construction of explicit evaluation places for Shamir's Secret Sharing (SSS) schemes that are resilient against physical-bit leakage over composite order fields ($\mathbb{F}_{p^d}$ where $d \ge 2$).

In standard SSS, a secret is shared among $n$ parties such that any $k$ can reconstruct it. While randomized constructions (choosing evaluation places uniformly at random) are known to be statistically secure against local leakage, they require trusted public randomness. In practice, adversaries may influence the random seed, steering the scheme toward vulnerable evaluation places.

Previous work established that:

• Over prime fields ($\mathbb{F}_p$), random evaluation places yield leakage resilience with high probability.
• Over composite fields ($\mathbb{F}_{p^d}$), Nguyen (EUROCRYPT 2025) established a perfect dichotomy: any linear code-based secret sharing scheme is either perfectly secure (statistical distance 0) or completely insecure against physical-bit leakage.
• However, for composite fields, no explicit, deterministic family of evaluation places was known for $k > 2$ or general block-leakage regimes. Existing explicit constructions for prime fields relied on non-linear bit-extraction properties that do not apply to the linear coordinate maps of composite fields.

The core challenge is to derandomize the choice of evaluation places (reducing the entropy required to specify them) while maintaining perfect security against physical-bit leakage in the composite field setting.

2. Methodology and Construction

The author proposes a partial derandomization strategy. Instead of selecting $n$ independent random evaluation points, they construct the evaluation places as the iterates of a single rational function $\Phi$ applied to a randomly chosen base point $x_0$.

The Construction:

• Field Setup: Let $\mathbb{F} = \mathbb{F}_{p^d}$ with a primitive element $\alpha$.
• Step Operator: Define the Möbius transformation $\Phi(x) = \frac{\alpha x}{x + 1}$.
• Evaluation Places: The $n$ evaluation places are defined as $x_j = \Phi^j(x_0)$ for $j = 0, \dots, n-1$, where $x_0 \in \mathbb{F}^*$ is a randomly chosen base point.
• Entropy Reduction: Specifying the scheme requires only $d \log p$ bits (to choose $x_0$), a significant reduction from the $nd \log p$ bits required for $n$ independent random points.

Key Structural Insight:
The security analysis relies on the distinct poles of the iterates $\Phi^j$.

• $\Phi^0(x) = x$ has a pole at $\infty$.
• For $j \ge 1$, $\Phi^j(x)$ has a pole at a distinct finite point in $\mathbb{F}^*$.
• This "pole-distinctness" is crucial. The author contrasts this with the candidate $\Psi(x) = \alpha x$ (pure dilation), where all iterates share the same pole at $\infty$, causing the security argument to collapse.

3. Technical Approach

The proof proceeds in three phases, leveraging the perfect dichotomy established by Nguyen (2025):

1. The Perfect Dichotomy (Phase 1):
   The paper utilizes the fact that coordinate extraction in $\mathbb{F}_{p^d}$ is $\mathbb{F}_p$-linear. Consequently, the leakage map is linear. This implies that the statistical distance between leakage distributions for different secrets is either 0 or 1. Perfect security is achieved if and only if the leakage map is surjective. This condition is equivalent to a test matrix $\Theta_{\vec{i}}$ (derived from the evaluation places and leakage pattern) having full column rank over $\mathbb{F}_p$.

2. Partial Fraction Nondegeneracy (Phase 2):
   To prove the test matrix has full rank, the author must show that no non-trivial linear combination of the evaluation place powers vanishes. They define a rational function $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$.
   Using partial fraction decomposition, they exploit the distinct poles of $\Phi^j$. Because the poles are distinct, the residue of $G_\ell$ at any specific pole is determined by a single term in the sum. If $G_\ell$ were identically zero, all coefficients would have to vanish. This "nondegeneracy" argument bounds the number of "bad" base points $x_0$ that cause the rank condition to fail.

3. Multi-block Extension (Phase 3):
   The argument is extended to multi-block leakage (where multiple coordinates per share are leaked). The author handles field coefficients arising from linear combinations within shares, showing that the partial fraction argument remains valid provided the leakage pattern is "admissible" (distinct block positions per share).

4. Key Results

Theorem 1.1 (Perfect Security against Single-Block Leakage):
For parameters $n = O(d / \log_p d)$ and any threshold $k \ge 2$, there exists a set of "bad" base points $Bad \subset \mathbb{F}^*$ with size $|Bad| \le n + n(dp)^n$. For any $x_0 \notin Bad$, the scheme using evaluation places $x_j = \Phi^j(x_0)$ is perfectly secure (statistical distance exactly 0) against any single-block leakage pattern.

• This implies perfect security against single physical-bit leakage per share for any prime $p$.
• A good $x_0$ is guaranteed to exist when $d > n(1 + \log_p d) + \log_p(2n)$.

Theorem 1.2 (Multi-Block Leakage):
For a fixed admissible leakage pattern with $M$ total blocks leaked, the bad set size is bounded by $n + n \cdot p^M$. A good $x_0$ exists if $M < d - \log_p(2n)$.

• For universal security against all patterns with $\le M$ blocks, the bound is $|Bad| \le n + n(dpe)^M$, with existence guaranteed when $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$.

Classifier:
The paper provides an explicit classifier (Algorithm 1) that, given a candidate $x_0$, verifies the full-rank condition for all leakage patterns. This serves as a sound test to certify the security of the structured construction.

5. Significance and Comparison

The paper claims the following contributions and distinctions:

• Perfect Security vs. Statistical Security: Unlike previous randomized constructions over composite fields which offered statistical security ($\epsilon = 2^{-\Omega(d)}$), this construction achieves perfect security (statistical distance 0) for a restricted regime of parameters.
• Derandomization: It reduces the randomness required to specify the scheme from $nd \log p$ bits to $d \log p$ bits by restricting evaluation places to a one-parameter family (the orbit of $\Phi$).
• Explicit Construction: It provides the first explicit family of evaluation places for $k > 2$ over composite fields that resists physical-bit leakage, moving beyond the "random places" paradigm.
• Limitations and Trade-offs:
  • The number of parties $n$ is limited to $O(d / \log_p d)$, whereas randomized constructions support $O(dk / \log_p d)$. The author conjectures this factor-$k$ loss is inherent to single-parameter constructions.
  • The multi-block universality is currently limited by a pattern enumeration bottleneck, resulting in exponential bad-set bounds in $M$.
  • The construction relies on the specific algebraic structure of the Möbius transformation $\Phi(x) = \alpha x / (x+1)$; the alternative dilation $\alpha x$ fails to provide security.

The work does not claim to solve the derandomization problem for all parameter regimes or to provide a polynomial-size bad-set bound for multi-block universality, identifying these as open problems. The primary contribution is a rigorous, partial derandomization that achieves perfect security in a specific, practically relevant regime by exploiting the distinct poles of rational iterates.