International Association for Cryptologic Research

International Association
for Cryptologic Research


Sai Lakshmi Bhavana Obbattu


Adaptive Extractors and their Application to Leakage Resilient Secret Sharing 📺
Nishanth Chandran Bhavana Kanukurthi Sai Lakshmi Bhavana Obbattu Sruthi Sekar
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.
Four-State Non-malleable Codes with Explicit Constant Rate
Bhavana Kanukurthi Sai Lakshmi Bhavana Obbattu Sruthi Sekar
Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs (ITCS 2010), provide a powerful guarantee in scenarios where the classical notion of error-correcting codes cannot provide any guarantee: a decoded message is either the same or completely independent of the underlying message, regardless of the number of errors introduced into the codeword. Informally, NMCs are defined with respect to a family of tampering functions $$\mathcal {F}$$ F and guarantee that any tampered codeword decodes either to the same message or to an independent message, so long as it is tampered using a function $$f \in \mathcal {F}$$ f ∈ F . One of the well-studied tampering families for NMCs is the t -split-state family, where the adversary tampers each of the t “states” of a codeword, arbitrarily but independently. Cheraghchi and Guruswami (TCC 2014) obtain a rate-1 non-malleable code for the case where $$t = \mathcal {O}(n)$$ t = O ( n ) with n being the codeword length and, in (ITCS 2014), show an upper bound of $$1-1/t$$ 1 - 1 / t on the best achievable rate for any t -split state NMC. For $$t=10$$ t = 10 , Chattopadhyay and Zuckerman (FOCS 2014) achieve a constant-rate construction where the constant is unknown. In summary, there is no known construction of an NMC with an explicit constant rate for any $$t= o(n)$$ t = o ( n ) , let alone one that comes close to matching Cheraghchi and Guruswami’s lowerbound! In this work, we construct an efficient non-malleable code in the t -split-state model, for $$t=4$$ t = 4 , that achieves a constant rate of $$\frac{1}{3+\zeta }$$ 1 3 + ζ , for any constant $$\zeta > 0$$ ζ > 0 , and error $$2^{-\varOmega (\ell / log^{c+1} \ell )}$$ 2 - Ω ( ℓ / l o g c + 1 ℓ ) , where $$\ell $$ ℓ is the length of the message and $$c > 0$$ c > 0 is a constant.