Adaptive Extractors and their Application to Leakage Resilient Secret Sharing

A Leakage Resilient Secret Sharing (LRSS) is a secure secret sharing scheme, even when the adversary obtains some (bounded) leakage on honest shares. Ideally, such schemes must be secure against adaptive and joint leakage queries – i.e., the adversary can make a sequence of adaptive leakage queries where each query can be a joint function of many of the shares. In this work, we provide the first constant rate LRSS (for the general access structure) and non-malleable LRSS (for the threshold access structure) schemes that tolerate such joint and adaptive leakage in the information-theoretic setting. We show how to make use of our constructions to also provide constant rate constructions of leakage-resilient (and non-malleable) secure message transmission.

This is joint work with Nishanth Chandran and Sai Lakshmi Bhavana Obbattu from Microsoft Research India and Sruthi Sekar from IISc.