Paper 2014/807

Leakage-resilient non-malleable codes

Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski

Abstract

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this state. One of the popular tools used to provide tamper-resistance are the \emph{non-malleable codes} introduced by Dziembowski, Pietrzak and Wichs (ICS 2010). These codes can be defined in several variants, but arguably the most natural of them are the information-theoretically secure codes in the k-split-state model (the most desired case being k=2). Such codes were constucted recently by Aggarwal et al.~(STOC 2014). Unfortunately, unlike the earlier, computationally-secure constructions (Liu and Lysyanskaya, CRYPTO 2012) these codes are not known to be resilient to leakage. This is unsatisfactory, since in practice one always aims at providing resilience against both leakage and tampering (especially considering tampering without leakage is problematic, since the leakage attacks are usually much easier to perform than the tampering attacks). In this paper we close this gap by showing a non-malleable code in the $2$-split state model that is secure against leaking almost a $1/12$-th fraction of the bits from the codeword (in the bounded-leakage model). This is achieved via a generic transformation that takes as input any non-malleable code $(\Enc,\Dec)$ in the $2$-split state model, and constructs out of it another non-malleable code $(\Enc',\Dec')$ in the $2$-split state model that is additionally leakage-resilient. The rate of $(\Enc',\Dec')$ is linear in the rate of $(\Enc,\Dec)$. Our construction requires that $\Dec$ is \emph{symmetric}, i.e., for all $x, y$, it is the case that $\Dec(x,y) = \Dec(y,x)$, but this property holds for all currently known information-theoretically secure codes in the $2$-split state model. In particular, we can apply our transformation to the code of Aggarwal et al., obtaining the first leakage-resilient code secure in the split-state model. Our transformation can be applied to other codes (in particular it can also be applied to a recent code of Aggarwal, Dodis, Kazana and Obremski constructed in the work subsequent to this one).