International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Constructing Locally Leakage-resilient Linear Secret-sharing Schemes

Authors:
Hemanta K. Maji , Purdue University
Anat Paskin-Cherniavsky , Ariel University
Tom Suad , Ariel University
Mingyuan Wang , Purdue University
Download:
DOI: 10.1007/978-3-030-84252-9_26 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Abstract: Innovative side-channel attacks have repeatedly falsified the assumption that cryptographic implementations are opaque black-boxes. Therefore, it is essential to ensure cryptographic constructions' security even when information leaks via unforeseen avenues. One such fundamental cryptographic primitive is the secret-sharing schemes, which underlies nearly all threshold cryptography. Our understanding of the leakage-resilience of secret-sharing schemes is still in its preliminary stage. This work studies locally leakage-resilient linear secret-sharing schemes. An adversary can leak m bits of arbitrary local leakage from each n secret shares. However, in a locally leakage-resilient secret-sharing scheme, the leakage's joint distribution reveals no additional information about the secret. For every constant m, we prove that the Massey secret-sharing scheme corresponding to a random linear code of dimension k (over sufficiently large prime fields) is locally leakage-resilient, where k/n>1/2 is a constant. The previous best construction by Benhamouda, Degwekar, Ishai, Rabin (CRYPTO--2018) needed k/n>0.907. A technical challenge arises because the number of all possible m-bit local leakage functions is exponentially larger than the number of random linear codes. Our technical innovation begins with identifying an appropriate pseudorandomness-inspired family of tests; passing them suffices to ensure leakage-resilience. We show that most linear codes pass all tests in this family. This Monte-Carlo construction of linear secret-sharing scheme that is locally leakage-resilient has applications to leakage-resilient secure computation. Furthermore, we highlight a crucial bottleneck for all the analytical approaches in this line of work. Benhamouda et al. introduced an analytical proxy to study the leakage-resilience of secret-sharing schemes; if the proxy is small, then the scheme is leakage-resilient. However, we present a one-bit local leakage function demonstrating that the converse is false, motivating the need for new analytically well-behaved functions that capture leakage-resilience more accurately. Technically, the analysis involves probabilistic and combinatorial techniques and (discrete) Fourier analysis. The family of new ``tests'' capturing local leakage functions, we believe, is of independent and broader interest.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31238,
  title={Constructing Locally Leakage-resilient Linear Secret-sharing Schemes},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-84252-9_26},
  author={Hemanta K. Maji and Anat Paskin-Cherniavsky and Tom Suad and Mingyuan Wang},
  year=2021
}