You are looking at a specific version 20201009:113939 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Information theoretic CryptographyNon-malleabilityLeakage Resilient Secret SharingNon-malleable CodesRandomness ExtractorsNon-malleable Secret Sharing
Contact author(s)
sruthi sekar1 @ gmail com,oslbhavana @ gmail com,bhavana @ iisc ac in,nichandr @ microsoft com
History
2021-06-24: last of 2 revisions
2020-10-09: received
See all versions
Short URL
https://ia.cr/2020/1252
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.