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

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 F p d 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 F p d 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 x j = j(x 0) of a simple fixed rational function, where the initial point x 0 in F p d* is randomly chosen. The randomness in the evaluation places thus drops from nd p bits to d p bits. Our construction is valid for the regime n = O(d/ p 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.