Cryptology ePrint Archive: Report 2020/1252

Constant Rate (Non-malleable) Secret Sharing Schemes Tolerating Joint Adaptive Leakage

Nishanth Chandran and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar

Abstract: 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. The most important parameters of interest are the rate (= $\frac{|secret|}{|longest share|}$) and the leakage rate (ratio of the total allowable leakage from a single leakage query to the size of a share). None of the prior works tolerating such adaptive and joint leakage could attain a constant rate and constant leakage rate, even for the threshold access structure. An LRSS is non-malleable (LRNMSS) when an adversary cannot tamper shares in a way that the reconstructed secret is related to the original secret. Similar to LRSSs, none of the prior LRNMSS schemes in the information theoretic setting could attain a constant rate, even for the threshold access structure.

In this work, we provide the first constant rate LRSS (for the general access structure) and LRNMSS (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.

We obtain our results by introducing a novel object called Adaptive Extractors. Adaptive extractors can be seen as a generalization of the notion of exposure-resilient extractors (Zimand, CCC 2006). Such extractors provide security guarantees even when an adversary obtains leakage on the source of the extractor after observing the extractor output. We make a compelling case for the study of such extractors by demonstrating their critical use for obtaining adaptive leakage and believe that such an object will be of independent interest.

Category / Keywords: foundations / Information theoretic Cryptography, Non-malleability, Leakage Resilient Secret Sharing, Non-malleable Codes, Randomness Extractors, Non-malleable Secret Sharing

Date: received 9 Oct 2020

Contact author: sruthi sekar1 at gmail com,oslbhavana@gmail com,bhavana@iisc ac in,nichandr@microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20201009:113939 (All versions of this report)

Short URL: ia.cr/2020/1252