Cryptography Reference
In-Depth Information
1.1 Related Work
In EuroCrypt 2008, Cash, Kiltz and Shoup [10] proposed a new computational
problem called the
twin Die-Hellman (DH) problem
, i.e. given a random triple
of the form (
X
1
,X
2
,Y
)
, compute dh(
X
1
,Y
)and
dh(
X
2
,Y
), where dh is the DH function. They also proposed the
strong twin DH
problem
, which is the twin DH problem under the condition that an adversary
is given access to a corresponding decision twin DH oracle. They developed an
ingenious trapdoor test, which enables them to prove that the strong twin Die-
Hellman problem is as hard as the original Die-Hellman problem. They also
extended this technique to the bilinear Die-Hellman (BDH) problem.
Trapdoor test is the main contribution of [10]. Concretely speaking, when a
DH adversary
∈
G
3
for a cyclic group
G
is given a challenge (
g, X, Y
)=(
g, g
x
,g
y
), it creates a twin DH
challenge with a trapdoor by setting
X
1
=
X
and
X
2
=
g
s
/X
1
.Inthisway,a
linear relation with
two degrees of freedom
:
x
2
=
s
B
rx
1
is embedded into the twin
DH challenge. Based on the observation that the solution exponents (
x
1
y, x
2
y
)
are linear to (
x
1
,x
2
),
−
can answer the twin DH decision queries by testing if the
linear relationship holds accordingly between
Z
1
and
Z
2
.Thistrapdoortestcan
be extended to BDH problem in an analogous way without any diculty, since
the BDH problem is a natural extension of the DH problem in groups equipped
with a bilinear map. Using the trapdoor test as a tool, they proved that the strong
twin DH/BDH problem is as hard as the ordinary DH/BDH problem. Benefiting
from this result, they improved a bunch of cryptographic schemes by tailoring
them to fit the twin-type problem, such as Die and Hellman non-interactive key
exchange protocol [17], Cramer-Shoup encryption [15], Boneh-Franklin identity
based encryption [7], etc. Particularly, we call the tailoring method as
twinning
technique
.
For clarity of further discussion, we take a close look at how to apply the
twinning technique to Boneh-Franklin IBE (BF-IBE for short) scheme. The
twin BF-IBE uses two hash functions,
K
(outputs symmetric keys) and
H
(hashes identities to group elements), and a symmetric cipher (
Enc
,
Dec
). The
master public key is (
X
1
,X
2
), where
X
i
=
g
x
i
for
i
=1
,
2. The master pri-
vate key is (
x
1
,x
2
). The private key for an identity
ID
∈{
B
}
∗
is (
S
1
,S
2
)=
(
H
(
ID
)
x
1
,H
(
ID
)
x
2
). To encrypt a message
M
for identity
ID
,onechooses
y
0
,
1
∈
Z
p
at random and sets
Y
=
g
y
,
Z
1
=
e
(
H
(
ID
,X
1
))
y
,
Z
2
=
e
(
H
(
ID
,X
2
))
y
, derives
k
=
K
(
ID
,Y,Z
1
,Z
2
), encrypts
C
=
Enc
(
k, M
). To decrypt using the private key
(
S
1
,S
2
)for
ID
, one computes
Z
1
=
e
(
S
1
,Y
),
Z
2
=
e
(
S
2
,Y
),
k
=
K
(
ID
,Y,Z
1
,Z
2
),
then decrypts
M
=
Dec
(
k, C
). We highlight that this is essentially a KEM-DEM
construction.
We study the possible improvements brought by the twinning technique as
follows, with an emphasis on public key encryption schemes based on the DH-
type problems in the random oracle model [4].
1. Tighten the security reductions to the computational DH-type problems.
Public key encryption schemes based on the DH-type problems can be di-
vided into two groups, one is based on the decisional problem [6, 16, 19], the
other one is based on the computational problems [1, 7, 22]. In the provable
Search WWH ::
Custom Search