Paper 2020/1252

Adaptive Extractors and their Application to Leakage Resilient Secret Sharing

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

Abstract

We introduce Adaptive Extractors, which, unlike traditional randomness extractors, guarantee security even when an adversary obtains leakage on the source after observing the extractor output. We make a compelling case for the study of such extractors by demonstrating their use in obtaining adaptive leakage in secret sharing schemes. Specifically, at FOCS 2020, Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, Zuckerman, built an adaptively secure leakage resilient secret sharing scheme (LRSS) with both rate and leakage rate being $O(1/n)$, where $n$ is the number of parties. In this work, we build an adaptively secure LRSS that offers an interesting trade-off between rate, leakage rate, and the total number of shares from which an adversary can obtain leakage. As a special case, when considering $t$-out-of-$n$ secret sharing schemes for threshold $t = cn$ (constant $0<c<1$), we build a scheme with a constant rate, constant leakage rate, and allow the adversary leakage from all but $t-1$ of the shares, while giving her the remaining $t-1$ shares completely in the clear. (Prior to this, constant rate LRSS scheme tolerating adaptive leakage was unknown for any threshold.) Finally, we show applications of our techniques to both non-malleable secret sharing and secure message transmission.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2021
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

BibTeX

@misc{cryptoeprint:2020/1252,
      author = {Nishanth Chandran and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar},
      title = {Adaptive Extractors and their Application to Leakage Resilient Secret Sharing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1252},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1252}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.