Cryptography Reference
In-Depth Information
security paradigm, the standard security notions (CPA and CCA) of pub-
lic key encryption systems are formally defined via an interactive decisional
problem: it is hard for an adversary to distinguish the challenge ciphertext
is the encryption of
M
0
or
M
1
. When the underlying hard problem is also a
decisional problem, the simulator always outputs its solution based on the
adversary's output. When the underlying hard problem is a computational
problem, a common proving technique in the random oracle model is the
simulator extracting the solution from a randomly picked entry in the asso-
ciated random oracle query list, whose correctness is based on the assertion
that if the adversary can answer the decision problem with advantage
,
then it must issue the associated query related to the challenge with proba-
bility at least 2
. However, the “random picking” step loses a factor of
Q
h
in
the security reduction, where
Q
h
is the maximum number of random oracle
queries an adversary can make. If applying the twin technique to the original
scheme, the simulator can identify the wanted query precisely with the help
of a corresponding decision oracle. Thereby the security reduction can be
tighten by a multiplicative factor
Q
h
immediately.
2. Facilitate a kind of redundancy free KEM construction without making a
stronger assumption.
For the public key encryption schemes based on the DH/BDH problem,
there exists a simple and elegant KEM construction which derives a sym-
metric key from a DH/BDH tuple. For example, in DHIES [1] (based on
the strong DH assumption), Abdalla, Bellare and Rogaway constructed the
KEM as
k
:=
K
(
y
r
), where
y
=
g
x
is the public key. The associated ci-
phertext
C
is
g
r
. In [20], Libert and Quisquater proposed a redundancy free
variant of BF-IBE (based on the Gap-BDH assumption). Their scheme essen-
tially adopts the KEM-DEM methodology, and the ID-KEM is constructed
as
k
:=
K
(
e
(
g
a
,g
b
)
r
) [20], while
g
a
is the master public key and
g
b
is the
public key of
ID
. The associated ciphertext
C
is
g
r
. It is easy to see that
(
g
x
,g
r
,y
r
) is a DH tuple, and (
g
a
,g
b
,g
r
,e
(
g
a
,g
b
)
r
) is a BDH tuple. Com-
pare to other KEM constructions, the advantage of this special construction
is that it is redundancy free. So it is not very surprisingly that the associated
security reduction requires a decisional DH/BDH oracle available to distin-
guish “valid” decapsulation queries. This explains why such a kind of KEM
construction has to resort to the strong DH/BDH assumptions. Via applying
twinning technique to this kind of KEM construction, the security can be
reduced to the ordinary assumption at a minor cost of the ciphertext size
and the computation overhead. For example, Cash, Kiltz and Shoup [10] im-
proved ElGamal encryption and BF-IBE in this way. The resulting schemes
are redundancy free.
1.2 Our Contributions
Cash, Kiltz and Shoup [10] mentioned that their ideas can also be applied to
the Sakai-Kasahara IBE scheme (SK-IBE for short) [22] based on the BDHI
Search WWH ::
Custom Search