2026-08-14T00:27:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27105 2026-08-12T06:00:27Z ddc:004 open_access

Partial Derandomization for Leakage-Resilient Shamir’s Secret Sharing over Composite Order Fields Venkitesh, S. Shamir’s secret sharing leakage resilience physical bit probing physical bit leakage secure evaluation places rational functions 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 𝔽_{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 𝔽_{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₀) of a simple fixed rational function Φ, where the initial point x₀ ∈ 𝔽_{p^d}^* 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/log_p d), and any reconstruction threshold k ≥ 2; in fact, the scheme attains perfect security (statistical distance exactly zero) against single-block leakage. Building on Nguyen’s dichotomy, our technique is a partial-fraction non-degeneracy argument that exploits the distinct poles of the rational iterates. Schloss Dagstuhl – Leibniz-Zentrum für Informatik S. Venkitesh 2026 Is Part Of LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2026.12 urn:nbn:de:0030-drops-271059 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode