Cryptology ePrint Archive: Report 2020/1517

On Leakage-Resilient Secret Sharing

Hemanta Maji and Anat Paskin-Cherniavsky and Tom Suad and Mingyaun Wang

Abstract: The security of cryptographic primitives typically relies on the storage of private secrets by each participant in a perfect manner. However, increasingly, side-channel attacks are demonstrating the pitfalls of assuming these cryptographic entities as opaque monolithic objects over the entire duration the primitive remains alive. Motivated by such concerns, there is a significant interest in revisiting well-established cryptographic primitives and their implementations to identify whether their security continues to hold in the presence of such side-channel attacks.

%Fundamental primitives, like secret-sharing schemes when performed over carelessly chosen finite fields lead to devastating security breaches. %For example, linear secret sharing schemes over characteristic 2 fields are susceptible to an adversary who performs only one-bit leakage from the shares of all the parties. Although there are compilers to convert any secret sharing scheme into one that is robust to local leakage on each of their shares, it is not feasible to replace every instance of traditional secret sharing schemes in use with a leakage-resilient counterpart. Beyond efficiency considerations, there may be an appropriate structure in specific secret-sharing schemes that are fundamental to their usage in a particular context. For example, the use of a linear secret sharing scheme helps perform secure aggregation of statistics in parallel (for example, the sum of the private inputs of the participants) even in the presence of malicious parties. The reconstruction threshold of these secret sharing schemes determines the threshold of corruption permissible in the secure computation protocol; a lower reconstruction threshold implies a higher efficiency.

This paper makes a two-fold contribution. First, we continue to study the local leakage resilience of Reed-Solomon codes as initiated by Benhamouda, Degwekar, Ishai, and Rabin (2018). We improve their lower bound on the reconstruction threshold for Reed Solomon codes from $0.907n$ to $0.867n$ for one-bit leakage from each secret share, where $n$ represents the number of parties receiving the secret shares.

Next, we explore whether, in the presence of local leakage, there is something inherent to maximum-distance separable (MDS) codes (Reed Solomon code is a particular example from this class of codes) that innately demands high reconstruction thresholds. Towards this investigation, we study random MDS codes and their necessary reconstruction threshold to remain resilient to a constant local leakage from each share. Given any $\delta\in(0,1/2),$ we prove that most random MDS codes over suitably large fields with reconstruction threshold $(1/2 + \delta)n$ are resilient to constant local leakage.

In terms of techniques, both results rely on a Fourier-analytic approach to this problem. In particular, the second result relies on new and subtle analysis techniques for random MDS codes, which we believe shall be of independent interest.

Finally, we also contribute to the impossibility of designing secret-sharing schemes based on MDS codes over prime-order fields, where the dimension of the code is very small. If one insists on exponentially small indistinguishability among the shares generated by two different secrets, then the dimension of the code needs to be $\Omega(n/\log n)$ even when the adversary obtains only $m=1$ bit leakage from each of the shares and the field size is arbitrarily large.

Category / Keywords: foundations / Random maximum distance separable codes, Secret sharing, Local leakage resilience, Discrete Fourier analysis.

Date: received 3 Dec 2020

Contact author: anps83 at gmail com, hemanta maji@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201204:080517 (All versions of this report)

Short URL: ia.cr/2020/1517


[ Cryptology ePrint archive ]