Cryptography Reference
In-Depth Information
always, except perhaps with negligible probability) to find a different valid tag
t
=
t
on
m
. This requirement is not too restrictive because for it to hold it suffices that the
MAC has
unique tags
in the sense that, for every key
k
and every message
m
, there
is a unique tag
t
such that the pair
is valid. This property holds whenever
Mac
is a deterministic algorithm, which is often the case and, of course, both the basic
CBC-MAC and CMAC have unique tags.
Using
(
m
,
t
)
E
and
I
, we define an encryption scheme
E
I
=
(
Gen
,
Enc
,
Dec
)
,as
follows:
are run on input 1
n
, producing
keys
k
1
,
k
2
, respectively. The output is the ordered pair
•
Gen
: The key generation algorithms of
E
and
I
(
k
1
,
k
2
)
.
•
Enc
: On input a key
(
k
1
,
k
2
)
and a message
m
,
m
is encrypted with the encryption
algorithm of
and key
k
1
producing a ciphertext
c
, and then the MAC tag
t
of
c
is computed using key
k
2
. The output is the ordered pair
E
(
c
,
t
)
.
•
Dec
: On input a key pair
(
k
1
,
k
2
)
and a ciphertext
(
c
,
t
)
, the verification algorithm
of
. If verification fails
then the decryption algorithm fails, otherwise
Dec
outputs the result of decrypting
c
with
I
is used with key
k
2
to verify the message/tag pair
(
c
,
t
)
E
using key
k
1
.
The security result is then the following:
Theorem 5.2
If
E
is a CPA secure private-key encryption scheme and
I
is a SUF-
CMA secure MAC, then
E
I
is a CCA secure private-key encryption scheme.
Sketch of proof
We explain the basic idea—which is very simple—underlying the
proof of the theorem and refer, e.g., to [109, Theorem 4.20] for a detailed proof
as well as for further background on this result and its significance. Let us call the
ciphertext
(
c
,
t
)
valid
if the verification algorithm of the MAC
I
accepts
t
as a valid
I
tag for
c
. Since
is UF-CMA secure, the adversary has negligible probability of
generating any valid ciphertext (i.e., a forgery in experiment
Mac
uf-cma
) except if
the ciphertext was generated by the honest users or was provided to the adversary by
the
A
,
I
(
n
)
E
I
-encryption oracle. Inmore detail, in experiment
PrivK
ind
−
cca
has access
to both an encryption and a decryption oracle. Some queries to the latter may be about
ciphertexts obtained from querying the former, but these queries do not give
(
n
)
,
A
A
,
E
I
new
information as it already knew the plaintext from some previous encryption query.
Thus the only potentially interesting decryption queries are those about ciphertexts
that
A
has not obtained from valid encryptions. But, as indicated above, in order to
construct such a ciphertext
A
has to output a forgery in experiment
Mac
uf-cma
A
A,I
(
n
)
which it can only do with negligible probability since
A
will not gain information from these queries either and this amounts to saying that
the decryption oracle only gives useful information with negligible probability and
hence is essentially useless. Therefore, to prove that
I
is UF-CMA secure. Thus
E
I
is CCA secure it is sufficient
to show that it is CPA secure and it is easy to see that this property follows from the
fact that
is CPA secure by hypothesis.
The previous discussion did not take into account that
E
might possibly construct
a valid ciphertext which is not a forgery in experiment
Mac
uf-cma
A
A,I
(
)
n
if, when it
