## CryptoDB

### Bhavana Kanukurthi

#### Affiliation: Indian Institute of Science, India

#### Publications

**Year**

**Venue**

**Title**

2019

JOFC

Four-State Non-malleable Codes with Explicit Constant Rate
Abstract

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.

2008

EPRINT

An Improved Robust Fuzzy Extractor
Abstract

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

#### Coauthors

- Prabhanjan Ananth (1)
- Nishanth Chandran (4)
- Vipul Goyal (1)
- Yael Tauman Kalai (1)
- Sai Lakshmi Bhavana Obbattu (3)
- Rafail Ostrovsky (2)
- Srinivasan Raghuraman (2)
- Leonid Reyzin (2)
- Amit Sahai (1)
- Sruthi Sekar (3)