CryptoDB

Paper: Leakage-resilient Linear Secret-sharing against arbitrary Bounded-size Leakage Family

Authors: Hemanta K. Maji , Purdue University Hai Nguyen , Purdue University Anat Paskin-Cherniavsky , Ariel University Tom Suad , Ariel University Mingyuan Wang , University of California Berkeley Xiuyu Ye , Purdue University Albert Yu , Purdue University Search ePrint Search Google Slides TCC 2022 Motivated by leakage-resilient secure computation of circuits with addition and multiplication gates, this work studies the leakage-resilience of linear secret-sharing schemes with a small reconstruction threshold against any {\em bounded-size} family of joint leakage attacks, \ie, the leakage function can leak {\em global} information from all secret shares. We first prove that, with high probability, the Massey secret-sharing scheme corresponding to a random linear code over a finite field $F$ is leakage-resilient against any $\ell$-bit joint leakage family of size at most $\abs{F}^{k-2.01}/8^\ell$, where $k$ is the reconstruction threshold. Our result (1) bypasses the bottleneck due to the existing Fourier-analytic approach, (2) enables secure multiplication of secrets, and (3) is near-optimal. We use combinatorial and second-moment techniques to prove the result. Next, we show that the Shamir secret-sharing scheme over a prime-order field $F$ with randomly chosen evaluation places and with threshold $k$ is leakage-resilient to any $\ell$-bit joint leakage family of size at most $\abs{F}^{2k-n-2.01}/(k!\cdot 8^\ell)$ with high probability. We prove this result by marrying our proof techniques for the first result with the existing Fourier analytical approach. Moreover, it is unlikely that one can extend this result beyond $k/n\leq0.5$ due to the technical hurdle of the Fourier-analytic approach.
BibTeX
@inproceedings{tcc-2022-32606,
title={Leakage-resilient Linear Secret-sharing against arbitrary Bounded-size Leakage Family},
publisher={Springer-Verlag},
author={Hemanta K. Maji and Hai Nguyen and Anat Paskin-Cherniavsky and Tom Suad and Mingyuan Wang and Xiuyu Ye and Albert Yu},
year=2022
}