Malléabilité (cryptographie)

La malléabilité est une propriété que peuvent posséder des protocoles cryptographiques. Un cryptosystème est dit malléable s’il est possible de transformer un chiffré d’un message m en un chiffré pour un message f(m) pour une fonction f connue sans connaître le message originel m ni obtenir d’information sur lui. Cette propriété n’est pas toujours désirable, puisqu’elle peut permettre à un attaquant de modifier le contenus de messages. Pour l'illustration, mettons qu’une banque chiffre une transaction de la forme (150,00€, #44), pour signifier « virement de 150,00€ pour le compte #44». Un attaquant sans connaître le message pourrait appliquer la fonction (x,y) \mapsto (100 \cdot x, 133), ce qui dans notre cas donnerait la transaction (15 000,00€, #133), qui correspond à la transaction de 15 000,00€ pour un compte cible: #133. En revanche cette propriété permet aussi de débloquer des fonctionnalités, comme le chiffrement homomorphe, qui permet d’exécuter des calculs sur d

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. [2]. Though constant, the rate of all known constructions in the split state model is very far from optimal (even with more than two states). In this work, we consider the question of improving the rate of splitstate non-malleable codes. In the "information theoretic" setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a "computationally" independent one. In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate-1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami [10] to show that the existence of one-way functions is necessary to achieve rate > 1/2 for such codes. Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal et al. [3]. This result is of independent interest.

Springer Int Publishing Ag2016

Leakage-resilient non-malleable codes

Divesh Aggarwal

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).

Springer2015

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Springer Int Publishing Ag2016

Leakage-resilient non-malleable codes

Divesh Aggarwal

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

Springer2015