International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Adaptive Extractors and their Application to Leakage Resilient Secret Sharing

Authors:
Nishanth Chandran , Microsoft Research, India
Bhavana Kanukurthi , Indian Institute of Science, Bangalore
Sai Lakshmi Bhavana Obbattu , Microsoft Research, India
Sruthi Sekar , Indian Institute of Science, Bangalore
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Abstract: We introduce Adaptive Extractors, which unlike traditional randomness extractors, guarantee security even when an adversary obtains leakage on the source \textit{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 $\mathcal{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 = \alpha n$ (constant $0<\alpha<1$), we build a scheme with 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 \textit{any} threshold.) Finally, we show applications of our techniques to both non-malleable secret sharing and secure message transmission.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31148,
  title={Adaptive Extractors and their Application to Leakage Resilient Secret Sharing},
  publisher={Springer-Verlag},
  author={Nishanth Chandran and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar},
  year=2021
}