2026/07/30 by S. Venkitesh
Computer Science · Mathematics · #cs.CR #cs.IT #math.IT
A preliminary version of this work is due to appear at ITC 2026
arxiv created 2026/07/30 · arxiv updated 2026/08/04
We make progress on the question of constructing explicit evaluation places for leakage-resilient 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 \mathbbFpd 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 \mathbbFpd 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 ∈ \mathbbFpd^* is randomly chosen. The randomness in the evaluation places thus drops from nd log p bits to dlog 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.