C. Yuan and D. Qingkuan RCCA security for KEM+DEM style hybrid encryptions
Table II. The three hybrid paradigms and their security.
Hybrid paradigm Security results
KEM+DEM
IND-CCA + IND-CCA ) IND-CCA [6]
IND-RCCA + IND-RCCA ) IND-RCCA (by Theorem 1)
Tag-KEM/DEM
IND-CCA + One-time security ) IND-CCA [7]
IND-RCCA + One-time security » IND-RCCA (by the counterexample)
IND-RCCA + IND-RCCA ) IND-RCCA (by Theorem 4)
IND-tRCCA + One-time security ) IND-RCCA (by Theorem 5)
KEM/Tag-DEM IND-RCCA + IND-CCA ) IND-CCA (by Thoerem 6)
integrity of tag , one can just Message Authentica-
tion Code (MAC) the tag or use the same techniques
in constructing deterministic authenticated encryption
in [12].
The CCA security of KEM/Tag-DEM and the RCCA
one of KEM+DEM actually show that RCCA-secure KEM
is sufficient for constructing hybrid encryption, just as we
desired: for RCCA security, follow KEM+DEM, and for
CCA security, follow KEM/Tag-DEM. We summarize all
three hybrid paradigms related security results in Table II.
1.2. Further discussions and related works
1.2.1. Benign RCCA security for
tag-based schemes.
It should be noted that, from our work, a benign RCCA
security notions for Tag-KEM should be tRCCA secu-
rity. The result can be very easily generalized to tag-based
public-key encryptions (TBEs) [13], that is, a benign mal-
leability for TBEs should be also of the same tag.
1.2.2. The difference between Tag-DEMs
and DAEs.
Tag-DEMs are deterministic SKEs with tag, and we
only ask one-time CCA security but not authenticity;
this makes them weaker than deterministic authenticated
encryptions [12] and authenticated encryption with associ-
ated data [14].
1.2.3. Importance of KEM/Tag-DEM.
In [7], Abe et al. also showed how to obtain a CCA-
secure hybrid encryption from an RCCA-secure KEM by
making it to be a CCA-secure Tag-KEM. Their method can
be explained by our new paradigm in another way.
Comparing with Tag-KEM/DEM, one may think
KEM/Tag-DEM achieves less improvement. However,
CCA-secure DEMs and Tag-DEMs can be easily and effi-
ciently built, while CCA-secure KEMs and Tag-KEMs
cost much; weakening the security requirement of KEM to
RCCA security may be beneficial. In most KEMs, the valid
ciphertext of an encapsulated key is uniquely determined;
this makes it difficult to build efficient and natural RCCA-
secure KEM, especially when a rerandomizable one is
taken into consideration [4]. Nevertheless, as illustrated in
[1], a CCA-secure KEM may only achieve RCCA security
in practical protocols when allowing for arbitrary padding
to ciphertexts (in order to align the length) or more than one
representation of ciphertexts. That time, KEM/Tag-DEM
will achieve advantages over KEM+DEM paradigm.
KEM/Tag-DEM shows the diversity of hybrid encryp-
tions and has additional practical values. In practice, there
are always associated data to DEM [14]; thus, including
the ciphertext of KEM brings no significant difference in
efficiency and may “offload” as much cryptographic work
from the slower KEM part onto the faster DEM part. In
addition, in Tag-KEM/DEM, a receiver generally needs
the entire ciphertext to derive the encapsulated key, which
makes it extremely unsuitable for streaming processing,
while KEM/Tag-DEM suffers no such problem.
1.2.4. Further weakening.
In Tag-KEM/DEM, binding the ciphertext of DEM to
Tag-KEM weakens the requirement of DEM to one-time
security; one may think that in KEM/Tag-DEM, it might
be possible to only ask Chosen Plaintext Attack (CPA)
security for KEM. However, this makes it impossible for an
adversary against KEM to simulate the decryption oracle
for an adversary against the hybrid encryption. It is open to
show whether an even weaker security than RCCA security
works.
1.2.5. To achieve RCCA-secure
hybrid encryptions.
From the previous discussion, to achieve RCCA-secure
hybrid encryptions, we need RCCA-secure KEMs, RCCA-
secure DEMs, or tRCCA-secure Tag-KEMs. Because of
the aforementioned reasons, we do not have candidates
for RCCA-secure KEMs and tRCCA-secure Tag-KEM.
In addition, it has been pointed out in [1] that RCCA-
secure SKEs, thus RCCA-secure DEMs, can be given by
the“encrypt-then-authenticate” paradigm using a regular
secure MAC (but not a strong one), which means given
pairs of messages and their mac values, it is not possible to
find a valid mac value for any other messages but may be
possible to find a different valid mac value for someone of
these messages. Thus, a regular secure but not strong MAC
may help in obtaining an RCCA-secure hybrid encryp-
tions more efficient than CCA-secure ones. However, most
MAC schemes are deterministic, and the verification is car-
ried out by re-computation, so finding a different valid mac
value for the same message is impossible. A randomized or
multi-valued MAC is needed. Krawczyk [15] gives some
examples, but just conceptual.
Security Comm. Networks
2014; 7:1219–1231 © 2013 John Wiley & Sons, Ltd. 1221
DOI: 10.1002/sec