International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Bhavana Kanukurthi

Affiliation: Indian Institute of Science, India

Publications

Year
Venue
Title
2019
JOFC
Four-State Non-malleable Codes with Explicit Constant Rate
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.
2018
EUROCRYPT
2017
TCC
2016
TCC
2015
EPRINT
2014
PKC
2014
TCC
2011
CRYPTO
2009
EUROCRYPT
2008
EPRINT
An Improved Robust Fuzzy Extractor
Bhavana Kanukurthi Leonid Reyzin
We consider the problem of building robust fuzzy extractors, which allow two parties holding similar random variables W, W' to agree on a secret key R in the presence of an active adversary. Robust fuzzy extractors were defined by Dodis et al. in Crypto 2006 to be noninteractive, i.e., only one message P, which can be modified by an unbounded adversary, can pass from one party to the other. This allows them to be used by a single party at different points in time (e.g., for key recovery or biometric authentication), but also presents an additional challenge: what if R is used, and thus possibly observed by the adversary, before the adversary has a chance to modify P. Fuzzy extractors secure against such a strong attack are called post-application robust. We construct a fuzzy extractor with post-application robustness that extracts a shared secret key of up to (2m-n)/2 bits (depending on error-tolerance and security parameters), where n is the bit-length and m is the entropy of W. The previously best known result, also of Dodis et al., extracted up to (2m-n)/3 bits (depending on the same parameters).

Program Committees

Eurocrypt 2020
Crypto 2019
TCC 2019
PKC 2018