Cryptographic Protocols - A Classical Introduction to Cryptography: Applications for Communications Security - page 284

Prover Verifier

Z n
pick a 1 ,...,

pick r ∈

a s ∈ Z 2

u
←−−−−−−−−−−−−−− r 2 g a 1

1

g a s
s

u = ···

v
−−−−−−−−−−−−−−→ v = χ ( u )

a s
←−−−−−−−−−−−−−−
v
−−−−−−−−−−−−−−→

r , a 1 ,...,

check u

check v

e a 1
1

e a s
s

v = ···

Figure 11.7. MOVA proof of interpolation protocol.

Proof of interpolation. The MOVA scheme requires to prove that given some subset

={

( g 1 ,

,...,

( g s ,

}

A e 1 ) e s )

of Z n ×{− form Z n

1 , + 1 } , there exists a character χ , i.e. a group homomorphism χ

to {− 1 , + 1 } such that χ ( g i ) = e i for i = 1 ,..., s . In all cases here this character is the

Legendre symbol p ), which is computable from the secret key only. We call

this a proof of interpolation for A . As depicted in Fig. 11.7, this consists of k iterations
of the following protocol.

χ = ( · /

r 2 g a 1
1

Z n , a 1 ,..., g a s

s

1. The verifier picks r ∈ a s ∈ Z 2 , computes u = ··· mod n

and sends it to the prover.
2. The prover computes

v = χ ( u ) and sends a commitment of v to the verifier.

3. The verifier discloses r , a 1 ,..., a s .

r 2 g a 1
1

g a s s mod n and opens the commitment.
(These steps are used in order to make sure that the verifier is honest.)
5. The verifier verifies the commitment and checks that

4. The prover verifies that u = ···

e a 1
1

v = ···

e a s .

We can prove that this protocol is complete, sound, and zero-knowledge. More precisely,
it cannot succeed with probability greater than 2 − k if there exists no character χ for

which χ ( g i ) = e i for i = 1 ,..., s .

Signature algorithm. The signature algorithm is quite simple. Given a message X ,we
generate x 1 ,..., Z n by using a generator fed with the hashed value of X . We then x t ∈

compute y i = y t ). (Note that it

consists of t bits.) We can show that someone who can distinguish a valid signature
from an invalid one can solve the quadratic residuosity problem in Z n , i.e. can distin-
guish a quadratic residue from a nonquadratic residue with a Jacobi symbol equal to
+

( x i / p ) for i = 1 ,..., t . The signature is σ = ( y 1 ,...,

1.

Confirmation algorithm. To confirm a signature σ = ( y 1 ,..., y t ) for a message X ,we

recalculate x 1 ,..., x t and then run the proof of interpolation with

A ={ ( g 1 , − 1) , ( g 2 , + 1) , ( x 1 , y 1 ) ,..., ( x t , y t ) } .