PKE WITH SO-CCA SECURITY BASED ON THE DDH ASSUMPTION
Hemenway et al. [14] gave modular construction of IND-SO-CCA2 secure encryption from a
certain family of tag-based encryption system using a variant of the Canetti–Halevi–Katz paradigm.
However, because one-time signatures cannot be used (because the adversary would have to obtain
one-time private keys for opened ciphertexts), they used chameleon hash functions to apply the
Canetti–Halevi–Katz paradigm. The length of ciphertext is O(1), and the length of public/private
key and computation complexity is of O.n/ with n the number of challenge ciphertexts. Hofheinz
et al. [15] showed how to avoid the O.n/ complexity for the sender and in the public/private key
size. The construction also involves chameleon hash functions, and the security reduction is loose.
Fehl et al . [16] considered how to construct schemes with NC-CCA2 security on the basis of hash
proof systems and L-Cross-Authentication codes. They also proved that NC-CCA2 security implies
SEM-SO-CCA2 security. Their constructions are free of chameleon hash functions, but the number
of group elements in the ciphertext is the same as the number of bits in the plaintext. On the other
hand, Huang et al. [17] showed that the NC-CCA security proof in [16] is flawed by showing an
attack. Hence, whether their scheme in [16] is SEM-SO-CCA2 secure is still open.
1.2. Our contributions
In this paper, we focus on IND-SO-CCA2. We show that a PKE scheme with IND-SO-CCA2
security can be constructed directly on the basis of the DDH assumption. Chameleon hashing is
not necessary to achieve IND-SO-CCA2 security, because the IND-SO-stag-wCCA2 PKE scheme
in [14] based on the DDH assumption can be modified to obtain IND-SO-CCA2 security without
chameleon hashing.
Our scheme can be regarded as a variant of the DDH-based construction of Hemenway et al. [14]
but free of chameleon hash functions. The scheme has the same efficiency as the original construc-
tion: encryption needs O.n/ exponentiations, where n is the number of challenge ciphertexts, and a
ciphertext consists of five elements (four group elements and one exponent).
2. PRELIMINARIES
Let H denote a set, jHj denote the cardinality of the set H,andh H denote sampling element h
uniformly random from set H.IfH is a probability distribution, then h H denotes sampling h
according to the distribution. If A./ is an algorithm, then a A./ denotes running the algorithm
and obtaining a as an output, which is distributed according to the internal randomness of A./.Let
PPT denote probabilistic polynomial time. A function f./ is negligible if for every c>0there
exists a
c
such that f ./ < 1=
c
for all >
c
.
Definition 1
Let H be a set of hash functions, mapping X to Y.Letk
$
Hindex.1
/ denote the index
generation algorithm. Each index k 2f1, 2, , jHjg determines a hash function H
k
2 H. Then,
H is collision-resistant (CR) if for any polynomial-time adversary A, its advantage Adv
CR
H,A
./,
defined as
Adv
CR
H,A
./ D Pr
H
k
.x
1
/ D H
k
.x
2
/, x ¤ x
0
j k
$
Hindex.1
/I x
1
, x
2
$
A.H
k
/
,
is negligible in .
Definition 2
Let H be defined as Definition 1. Then H is target collision-resistant (TCR) if for any PPT adversary
A, its advantage Adv
TCR
H,A
./,definedas
Adv
TCR
H,A
./ D Pr
H
k
.x/ D H
k
.x
0
/, x ¤ x
0
j k
$
Hindex.1
/I x 2 X , x
0
$
A.H
k
, x/
,
is negligible in .
Copyright © 2013 John Wiley & Sons, Ltd. Concurrency Computat.: Pract. Exper. (2013)
DOI: 10.1002/cpe