Cryptography Reference
In-Depth Information
extraction queries,
Q
d
decapsulation queries, and at most
Q
h
i
queries on
H
i
for
1
≤
i
≤
2
respectively. Then there exists an algorithm
B
to solve the
(
Q
h
1
+1)
-
BDHI
problem with advantage
1
1
Q
h
1
2
Q
h
1
p
Adv-BDHI
B
≥
2
·
−
and running time
O
(
time
(
A
)).
Proof.
We first build an algorithm
B
that uses
A
to solve the strong twin
q
-BDHI problem in
is given as input a strong twin
q
-BDHI instance
(
g
1
, g
1
x
,..., g
1
x
q
;
g
2
, g
2
y
,..., g
2
y
q
) and is expected to output
Z
1
=
e
(
g
1
, g
1
)
1
/x
and
Z
2
=
e
(
g
2
, g
2
)
1
/y
.
G
.
B
B
works by interacting with
A
in an
IND
-
ID
-
CCA
game
as follows:
Preparation.
Same as in the proof of twin SK-IBE scheme in Section 3.
Setup.
Same as in the proof of twin SK-IBE scheme Section 3.
H
1
-
queries.
Same as in the proof of twin SK-IBE scheme Section 3.
H
2
-
queries.
Same as in the proof of twin SK-IBE scheme Section 3, except that
we replace the self-decryption funtion with the corresponding self-decapsulation
function (as explained below).
Phase 1: Private key queries.
Same as in the proof of twin SK-IBE scheme 3.
Phase 1: Decapsulation queries.
In order to simulate the decapsulation or-
acle coherently with a
H
2
oracle,
. We refer
to this list as the
R
list, which is initially empty. The
R
list is used to store the
invalid ciphertexts issued by
B
maintains a list of tuples
ID
j
,C
j
A
.Let
ID
,C
i
be a decapsulation query issued by
algorithm
A
,where
C
i
=
U
i,
1
,U
i,
2
,V
i
.
B
simulates the decapsulation oracle to
answer this query as follows:
-If
B
can extract the private key
d
ID
i
=(
d
i,
1
,d
i,
2
)of
ID
i
,
B
uses the private
key to process the decapsulation query normally.
-If
can not extract the corresponding private key, for every tuple (
v
1
, v
2
, θ
)
on
L
2
,
B
B
runs the following test with composing
ID
i
,U
i,
1
,U
i,
2
,V
i
and each
v
1
, v
2
, θ
tuple
on the
L
2
list as input,
1. Compute
t
i,
1
=
u
1
g
H
1
(
ID
i
)
1
,
t
i,
2
=
u
2
g
H
1
(
ID
i
)
2
;
θ
,(
r
1
, r
2
)=
H
3
(
σ
).
2. Compute
σ
=
V
i
⊕
3. Check if
U
i,
1
=
t
r
1
i,
1
,
U
i,
2
=
t
r
2
i,
2
,
v
1
=
e
(
g
1
,g
1
)
r
1
,and
v
2
=
e
(
g
2
,g
2
)
r
2
simultaneously.
4. If so, return true. Else, continue the test with the next input.
5. Finally, if no input can go through this test, return false.
If the test returns true,
returns the associated
M
.Otherwise,
B
B
returns
⊥
into the
R
list. Particularly, we refer to
the above test as the
self-decapsulation function
.
Challenge.
Once
to
A
and inserts
ID
i
,U
i,
1
,U
i,
2
,V
i
decides that Phase 1 is over it outputs a target identity
ID
∗
on which it wishes to be challenged.
A
B
operates as follows:
Search WWH ::
Custom Search