Information Technology Reference
In-Depth Information
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 1,
xy
zu
which means that
=
. Otherwise
outputs 0, which means that
z
∈
.
R1
Now, we evaluate the advantage of the guess of
. Let
a
∈
{0,1}
denote whether
a
=
0
xy
a
=
1
the input
z
is a random element in
(
) or
u
(
). Let
abort
be the event
aa
′
that
aborts. Then, we have Pr[
=
|
abort
]
=
1 / 2
. We assume that
does not
a
=
0
abort. If
, i.e.,
z
∈
, then the challenged signature has no information on
x
.
R1
a
′
=¬
a
=
1
, i.e.,
xy
Thus, Pr[
z
= , then
perfectly
simulates the real and thus
guesses correctly with the advantage
ʵ
. Therefore, we
obtain Pr[
0 |
abort
∧
a
==
0]
1 / 2
. If
′
=¬
a
1 |
abort
∧==
a
1]
1 / 2
+
ε
. Putting everything together, we obtain
the advantage of
's guess as follows:
x
y
x y
⋅
x
y
|Pr[
(( ,
uv u w u z
=
,
=
, )
∧=
(
z
u
))
=
0] - Pr[
(( ,
uv u w u z
=
,
=
, )
∧∈ =
(
z
))
0]|
R1
′
′
=|Pr[
a
==
0 |
a
1]-Pr[
a
==
0 |
a
0]|
′
′
=|1-Pr[
aa
==
1|
1]-Pr[
a a
= =
0 |
0]|
′
′
=|1-Pr[
abort
]Pr[
a
=
1 |
abort
∧
a
=
1]- Pr[
¬
abort
]Pr[
a
=
1|
¬
abort
∧
a
=
1]
′
′
-Pr[
a
bort
]Pr[
a
=
0 |
abort
∧
a
=
0]- Pr[
¬
abort
]Pr[
a
=
0 |
¬
abort
∧
a
=
0]|
=|1-Pr[
abort
](1/2+1/2)-Pr[
¬
abort
]((1/2+ )+1/2)|
ε
=Pr[
¬
abort
]
ε
¬
abort
denotes the probability that
does not abort. In the signing oracle
query,
aborts only when the backpatch is failure. The probability that a specific
signature causes the failure is at most
Pr[
]
4
h
qp
. In
SK
, as
cannot corrupt all the
signers, the probability that
does not abort is at least (1
/
−
1 / (
q
−
1))
. In the chal-
j
*
ID
. Thus the probability
lenge oracle query,
does not abort in this case if
selects
that
does
not
abort
in
this
case
is
1 /
q
.
To
sum
up,
j
Pr[
³
abort
]
(1
−
qp
/
4
) (1
⋅
−
1 / (
q
−
1))
⋅
1/
q
. Therefore, assuming
does not
h
j
4
abort, it has probability at least
ε ⋅−
(1
h
qp
/
) (1
⋅−
1 /
(
q
−⋅
)) /
q
in solving the
j
j
XDH problem.
Lemma 2.
If the basename is non-empty, our DAA scheme meets user-controlled
unlinkability under the XDH assumption.
Proof
. The processes of the proof are similar to the above lemma 1. Given a XDH
problem ( ,
uv
=
u
x
,
wuz
=
y
,)
as input where
u
∈
,,
xy
∈
and either
zu
=
xy
1
p
or
z
is a random element in
,
decides which
z
was given by interacting with
as follows.
Initialization.
The step is the same as that of lemma 1.
runs the Setup(1 )
κ
algo-
rithm, sets L
j
and L
S
empty, and sends
ipk
and
isk
to
.
Hash-2
: Let
q
′
be the expected number of unique H
2
queries.
chooses a random
h
}. If the basename
bsn
has been queried before,
returns the pre-
viously queried result on
bsn
to ensure consistency. Otherwise, if
bsn
is the
i
←{1, …,
q
′
h
i
unique
*
p
query on H
2
,
chooses a random
r
←
and sets
H(
bsn
):
=
w
r
. For rest of the
