difference (in bits) between the CT length and the message
length. |p| and |s| are the length (in bits) of a group element
and a seed, respectively. |q| is the length of the group order.
We ignore the cost comparison with the scheme in [13],
since it requires heavy computation, including pairing.
We also present an application of our result to analyse the
security of Baek et al.’s KEM scheme [6], which can be
viewed as our DDH-based scheme that does not tolerate
any leakage. We point out a flaw in the security proof of
Baek et al.’s KEM [6]. This flaw is inherited by the scheme
in [23]. Our general construction will unify the work of [6,
23, 24] and the corresponding proof will correct flaws
existing in the security proof in [6, 23].
1.3 Related work
The structure of our scheme previously appeared in some
KEM schemes [6, 26, 27]. Kiltz [26] proposes an
IND-CCA2-secure KEM based on the gap hashed Diffie–
Hellman problem, whose efficiency was later improved by
Lu et al. [27]. Baek et al. [6] proposed a variant of the
CS-KEM scheme, which has shorter public/private key pair
and slightly more efficient encapsulation than the original
Cramer–Shoup KEM scheme, but is proven to be (still)
IND-CCA2-secure. Recently, Li et al. [23] and Liu et al.
[24], respectively, proposed a CCA2-secure PKE scheme
under the DDH assumption that achieves higher leakage
rate using this technique.
2 Preliminaries
Notation: Let N denote the set of natural numbers. Let [n]
denote set {1, …, n}. Throughout the paper, let
k
[ N
denote the security parameter and 1
κ
denote the string of κ
ones. If S is a finite set, then |S| denotes the cardinality of
the set and s ← S denotes the operation of picking an
element s uniformly at random from S.Ifs is a random
variable, then |s| denote the bit-length of s.IfA is a
probabilistic algorithm, then y ← A(x;R) denotes the
operation of running A on input x and randomness R, and
assigning y the result. We write y ← A(x) for y ← A(x;R)
with a uniformly chosen R.
2.1 Statistical distance, min-entropy and
randomness extractor
Let X and Y be the two random variables over a finite domain
S. Denote by SD(X, Y ) the ‘statistical distance’ between X and
Y. Namely, SD( X, Y ) = (1/2)Σ
s ∈ S
|Pr[X = s]−Pr[Y = s ]|. The
‘min-entropy’ of X is H
∞
(X )=−log(max
s ∈ S
Pr[X = s]).
Dodis et al. [28] formalised the notion of ‘average
min-entropy’ that captures the remaining unpredictability of
X conditioned on Y. It is formally defined as
H
1
(X |Y ) =
− log E
yY
2
−H
1
(X |Y=y)
. Dodis et al. [28] proved the
following property of average min-entropy that is useful in
the security analysis of our scheme.
Lemma 1 [28]: Let X, Y and Z be random variables. If Y has 2
r
possible values, then
H
1
(X |(Y , Z)) ≥
H
1
(X |Z) − r.
Definition 1 (strong extractor): A function Ext:X×SY
is an average-case (ℓ,
e
)−strong extractor if for all pairs of
random variables (X, Z ) such that X [ X and
H
1
(X |Z) ≥ ℓ
the following inequality holds
SD (Z, s , Ext(X , s)), (Z, s, U
Y
)
≤
e
where s is uniform over S and U
Y
is uniform over Y.
2.2 Key derivation functions (KDFs) [5]
KDFs can be viewed as a special randomness extractor, which
extracts random bits from a uniformly distributed source.
Roughly speaking, a KDF associated with group G takes as
input two random elements (a, b) [ G
2
and outputs a key
K. Let m be the key length which is determined by the
security parameter κ. The security of KDF is formally
captured by defining the advantage function Adv
KDF
G,B
(
k
)of
a 0/1-valued PPT algorithm B as
Adv
KDF
G,B
(
k
) := Pr[B(a, KDF(a, b)) = 1] − Pr B a,
K
′
= 1
where a, b G and
K
′
{0, 1}
m
.
We say that KDF is secure if Adv
KDF
G,B
(
k
) is negligible in κ
for any 0/1-valued PPT algorithm B.
From [5], KDFs can be built from pairwise independent
functions or standard hash functions. Note that a secure
KDF may be injective or lossy (meaning that the size of its
image is smaller than the size of its domain). In addition,
an injective KDF may be efficiently invertible, meaning that
b is recoverable from KDF(a, b). We give an example of
invertible KDF in Appendix 1.
2.3 Target collision-resistant hashing
Informally, we say that a function TCR:X → Y is a target
collision-resis tant (TCR) hash function, if given a random
pre-image x ∈ X,itishardtofind x′ ≠ x with TCR(x′)=TCR(x).
Table 1 Efficiency comparison for IND-KL-CCA2-secure PKE/KEM schemes
Schemes Operation cost PK size CT overhead Leakage rate Assumption
Enc. Dec. #bits #bits
Naor and Segev [8] 3E + 1ME 2ME 5|p|3|p|+|s| 1/6 DDH
Kurosawa et al. [25] 2E + 1ME 1ME 4|p| (2 + 1/3) |p|+|s| 1/12 DDH
Liu et al. [22] 2E + 2ME 2ME 5|p|3|p|+|q| 1/6 DDH
Liu et al. [24] 3E + 1ME 2ME 4|p|3|p|+|s| 1/4 DDH
Li et al. [23] 3E + 1ME 2ME 4|p|3|p|+|s| 1/4 DDH
ours 1 (KEM) 4E 2ME 4|p|3|p|+|s| 1/4 DDH
Dodis et al. [13] ——O(κ)|p| ≥(36 + 9/δ)|p|1− δ DLIN (pairing)
Kurosawa et al. [25] 3E + 1ME 1ME 7|p| (3 + 1/3)|p|+|s| 1/18 DLIN
ours 2 (KEM) 3E + 2ME 2ME 7|p|4|p|+|s
| 1/6 DLIN
www.ietdl.org
34
&
The Institution of Engineering and Technology 2014
IET Inf. Secur., 2015, Vol. 9, Iss. 1, pp. 32–42
doi: 10.1049/iet-ifs.2013.0173