Cryptography Reference
In-Depth Information
Prover
Verifier
Z
n
pick
λ
∈
Z
2
,
a
i
,
b
i
∈
Z
2
,
r
i
∈
r
i
g
a
1
g
b
2
x
i
,
w
i
=(
−
a
i
i
u
i
=
1
)
w
i
←−−−−−−−−−−−−−−
u
i
,
compute
v
i
=
χ
(
u
i
)
λ
−−−−−−−−−−−−−−→
y
i
)
λ
get
λ
from
w
i
/
v
i
=(
i
/
b
i
←−−−−−−−−−−−−−−
λ
−−−−−−−−−−−−−−→
r
i
,
a
i
,
check
u
i
,
w
i
check
λ
,
λ
Figure 11.8.
MOVA denial protocol.
Denial algorithm.
To deny a signature
σ
=
(
z
1
,...,
z
t
) for a message
X
, we recalculate
x
1
,...,
x
t
and then run the proof of noninterpolation below. As depicted in Fig. 11.8,
this consists of
iterations of the following protocol.
Z
n
,
a
1
,...,
1. The verifier picks
r
1
,...,
r
t
∈
a
s
,
b
1
,...,
b
s
,λ
∈
Z
2
, computes
r
i
g
a
1
g
b
2
x
i
1)
a
i
z
i
u
i
=
mod
n
and
w
i
=
(
−
for
i
=
1
,...,
t
. He sends the
w
t
) to the prover.
2. The prover computes
y
i
=
(
u
1
,...,
u
t
) and (
w
1
,...,
(
x
i
/
p
) and
v
i
=
(
u
i
/
p
) for
i
=
1
,...,
t
. Since
z
i
)
λ
for all
i
and that there must be some
w
i
/v
i
mod
n
should be equal to (
x
i
/
i
for which
x
i
=
z
i
, the prover can recover
λ
. In case of inconsistency he picks
λ
at random. He sends a commitment to
λ
.
3. The verifier discloses (
r
i
,
a
1
,
b
i
) for
i
=
1
,...,
t
.
4. The prover verifies the consistency with (
u
i
,
w
i
) and
λ
for
i
=
1
,...,
t
. He then
opens the commitment.
5. The verifier verifies the commitment and checks that
λ
is correct.
We can prove that this protocol is complete, sound, and zero-knowledge. More precisely,
it cannot succeed with probability greater than 2
−
if the signature is valid.
11.3.2
Other Special Purpose Digital Signatures
Group signature.
We may need to have a signature scheme for a group of participants:
we want to certify that someone from a given group has signed a document with-
out disclosing who really did. Group signatures usually require a heavy process for
welcoming or revoking members, but have pretty efficient signature and verification
schemes.
Ring signature.
Some special groups are ad hoc groups. They are not controlled by
any means of membership and there is no formal process. Anyone can indeed invent
a group by describing who is member and produce a proof that someone from this
list did sign a document. (The main drawback is that the proof is pretty long.) These
ad hoc groups are called rings.
Search WWH ::
Custom Search