Information Technology Reference
In-Depth Information
r
1)
searches the log of H
1
queries and retrieves
r
where
H(
bsn
):
=
w
.
sets
J
:
=
w
and
r
Kz
2)
The rest of the signing algorithm is the same as the Case 2 in the
Sig
oracle;
3)
sends the resulting to
:
=
;
*
σ
.
b
′
∈
Output.
In the end,
outputs
{0,1}
as the guess for
b
. If
bb
′
=
, then
outputs
xy
zu
1, which means that
.
The evaluation of advantage of the guess of
is the same as that of lemma 1. In
the signing oracle query,
aborts when the backpatch is failure and
=
. Otherwise
outputs 0, which means that
z
∈
R1
*
bsn
=
bsn
. The
qp
⋅ . In
SK
, as
cannot corrupt all the signers, the
probability that
does not abort is at least (1
6
probability is at most
/
h
h
−
1 / (
q
−
1))
. In the challenge oracle
j
*
bsn
. Thus the probability that
query,
does not abort in this case if
selects
*
ID
and
qq
′
does
not
abort
in
this
case
is
1 /
⋅
.
To
sum
up,
j
h
6
′
q
′
Pr[
¬
abort
]
≥
(1
−
qp
/
⋅
) (1
⋅
−
1/ (
q
−⋅
1)) 1/
q
⋅
. Therefore, assuming
does
h
h
j
j
h
ε
⋅−
(1
qpq
/
6
⋅ ⋅−
′
) (1
1 / (
q
− ⋅
1)) 1 /
qq
⋅
′
not abort, it has probability at least
in
h
h
j
j
h
solving the XDH problem.
Theorem 4
.
Under the q-SDH assumption, our DAA scheme is user-controlled trace-
able. More specifically, if there is an adversary
that succeeds with a non-negligible
probability to break the user-controlled traceability game, then there is a simulator
running in polynomial-time that solves the q-SDH problem with a non-negligible
probability.
Proof
. In this proof, we show how to construct a simulator
that solves the
q
-SDH
problem by interacting with
that succeeds with a non-negligible probability to
break the user-controlled traceability game. We use a technique from Boneh and
Boyen[28] that, given
2
q
gg r
γ
γ
γ
γ
(,
gg
,
,
,
,
)
, one more SDH instance
1
1
1
2
Bilinear
*
g
γ +
*
x
can be transformed into a solution to the
q
-SDH problem. We now
describe how
interacts with
as follows:
Initialization.
is given the above
q
-SDH problem parameters, and generates the
issuer public key as follows: Assuming that
will query the oracle
SndToI
with
q
-1
distinct values
1/ (
x
)
(
,
1
xx
−
,
,
∈
*
ab
,,
θ ←
and com-
*
Xx
=
=
{
ii
.
chooses
1
q
1
p
p
1,
,
q
−
1
g
θγ
′
=
⋅
f
()
q
i
−
=
1
1
putes
where
f
()
γ
=+
b
(
a
)
⋅∏
(
γ
+
x
)
.
sets the issuer public key
1
1
i
and sends
ipk
to
.
Hash
: If the query string has been queried,
returns the previously queried result
to ensure consistency. Otherwise,
chooses a value uniformly at random from
,
,
peg g
, ,
′
,
, H, H, H,H, H,
g
γ
)
ipk
=
(,
2
T
1
2
1
2
3
αβ
2
(the result of H, H) or (the result of H) or {0,1}
L
(the result of H
α
,H
β
).
AddU
: Given a new signer with
ID
from
's query.
can freely choose a value
from the set
X
as the signer secret key
sk
and removes the selected value from the set
X
.
generates the signing key
*
p
xf
⋅⋅
θγ
()
θγ
⋅
f
()
′
x
/ (
γ
+
x
)
′
1/ (
γ
+
x
)
sigk
=
(
g
,
g
)
=
(
g
,
g
)
where
i
i
i
i
i
i
i
1
1
1
1
f
()
γ
=
f
()/(
γ
γ
+
x
)
= ∏
q
(
γ +
x
)
, stores (,
ID
xsigk
in L
j
and adds
,
)
i
i
j
=≠
1,
j
i
j
i
i
ID
→
HS
. At one point,
selects one query and sets
sk
=
a
and signing key
ab
⋅⋅⋅
θγ
f
′
()
b
⋅⋅
θγ
f
′
()
′
−
=
∏+, stores
q
i
1
1
(
*
sigk
=
(
g
,
g
)
where
f
()
γ
=
γ
x
)
(
ID
,
sk sigk
,
)
in L
j
1
1
ID
to HS.
SndToI
:
requests for creating a new signer with
ID
and
i
x
∈ .
runs the
Join/Issue protocol as the issuer by interacting with
as the signer, and generates the
signing key
and adds
*
xf
⋅⋅
θγ
()
θγ
⋅
f
()
sigk
=
(
g
,
g
)
as before.
stores (,
ID x
,
sigk
)
in L
j
and
i
i
i
i
1
1
i
i
adds
ID
to CS.
