| Paper ID | D2-S7-T4.2 |
| Paper Title |
Lower Bounds for Leakage-Resilient Secret-Sharing Schemes against Probing Attacks |
| Authors |
Donald Q. Adams, Hemanta K. Maji, Hai H. Nguyen, Minh L. Nguyen, Purdue University, United States; Anat Paskin-Cherniavsky, Tom Suad, Ariel University, Israel; Mingyuan Wang, Purdue University, United States |
| Session |
D2-S7-T4: Secret Sharing |
| Chaired Session: |
Wednesday, 14 July, 00:00 - 00:20 |
| Engagement Session: |
Wednesday, 14 July, 00:20 - 00:40 |
| Abstract |
Historically, side-channel attacks have revealed partial information about the intermediate values and secrets of computations to compromise the security of cryptographic primitives. The objective of leakage-resilient cryptography is to model such avenues of information leakage and study techniques to realize them securely. This work studies the local leakage-resilience of prominent secret-sharing schemes like Shamir's secret-sharing scheme and the additive secret-sharing scheme against probing attacks that leak physical-bits from the memory hardware storing the secret shares. Consider the additive secret-sharing scheme among $k$ parties over a prime field such that the prime needs $\secpar$-bits for its binary representation, where $\secpar$ is the security parameter. We prove that $k$ must be at least $\smallOmega{\log\secpar/\log\log\secpar}$ for the scheme to be secure against even one physical-bit leakage from each secret share. This result improves the previous state-of-the-art result where an identical lower bound was known for one-bit general leakage from each secret share (Benhamouda, Degwekar, Ishai, and Rabin, CRYPTO--2018). This lower bound on the reconstruction threshold extends to Shamir's secret-sharing scheme if one does not carefully choose the evaluation places for generating the secret shares. For this scheme, our result additionally improves another lower bound on the reconstruction threshold $k$ of Shamir's secret-sharing scheme (Nielsen and Simkin, EUROCRYPT--2020) when the total number of parties is $\bigO{\secpar\log\secpar/\log\log\secpar}$. Our work provides the analysis of the recently-proposed (explicit) physical-bit leakage attack of Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT--2021), namely the ``parity of parity'' attack. This analysis relies on lower-bounding the ``discrepancy'' of the Irwin-Hall probability distribution.
|
