Ashutosh Kumar: Securing Secret Sharing Against Leakage and Tampering

Friday, November 22, 2019 - 10:30am to 12:00pm
Hewlett, G882
Ashutosh Kumar, UCLA
ABSTRACT: Secret sharing is one of the most classical and widely used cryptographic primitives. In the most basic and perhaps the most important setup, a secret needs to be shared between n parties such that any t of them can recover the secret but no fewer can gain any information even with collusion. As useful as this model, such schemes are still susceptible to attacks where someone 'tampers' or 'leaks' tiny amount of information from the parties. Here we seek to counteract such threats.

We say that a scheme is p-party leakage-resilient if the secret remains statistically hidden even after an adversary learns a bounded amount of leakage, where each bit of leakage can depend jointly on the shares of an adaptively chosen subset of p parties. We rely on communication complexity lower bounds in the number-on-forehead model to transform any scheme into a p-party leakage-resilient one for p logarithmic in the number of parties. This yields the first multi-party schemes secure against adaptive and joint leakage.

We say that a scheme is non-malleable if the secret is essentially `destroyed' in case an adversary tampers with (possibly all) the shares. This notion is inspired by the beautiful line of work on non-malleable codes. We transform any scheme into one that is non-malleable against an adversary who tampers with all the shares arbitrarily and independently. We also consider stronger adversaries who may jointly tamper multiple shares. All our constructions achieve information-theoretic security.

Based on joint works with Vipul Goyal, Raghu Meka, and Amit Sahai.