Abstract

We make progress on the question of constructing explicit evaluation places for leakageresilient Shamirs secret sharing, over composite order fields. Previously, Maji et al. (EUROCRYPT 2024) showed that random evaluation places yield Shamirs secret sharing over the composite order field F pd 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 pd is either statistically secure or completely insecure against such leakage. Building upon Nguyens 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 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.