Welcome to the resource topic for 2020/1517
Title:
Constructing Locally Leakage-resilient Linear Secret-sharing Schemes
Authors: Hemanta Maji, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang
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.
ePrint: https://eprint.iacr.org/2020/1517
Talk: https://www.youtube.com/watch?v=_cq9UD7Cn5w
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/361/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .