Cryptography Reference
In-Depth Information
Prover
Verifier
x
−−−−−−−−−−−−−−→
y
←−−−−−−−−−−−−−−
∈
Z
n
pick
x
Z
n
pick
y
∈
a
2
−−−−−−−−−−−−−−→
x
,
r
,
a
1
,
r
2
g
a
1
g
a
2
split
xy
=
check
x
,
xy
2
Figure 11.6.
MOVA key validation protocol.
malicious verifiers should learn no other information from the protocols but the validity
or invalidity of signatures.
As
an
example
we
describe
here
the
MOVA
scheme
designed
by
Jean
Monnerat and Serge Vaudenay which is based on quadratic residuosity.
1
It depends
on several security parameters
m
,
t
,
k
,
. In a typical setting we can propose
m
=
t
=
k
=
=
30.
Key setup.
We take two different odd prime numbers
p
and
q
and compute
n
=
pq
.
We take two elements
g
1
,
g
2
∈
Z
n
such that (
g
1
/
=
(
g
2
/
=−
1, (
g
1
/
=−
n
)
n
)
p
)
1,
and (
g
2
/
=+
1. Note that it suffices to use the Chinese Remainder Theorem with a
nonquadratic residue (resp. a quadratic residue) in
Z
p
and a quadratic residue (resp. a
nonquadratic residue) in
Z
q
p
)
g
2
). The
secret key is
p
. In order to prove that the generated key is valid, the scheme requires a
special protocol. As depicted in Fig. 11.6, this consists of
m
iterations of the following
protocol.
to make
g
1
(resp.
g
2
). The public key is (
n
,
g
1
,
Z
n
1. The prover picks
x
∈
at random and sends a commitment to
x
to the
verifier.
2. The verifier picks
y
Z
n
at random and sends it to the prover.
∈
r
2
g
a
1
g
a
2
Z
n
and
a
1
,
3. The prover looks for
r
∈
a
2
∈
Z
2
such that
xy
≡
(mod
n
).
2
1)
a
1
+
a
2
,
and computes a square root
r
of
xyg
−
a
1
g
−
a
2
mod
n
by using the Tonelli algo-
rithm and the factorization of
n
. He then reveals
r
1)
a
1
,
a
2
such that (
xy
For this he takes
a
1
such that (
xy
/
p
)
=
(
−
/
n
)
=
(
−
,
a
1
,
a
2
and opens the com-
mitment to
x
.
4. The verifier checks the commitment for
x
and that
xy
r
2
g
a
1
g
a
2
≡
(mod
n
).
2
We can prove that this protocol is complete, sound, and zero-knowledge. More precisely,
it cannot succeed with probability greater than 2
−
m
if there exists some
z
Z
n
which
∈
r
2
g
a
1
g
a
2
Z
n
and
a
1
,
cannot be written
z
=
mod
n
for
r
∈
a
2
∈
Z
2
.
2
χ
over
Z
n
, i.e.
Using this process the key holders own some nontrivial character
some group homomorphism between
Z
n
and
{−
,
+
}
χ
=−
1
1
such that
(
g
1
)
1 and
1, and he proves that all
Z
n
can be written
r
2
g
a
1
g
a
2
χ
(
g
1
)
=+
mod
n
for
r
∈
Z
n
and
2
a
1
,
a
2
∈
Z
2
.
1
We actually describe a particular case based on characters of order 2. See Refs. [135, 136].
Search WWH ::
Custom Search