International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Hemanta K. Maji , Purdue University
Hai H. Nguyen , ETH Zurich
Anat Paskin-Cherniavsky , Ariel University
Xiuyu Ye , Purdue University
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: 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 presents an algorithm to classify evaluation places as secure or vulnerable against physical-bit probes for some specific cases. Our security analysis of the randomized construction is Fourier-analytic, and the classification techniques are combinatorial. Our analysis relies on (1) contemporary Bezout-theorem-type 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.
  title={Constructing Leakage-resilient Shamir's Secret Sharing: Over Composite Order Fields},
  author={Hemanta K. Maji and Hai H. Nguyen and Anat Paskin-Cherniavsky and Xiuyu Ye},