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

participant can learn what card was distributed to another participant, one should make
sure that no card is distributed twice, and one should make sure that the distribution of
card shuffling is as fair as possible. Some protocols can be used in order to share the
card deck, to shuffle, to distribute, etc.

Multiparty computation. A more general problem is to make multiparty computation:
each participant has a secret value, and we want to compute a function in terms of
all secret values, without disclosing the values. In the electronic vote, we want to
count the number of occurrences of several values, and hopefully get the majority. We
can invent other odd problems: compute the maximum fortune of jealous millionaires
who do not want to disclose their fortune, but only to know how much owns the
richest; compute perfect matchings out of private requirements in blind date ceremonies,
etc.

Broadcast encryption. In pay television, we need to broadcast a signal which is en-
crypted, and to distribute different keys to the participants in order for them to be able
to decrypt.

11.5 Exercises

Exercise 11.1. An idiot dishonest verifier thinks that giving the challenge e = 0 in the

basic Fiat-Shamir protocol is useless since the answer y = r does not depend on the

secret key. Therefore he decides to always ask e = 1 .

Show how a malicious prover can impersonate anyone to this verifier.

Exercise 11.2. Let us define the following identification scheme. A user U has a secret
key which consists of two prime numbers p and q such that p ≡ q ≡ 3 (mod 4) .We

have n pq which is public and associated to the identity of U by a certificate. In

order to prove the knowledge of the secret key, we can challenge U with a random x.
U then computes one square root y of x modulo n, and we can check that it is indeed
a square root by raising it to the square.

=

Why is it insecure?

Exercise 11.3. Explain how to transform the Fiat-Shamir protocol into a signature
scheme.

Exercise 11.4 (Guillou-Quisquater zero-knowledge protocol). We consider the fol-
lowing scheme.

Setup of public parameters: take n = pq with p , q primes and an exponent v ∈

Z ϕ ( n ) .
Setup of the keys: for a given prover, define his identity string J , and compute B

=

J 1 /v

1 / mod n. The public key is K p = ( J ,v, n ) . The secret key is K s = B.