Cryptology ePrint Archive: Report 2019/653

On the Local Leakage Resilience of Linear Secret Sharing Schemes

Fabrice Benhamouda and Akshay Degwekar and Yuval Ishai and Tal Rabin

Abstract: We consider the following basic question: to what extent are standard secret sharing schemes and protocols for secure multiparty computation that build on them resilient to leakage? We focus on a simple local leakage model, where the adversary can apply an arbitrary function of a bounded output length to the secret state of each party, but cannot otherwise learn joint information about the states.

We show that additive secret sharing schemes and high-threshold instances of Shamir’s secret sharing scheme are secure under local leakage attacks when the underlying field is of a large prime order and the number of parties is sufficiently large. This should be contrasted with the fact that any linear secret sharing scheme over a small characteristic field is clearly insecure under local leakage attacks, regardless of the number of parties. Our results are obtained via tools from Fourier analysis and additive combinatorics.

We present two types of applications of the above results and techniques. As a positive application, we show that the “GMW protocol” for honest-but-curious parties, when implemented using shared products of random field elements (so-called “Beaver Triples”), is resilient in the local leakage model for sufficiently many parties and over certain fields. This holds even when the adversary has full access to a constant fraction of the views. As a negative application, we rule out multiparty variants of the share conversion scheme used in the 2-party homomorphic secret sharing scheme of Boyle et al. (Crypto 2016).

Category / Keywords: foundations / Secret Sharing, leakage resilience, information theory, multiparty computation

Original Publication (with minor differences): IACR-CRYPTO-2018

Date: received 3 Jun 2019, last revised 3 Jun 2019

Contact author: degwekarakshay at gmail com,talrny@yahoo com,yuval ishai@gmail com,fabrice benhamouda@normalesup org

Available format(s): PDF | BibTeX Citation

Version: 20190604:071039 (All versions of this report)

Short URL: ia.cr/2019/653


[ Cryptology ePrint archive ]