Paper 2020/1252

Adaptive Extractors and their Application to Leakage Resilient Secret Sharing

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


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.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2021
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
2021-06-24: last of 2 revisions
2020-10-09: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.