2015 | OriginalPaper | Buchkapitel
Tamper Detection and Continuous Non-malleable Codes
verfasst von : Zahra Jafargholi, Daniel Wichs
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
WeN consider a public and keyless code (
Enc,Dec
) which is used to encode a message
m
and derive a codeword
c
=
Enc
(
m
). The codeword can be adversarially tampered via a function
$f \in{\mathcal F}$
from some “tampering function family”
$\mathcal F$
, resulting in a tampered value
c
′ =
f
(
c
). We study the different types of security guarantees that can be achieved in this scenario for different families
$\mathcal{F}$
of tampering attacks.
Firstly, we initiate the general study of
tamper-detection codes
, which must detect that tampering occurred and output
Dec
$(c') = \bot$
. We show that such codes exist for any family of functions
${\mathcal F}$
over
n
bit codewords, as long as
$|{\mathcal F}| < 2^{2^n}$
is sufficiently smaller than the set of all possible functions, and the functions
$f \in{\mathcal F}$
are further
restricted
in two ways: (1) they can only have a
few fixed points
x
such that
f
(
x
) =
x
, (2) they must have
high entropy
of
f
(
x
) over a random
x
. Such codes can also be made efficient when
$|\mathcal{F}| = 2^{{\rm poly(n)}}$
.
Next, we revisit
non-malleable codes
, which were introduced by Dziembowski, Pietrzak and Wichs (ICS ’10) and require that
Dec
(
c
′) either decodes to the original message
m
, or to some unrelated value (possibly
$\bot$
) that doesn’t provide any information about
m
. We give a modular construction of non-malleable codes by combining tamper-detection codes and leakage-resilient codes. The resulting construction matches that of Faust et al. (EUROCRYPT ’14) but has a more modular proof and improved parameters.
Finally, we initiate the general study of
continuous non-malleable codes
, which provide a non-malleability guarantee against an attacker that can tamper a codeword multiple times. We define several variants of the problem depending on: (I) whether tampering is
persistent
and each successive attack modifies the codeword that has been modified by previous attacks, or whether tampering is non-persistent and is always applied to the original codeword, (II) whether we can “
self-destruct
” and stop the experiment if a tampered codeword is ever detected to be invalid or whether the attacker can always tamper more. In the case of persistent tampering and self-destruct (weakest case), we get a broad existence results, essentially matching what’s known for standard non-malleable codes. In the case of non-persistent tampering and no self-destruct (strongest case), we must further restrict the tampering functions to have few fixed points and high entropy. The two intermediate cases correspond to requiring only one of the above two restrictions.