Cryptography Reference
In-Depth Information
3. Check that
g
1
∈
G
∗
.Thecase
g
1
=1
G
means that
w
j
=
−
x
for some easily
identifiable
w
j
,atwhichpoint
would be able to solve the challenge directly.
Similarly, check that
g
2
∈
G
∗
.Thecase
g
2
=1
G
means that
w
j
=
B
−
y
for
some easily identifiable
w
j
,atwhichpoint
B
would be able to solve the
challenge directly. We thus assume that all
w
j
−
x
,
w
j
−
y
.
=
=
4. For any
i
=1
,...,q
−
B
to construct the triple (
w
0
+
1, it is easy for
). To see this, write
f
i
(
z
)=
f
(
z
)
/
(
z
+
w
i
)=
q−
2
w
i
,g
1
/
(
x
+
w
i
)
1
,g
1
/
(
y
+
w
i
)
2
i
=0
d
i
z
i
.
=
g
1
f
i
(
x
)
=
q−
2
=
g
2
f
i
(
y
)
=
q−
2
Then
g
1
i
=0
(
g
1
x
i
)
d
i
and
g
1
i
=0
(
g
2
y
i
)
d
i
.
x
+
w
i
1
y
+
w
i
2
5.
B
computes
q−
2
,T
1
=
e
(
T
1
, g
1
f
(
x
)+
c
0
)=
e
(
g
1
, g
1
)
f
(
x
)
2
−c
0
(
g
1
x
i
)
c
i
+1
=
g
1
f
(
x
)
−c
0
T
1
=
,
x
x
i
=0
q−
2
,T
2
=
e
(
T
2
, g
2
f
(
y
)+
c
0
)=
e
(
g
2
, g
2
)
f
(
y
)
2
−c
0
(
g
2
y
i
)
c
i
+1
=
g
2
f
(
y
)
−c
0
T
2
=
.
y
y
i
=0
We will use these values throughout the simulation.
Setup.
B
sets the master public key
mpk
=(
g
1
,g
2
,u
1
,u
2
), implicitly sets the
master secret key
msk
=(
x − w
0
,y− w
0
), which is unknown to
B
.
B
generates
aset
S
containing
w
0
,and(
w
0
+
w
i
)for
i
=1
,...,q
−
1.
H
1
-
queries.
At any time algorithm
A
can query the random oracle
H
1
.To
respond to these queries
indexed by
ID
i
(as explained below). We refer to this list as the
L
1
list which is initially empty.
When
B
maintains a list of tuples
ID
i
,W
i
A
queries the oracle
H
1
at a point
ID
i
algorithm
B
responds as follows:
1. If
ID
i
already appears on
L
1
in a tuple
ID
i
,W
i
B
then
responds with
H
1
(
ID
i
)=
W
i
∈
Z
p
.
2. Otherwise,
B
randomly picks an element from
S
,
- If the element has the form
w
0
+
w
j
,
B
adds the pair
ID
i
,W
i
=
w
0
+
w
j
with
H
1
(
ID
i
)=
w
0
+
w
j
.
- If the element is
w
0
,
B
adds the pair
ID
i
,w
0
into
L
1
and responds
A
with
H
1
(
ID
i
)=
w
0
.
- Delete this element from
S
.
Note that either way
H
1
(
ID
i
) is uniform in
into
L
1
and answers
A
Z
p
and independent of
A
's current
view as required.
H
2
-
queries.
To respond the queries to
H
2
oracle,
B
maintains a list of tuples
indexed by (
v
i,
1
,v
i,
2
) (as explain below). We refer to this list as the
L
2
list which is initially empty. To respond to a query on (
v
i,
1
,v
i,
2
),
v
i,
1
,v
i,
2
,θ
i
B
carries
out the following operations:
1. If there is a tuple indexed by (
v
i,
1
,v
i,
2
)on
L
2
,
B
responds with
θ
i
.
n
, runs the self-decryption func-
tion (as described below in the simulation algorithm of decryption oracle)
with composing
2. Otherwise,
B
randomly picks a
θ
i
∈{
0
,
1
}
ID
, C
v
i,
1
,v
i,
2
,θ
i
and each tuple
in the current
R
list
Search WWH ::
Custom Search