Constructing Leakage-Resilient Shamir's Secret Sharing: Over Composite Order Fields

Probing physical bits in hardware has compromised cryptographic systems. This work investigates how to instantiate Shamir's secret sharing so that the physical probes into its shares reveal statistically insignificant information about the secret.

Over prime fields, Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT 2021) proved that choosing random evaluation places achieves this objective with high probability. Our work extends their randomized construction to composite order fields -particularly for fields with characteristic 2. Next, this work fully derandomizes this result for some specific cases.

Our security analysis of the randomized construction is Fourier-analytic, and the derandomization techniques are combinatorial. Our analysis relies on (1) contemporary Bézout-theoremtype algebraic complexity results that bound the number of simultaneous zeroes of a system of polynomial equations over composite order fields and (2) characterization of the zeroes of an appropriate generalized Vandermonde determinant.

How do we instantiate Shamir's secret sharing to protect its secret against physical bit probes on the shares? Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang [MNP + 21] proved that for large prime moduli and reconstruction threshold ⩾ 2, choosing the evaluation places for Shamir's secret sharing at random results in a locally leakage-resilient scheme secure against physical bit leakage with high probability. This work investigates the secret sharing over composite order fields, specifically large characteristic-2 fields used widely in practice.