Zero-Knowledge Proofs

Authentication and deniability seem fundamentally opposed. Authentication means becoming convinced of someone's identity. Deniability, in the context of authentication, means having no proof of interacting with someone. How can you become convinced of someone's identity without also having proof of their identity?

Amazingly, it is possible to reconcile authentication with deniability, to authenticate without a trace. I can prove my identity to you in such a way that leaves you with no evidence you could use to convince someone else. This concept of leaving no trace is called zero knowledge, and it is not limited only to authentication. A zero-knowledge proof lets me convince you that something is true—like the fact that I know a private key corresponding to some public key—while leaving no useful information behind.

19.1. The Schnorr identification protocol

Cryptographic authentication happens with respect to a public key. Let's consider key pairs where an integer $a$ is the private key and $A = g^a$ is the corresponding public key, where $g$ is the generator of a suitable cyclic group. “Authenticating the owner of public key $A$” means becoming convinced that you are talking to someone who knows the discrete logarithm $a$ of $A$. The following interactive protocol, named after its creator Claus Schnorr, is a method for doing just that:

When the protocol is executed as shown above, the verifier will always accept, because

It's more interesting to consider what happens when one of the participants is adversarial.

Lying prover: The verifier wants to be sure that only someone who knows the private key $a$ can succeed in the protocol. The analysis of Schnorr's protocol uses a clever way to characterize whether a cheating prover “knows” a certain value.

What does this have to do with determining whether the prover knows $a$, you might be asking? Consider the moment in Schnorr's protocol immediately after the prover has sent their first message $Y$. The verifier is about to sample $c \gets \Z_\nmod$. For any possible $c$, we can imagine whether the prover would be able to produce the correct response, causing the verifier to accept. There are two cases to consider:

• The prover could respond correctly to two different values of $c$. If the prover is able to do this, then from claim 19.1.3 the prover surely has enough information to compute $a$. Thus, it is safe to say that the prover knows $a$, and it is fine that the verifier accepts.

• Otherwise, the prover can respond correctly to at most one value of $c$. It doesn't matter what this value is, just that there is at most one such value. Since the verifier samples $c$ uniformly in $\Z_\nmod$, the chance of choosing this special value is $1/\nmod$, which is negligible ($\nmod$ is exponentially large, as the order of a cryptographically strong cyclic group). Barring this negligibly likely bad event, the verifier must choose a $c$ for which the prover cannot produce the correct response, so the verifier will reject.

Nosy verifier: What does the verifier learn about the prover in this protocol? This answer is (arguably) best understood with a story:

Why does the King think that an arrow in the middle of a target is convincing evidence of Robin Hood's skill, but the Sheriff does not? The Sheriff is correct that it requires no skill to produce an arrow in the center of a target. On the other hand, it requires great skill to produce an arrow in the center of a target if the target is painted before the arrow is fired! The King saw that the target was painted before Robin Hood fired his arrow, but the Sheriff did not.

In the world of zero-knowledge, the artifacts of the interaction are not convincing in themselves; what is convincing is the manner in which those artifacts were produced. We can say something similar about Schnorr's protocol:

In the Schnorr protocol, $Y$ and $c$ are like the target, and $r$ is like the arrow. If $Y$ is chosen first and $c$ second, then only someone who knows Alice's private key can produce the correct $r$ (except with negligibly small probability). Like King Richard at his archery competition, a verifier who participates in Schnorr's protocol becomes convinced that the prover knows $a$. However, after the interaction is finished, its transcript is meaningless. Anyone can create an accepting transcript by choosing $r$ and $c$ first, and then solving for $Y$; this is like painting a target where the arrow struck. And since these “fake” transcripts can be generated without knowing the secret value $a$, the “real” Schnorr transcripts, generated using $a$, cannot leak any information about $a$.

Let's see how to generate Schnorr protocol transcripts without knowing the private key:

An authentication session using Schnorr's protocol leaves behind no valuable information. Everything the verifier sees during the protocol, he could have generated himself using the process in $\lib{schnorr-fake}$, even without knowing the private key $a$.

Compare this aspect of Schnorr's protocol with signature-based authentication. Only someone who knows the signing key can generate a valid signature. If Alice authenticates by sending Bob a signature, she gives him something that he could not have computed himself. He could have obtained this signature only by interacting with Alice.

19.2. Sigma protocols

Schnorr's protocol is an example of a special kind of interactive proof called a sigma protocol.

An interactive proof is simply an interactive protocol in which the prover tries to convince the verifier that some condition is true.

In Schnorr's protocol, there is a public value $A$, known to both the prover and verifier; the prover wants to convince the verifier that it knows a private value $a$ that satisfies $g^a = A$. In a generic sigma protocol, there is a public value $X$ called an instance; the prover wants to convince the verifier that it knows a private witness $W$ such that $X$ and $W$ together satisfy some condition (or predicate).

In the language of mathematical proofs, completeness means that every true thing should have a valid proof, and soundness means that only true things have valid proofs. Interactive proofs like sigma protocols must be both complete and sound in order to be useful:

We define soundness for sigma protocols in the style of Schnorr's protocol. Namely, if there are two accepting transcripts that share a common prefix, then we must be able to extract a witness $W$ that satisfies $P(X,W)$. This way of defining soundness is highly specialized to the strict structure of a sigma protocol, and is not meaningful for all flavors of interactive proofs that cryptographers study. Thus, it is traditionally called special soundness.

We call an interactive proof zero-knowledge if, informally, the interaction reveals nothing about the witness to the verifier. This property can be formalized by saying that there is a way to generate convincing protocol transcripts without using the witness at all. By definition, these “fake” transcripts contain no information about the witness. So if they are indistinguishable from real transcripts, then real transcripts must not leak information about the witness.

The zero-knowledge security definition for sigma protocols considers only transcripts that are generated with a verifier who follows the protocol. Thus, the definition can be interpreted as: Verifiers who follow the protocol learn nothing about the witness. Other forms of zero-knowledge proofs, which we do not study in this book, also consider the more challenging case where a verifier cheats in (deviates from) the protocol.

19.3. More examples of sigma protocols

This section introduces several more sigma protocols for proving more complex conditions.

19.3.1. Proof of discrete log equality

Let $(g_1, g_2, A_1, A_2)$ be cyclic group elements, and suppose the prover would like to convince the verifier that it knows a value $a$ such that $g_1^a = A_1$ and $g_2^a = A_2$—in other words, that two discrete logarithms are equal.

Running Schnorr's identification protocol twice, first on $(g_1,A_1)$ and then on $(g_2,A_2)$, would establish that the prover knows both discrete logs, but it would do nothing to establish that those discrete logs are equal. The idea instead is to run these two instances of Schnorr's protocol, but restrict the prover to use the same challenge and response in both instances. It turns out that this idea is enough to ensure that the two discrete logs must be equal.

19.3.2. Proving ANDs and ORs

In this section we show how to construct sigma protocols for more complicated conditions, involving ands and ors. For example:

• Alice wants to prove that she knows the discrete log of either $A_1$ or $A_2$. Imagine that these are public keys of two people who are authorized to use a system, and Alice wants to authenticate without revealing who she is.

• Given a public ciphertext $\ctxt$, Alice wants to prove that $\Dec(\sk,\ctxt) \in \{ \bit{yes}, \bit{no} \}$. In other words, either the ciphertext decrypts to $\bit{yes}$, or it decrypts to $\bit{no}$. The ciphertext may represent a vote in an election, and Alice wants to prove that she cast an unambiguous vote, without revealing it.

• Alice wants to prove that $(g_1,g_2,g_3, A_1,A_2,A_3)$ satisfy $(g_i)^a = A_i$. In other words, the discrete logs of $A_1$ and $A_2$ are equal, and the discrete logs of $A_2$ and $A_3$ are equal.

Proving an OR: We start with the case of an or of two conditions. Suppose we have a sigma protocol $\Sigma_0$ for condition $P_0$ and a sigma protocol $\Sigma_1$ for condition $P_1$. A prover wants to prove knowledge of $W$ such that [$P_0(X,W)$ or $P_1(X,W)$], or in other words, prove knowledge of $b \in \{0,1\}$ and $W$ such that $P_b(X,W)$.

To understand the clever idea behind this sigma protocol, we return to the metaphor involving arrows and targets. Robin Hood has two bows and wants to convince the King that he can fire one of them accurately. The King could draw two targets and ask Robin to fire an arrow from each bow and hit the two targets. But Robin might not be able to hit both targets, because one of his bows might be erratic. Additionally, the final positions of the arrows might reveal to the King which bow is the good one.

Instead, the King should draw only one target, and ask Robin to fire an arrow from each bow, so that the target is precisely between the two arrows. As long as Robin can fire just one bow accurately, he can succeed. He should first fire the erratic bow; its arrow will land unpredictably, likely nowhere near the target. But then Robin knows exactly where he should fire the second arrow, now from the accurate bow, so that the target is precisely between the arrows.

Okay, this physical metaphor is convoluted and strained, but it captures the spirit of the sigma protocol, which works as follows:

• The prover sends the first messages ($Y_0, Y_1$) in parallel instances of $\Sigma_0$ and $\Sigma_1$.

• The verifier uniformly samples $C$ and challenges the prover to complete two accepting transcripts $(Y_0, C_0, R_0)$ and $(Y_1, C_1, R_1)$, such that $C_0 + C_1 = C$. Here, $C_0$ and $C_1$ are like the two arrows, which can be fired anywhere but whose average (or sum, in this case) must hit a particular target $C$.

• Suppose the prover knows a witness for $\Sigma_0$ but not $\Sigma_1$. Then it should have generated $Y_1$ by simulating a transcript $(Y_1, C_1, R_1)$. Now the prover is bound to use this $C_1$ and has no control over $C_0 = C - C_1$, so it must use its witness to construct the correct response $R_0$ in the $\Sigma_0$ instance.

The formal details are given below. The verifier thinks of the two sigma protocol instances using subscripts 0 and 1, but the prover, who has a witness for $P_b$, thinks of them using subscripts $b$ and $1-b$.

Proving an AND: Now suppose we have sigma protocols $\Sigma_0$ and $\Sigma_1$, for conditions $P_0$ and $P_1$, respectively, and the prover would like to convince the verifier that it knows $W_0$ and $W_1$ such that $P_0(X,W_0)$ and $P_1(X,W_1)$. A natural idea is to simply run an instance of each of $\Sigma_0$ and $\Sigma_1$, in parallel. It is true that if the verifier accepts both proofs, then he can be convinced that the prover knows a witness to both conditions. However, the resulting protocol does not technically satisfy the formal security properties of a sigma protocol; exercise 19.12 explores this issue further.

To combine $\Sigma_0$ and $\Sigma_1$ into a single protocol that satisfies all of the usual sigma protocol security definitions, we must make one small modification:

You are asked to prove the following in an exercise:

19.4. Noninteractive proofs and signatures

19.4.1. The Fiat-Shamir transformation

Interaction in a sigma protocol is crucial: It is how the protocol enforces that the verifier's challenge $C$ is chosen after the prover has committed to a value of $Y$. Without this strict order of operations, a sigma protocol proves nothing. Indeed, we have seen that it is easy to generate an accepting transcript in a different order; this is an important feature of a sigma protocol.

But interaction is not the only way to enforce that $C$ is chosen after $Y$. Suppose we compute $C := \ro(X,Y)$, where $\ro$ is a random oracle. Then there is indeed no way to predict $C$ before calling $\ro(X,Y)$. Furthermore, $C$ will be distributed uniformly, just as in the sigma protocol.

The idea of replacing the verifier with a random oracle is called the Fiat-Shamir method. It converts an interactive sigma protocol into a noninteractive proof. The prover can generate the entire transcript locally:

The intuitive idea is that only someone who knows a valid witness $W$ can generate a proof that causes $\textsf{Verify}$ to output $\mytrue$, and yet the proof $(Y,R)$ reveals nothing about the witness $W$. We will not formally define security properties of abstract noninteractive proof systems, but rather state some useful properties of the Fiat-Shamir construction. In particular, we reason about soundness in a similar way to sigma protocols. If a prover is able to produce valid proofs, then we can efficiently extract a valid witness from that prover.

Lemma 19.4.2 is often called the forking lemma, because of how $\A'$ “forks” the execution of $\A$ into many different branches.

Deniability: Be careful! The Fiat-Shamir technique destroys a sigma protocol's deniability property! Plain (interactive) sigma protocol transcripts are deniable, because anyone can easily generate an accepting transcript. In the real protocol execution, $Y$ is chosen first, then $C$, and then $R$; but anyone can generate an accepting transcript by choosing $C$ and $R$ first and then solving for $Y$.

In a Fiat-Shamir proof, we have $C = \ro(X,Y)$. Anyone with access to the random oracle—which is to say, anyone at all, since a random oracle is public—can conclude that $Y$ must have been chosen before $C$. And only someone who knows a valid witness can complete an accepting transcript when $Y$ is chosen before $C$.

19.4.2. Schnorr signatures

Imagine applying the Fiat-Shamir method to Schnorr's protocol, in which the prover convinces the verifier that it knows the discrete log $a$ for a public value $A = g^a$:

As we discussed above, such Fiat-Shamir proofs are not deniable. In some situations the lack of deniability is a bad thing, but on the other hand we have achieved almost exactly the goal of a digital signature: Only someone who knows the witness $a$ can generate a valid Fiat-Shamir proof, but anyone can verify it.

However, we have not yet constructed a digital signature scheme, because each signature needs to be associated with a particular message. We can incorporate a message $\ptxt$ by computing the sigma protocol's challenge, not as $c := \ro(A,Y)$, but as $c := \ro(A,Y, \hl{\ptxt})$. The result of this change is the Schnorr signature scheme:

You can interpret Schnorr signatures in the following way: A valid signature is essentially an accepting sigma protocol transcript $(A,Y,c,r)$. The fact that $c = \ro(\hl{A,Y},\ptxt)$, implies that $Y$ was chosen before $c$, and thus only someone who knows the private key $a$ could have generated the transcript. Furthermore, since $\ptxt$ is included in $\ro(A,Y,\hl{\ptxt})$, the person who knows $a$ clearly generated the transcript with $\ptxt$ specifically in mind! The sigma protocol transcript is bound to $\ptxt$.

The proof of this claim is somewhat technical, and beyond the scope of this book, but uses several important ideas introduced above:

• We introduce a hybrid library where $\sigsign$ generates signatures in a different way: It simulates an accepting transcript $(Y,C,r)$, then programs the random oracle so that $\ro(A,Y,M) = C$. Thus, $(Y,r)$ is a valid signature of $M$, but it was generated without knowledge of the signing key $a$.

• Next, we use the forking lemma (lemma 19.4.2) to argue that if an adversary can successfully produce signature forgeries, then there would be a way to efficiently extract the Schnorr witness $a$. But such an algorithm would contradict the discrete logarithm assumption. So we must conclude that it is hard for an adversary to produce a forgery.

Schnorr signatures in the wild: Schnorr signatures are elegant and have a security analysis that is easy to understand in light of Schnorr's identification protocol. Schnorr signatures can be implemented using a cyclic group based on elliptic curves, leading to signatures that can be as short as 512 bits. In comparison, RSA signatures are generally 2048–4096 bits in practice, because that is the range of safe sizes for an RSA modulus.

Despite its unmistakable advantages, the Schnorr signature scheme is not used in practice as much as it deserves to be. The main reason is that for a long time the construction was subject to a patent. Governmental organizations that standardize cryptographic algorithms, like NIST, are reluctant to standardize algorithms that are encumbered by patents. As a result, the standardized options for elliptic-curve-based signatures are algorithms like ECDSA and EdDSA, two algorithms that were clearly inspired by Schnorr signatures, but that lack its simplicity and charm since an important design constraint was avoiding the reach of Schnorr's patent. Unfortunately, it is exactly these differences from Schnorr signatures that make ECDSA and EdDSA difficult for provable security. Neither has a proof that bases their security on such a simple problem as discrete logarithm. Although Schnorr's patent expired in 2010, by that time ECDSA and EdDSA had become entrenched as standards.

Exercises

1. Definition 19.2.5 asks for a simulator that generates the entire transcript $(Y,C,R)$ together. There are some situations where we require $C$ to be chosen first, and the rest of the transcript $(Y,R)$ computed as a function of $(X,C)$. Let's say that a sigma protocol has special HVZK if there is a simulator $\SimTrans$ such that the following libraries are indistinguishable:

   $\lib{shvzk-real}$

   $\hvzktrans(X,W)$:

   $(Y,\sigma) := \Commit(X,W)$

   $C \gets \C$

   $R := \Respond(\sigma,C)$

   return $(X,Y,C,R)$

   $\indist$

   $\lib{shvzk-fake}$

   $\hvzktrans(X,W)$:

   $\hl{C \gets \C}$

   $(Y,R) := \SimTrans(X, \hl{C})$

   return $(X,Y,C,R)$

   In this exercise, you will show how to convert a standard sigma protocol into one with special HVZK.

   Suppose $\Sigma$ is a sigma protocol and $\Sigma.\C$ has an addition operation. Define the new protocol $\Sigma^*$ as follows:

   $\Sigma^*.\C = \Sigma.\C$

   $\Sigma^*.\Commit(X,W)$:

   $(Y, \sigma) := \Sigma.\Commit(X,W)$

   $\Delta \gets \Sigma.\C$

   return $\bigl( (Y,\Delta), (\sigma,\Delta) \bigr)$

   $\Sigma^*.\Respond( \sigma^*, C )$:

   $(\sigma,\Delta) := \sigma^*$

   return $\Sigma.\Respond(\sigma, \hl{C+\Delta})$

   $\Sigma^*.\Check(X, Y^*, C, R)$:

   $(Y,\Delta) := Y^*$

   return $\Sigma.\Check(X,Y,\hl{C+\Delta},R)$

   1. Prove that $\Sigma^*$ has special soundness, if $\Sigma$ does.

   2. Prove that $\Sigma^*$ has special HVZK, if $\Sigma$ has (plain) HVZK. Clearly describe the simulator for $\Sigma^*$, in terms of the simulator for $\Sigma$.

2. Let $(g_1,g_2,A_1,A_2)$ be cyclic group elements. Describe a sigma protocol that lets a prover convince a verifier that it knows $a$ such that $g_1^a = A_1$ and $\hl{g_2^{2a}} = A_2$. Prove that your protocol satisfies honest-verifier zero-knowledge and special soundness.

3. Suppose $(U,V)$ are two public values. Describe a sigma protocol that lets a prover convince a verifier that it knows $a$ such that $(U,V) = (g^a, g^{a^2})$. Prove that your protocol satisfies honest-verifier zero-knowledge and special soundness. Assume that the group generator $g$ is public.

4. h Describe a sigma protocol for proving that a public instance $(A,B,C)$ has the form $(g^a, g^b, g^{ab})$, and prove that your protocol satisfies honest-verifier zero-knowledge and special soundness. Assume that $g$ is public, and that the prover knows $a$ and $b$.

   Rename $g$ to $g_1$ and $B$ to $g_2$.

5. h Let $(C_1,C_2)$ be an El Gamal ciphertext encrypted under key pair $(\sk,\pk)$, and let $\ptxt$ be a publicly known value. Propose a sigma protocol whereby a prover can convince a verifier that $\Dec(\sk, (C_1,C_2)) = \ptxt$.

   1. Describe such a protocol that is suitable for a prover who knows $\sk$, but not the randomness used to generate the ciphertext.

   2. Describe such a protocol that is suitable for a prover who knows the randomness used to generate the ciphertext, but does not know $\sk$.

   In both cases, prove that the protocol satisfies special soundness and honest-verifier zero knowledge.

   Manipulate the El Gamal decryption equation into an expression that can be proven with a single instance of the Schnorr proof. For part (b), prove knowledge of $r$ that satisfies $(C_1,C_2) = (g^r, \ptxt \cdot \pk^r)$.

6. h Let $(C_1,C_2)$ and $(C_3,C_4)$ be El Gamal ciphertexts, encrypted under a common public key $\pk$. Describe a sigma protocol whereby a prover can convince a verifier that:

   $\Dec\bigl(\sk, (C_1,C_2)\bigr) = \Dec\bigl(\sk, (C_3,C_4) \bigr).$

   The protocol should be suitable for a prover who knows the randomness used to generate the ciphertexts but not $\sk$. Prove that the protocol satisfies special soundness and honest-verifier zero knowledge.

   $\begin{aligned} \text{if } (C_1,C_2) &= (g^{r_1}, M \cdot \pk^{r_1}) \\ \text{and } (C_3,C_4) &= (g^{r_2}, M \cdot \pk^{r_2}) \\ \text{then } ( C_1 (C_3)^{-1}, C_2 (C_4)^{-1} ) &= ( g^{r_1 - r_2}, \pk^{r_1 - r_2} )\end{aligned}$

7. Let $X, g, h$ be public group elements, in a cyclic group of prime order $\nmod$. Describe a sigma protocol whereby a prover can convince a verifier that it knows exponents $a,b$ such that $X = g^a h^b$. Prove that the protocol satisfies special soundness and honest-verifier zero knowledge.

8. h$\star$ Let $(g_1,g_2,A_1,A_2)$ be a public instance, and suppose Alice knows a value $a$ such that $A_1 = g_1^a$ but $A_2 \hl{\ne} g_2^a$. She would like to prove in zero knowledge that $A_1$ and $A_2$ have different discrete logs. In other words, nothing should be revealed about the relationship between those discrete logs besides the fact that they are different. Describe a sigma protocol for this problem and prove that it satisfies special soundness and honest-verifier zero knowledge.

   $A_1^r g_1^{-ar} = 1$ and $A_2^r g_2^{-ar} \ne 1$, for any nonzero $r$. Additionally, when $r$ is uniform, $A_2^r g_2^{-ar}$ is distributed uniformly. Have the prover send $X = A_2^r g_2^{-ar}$ to the verifier and then prove knowledge of exponents $s, t$ such that $A_1 ^s g_1^t = 1$ and $A_2^s g_2^t = X$. The verifier should also check that $X \ne 1$.

9. Complete the proof of claim 19.3.6: Prove that the simulated transcripts are indistinguishable from real ones.

10. Suppose the verifier forgets to check the condition $C_0 + C_1 == C$ in construction 19.3.4. Show how the prover can prove a false statement.

11. The prover in construction 19.3.4 convinces the verifier that one of two conditions is true.

    1. Suppose there are three conditions. Describe a sigma protocol that allows the prover to prove that at least one of the conditions is true (without revealing which one). Prove that your protocol is secure.

    2. Describe a sigma protocol that allows the prover to prove that at least two of the three conditions are true (without revealing which ones). Prove that your protocol is secure.

    3. $\star$ Generalize this construction to $t$ out of $n$ conditions and prove that your construction is secure.

12. Let $\Sigma_0$ and $\Sigma_1$ be sigma protocols for conditions $P_0$ and $P_1$, respectively. Consider the naïve method of composing them in parallel to obtain a sigma protocol to prove $P_0(X,W_0)$ and $P_1(X,W_1)$:

    

    Version 1 of the protocol is as described above; version 2 is the same except both instances use the same challenge (i.e., $C_0 = C_1$). One of these versions has special soundness but not necessarily HVZK; the other has HVZK but not necessarily special soundness. Which is which, and why?

13. Prove claim 19.3.8: Construction 19.3.7 has special soundness and is HVZK.

14. Describe a sigma protocol for the following problem, and prove that it satisfies the usual properties: Alice has generated an El Gamal encryption under a public key $\pk$; she wants to convince a verifier that the ciphertext decrypts to either $g^0$ or $g^1$. Assume that Alice knows the randomness used to encrypt the ciphertexts but not the El Gamal private key.

15. h Suppose $\nmod$ is an RSA modulus, and $e$ is a prime exponent such that $\gcd(e,\nmod)=1$. Consider the following sigma protocol, in which the prover wants to convince the verifier that it knows an $e$-th root of a public value $X$.

    

    Note that neither the prover nor verifier need to know the factorization of $\nmod$. Prove that the protocol satisfies special soundness and honest-verifier zero knowledge.

    Given two accepting transcripts $(X,Y,c,R)$ and $(X,Y,c',R')$ with $c\ne c'$, use Bezout's theorem to compute integers $s$ and $t$ such that $s e + t (c-c') = 1$, and take $W \equiv_\nmod X^s (R/R')^t$.

16. In the Schnorr signature scheme, the signer samples a value $y$ uniformly. Show that if an adversary obtains signatures of two different messages signed using the same $y$, they can compute the private signing key.

17. Digital Signature Algorithm (DSA) is a standard signature scheme defined using modular arithmetic. In the following, $\pmod$ and $\qmod$ are distinct primes and $g$ is a fixed integer. All three values are publicly known parameters. $H$ is a hash function with output in $\Z_\qmod$.

    $\KeyGen(\,)$:

    $\sk \gets \Z_\qmod$

    $\pk := g^{\sk} \pct \pmod$

    return $(\sk,\pk)$

    $\Sign(\sk,\ptxt)$:

    $k \gets \Z_\qmod$

    $R := (g^k \pct \pmod) \pct \qmod$

    $S := \bigl(k^{-1} ( H(\ptxt) + \sk \cdot R ) \bigr) \pct \qmod$

    return $(R,S)$

    The verification algorithm is not relevant for this exercise.

    1. Suppose an adversary observes a signature $(R,S)$ on message $\ptxt$ and another signature $(R',S')$ on message $\ptxt' \ne \ptxt$, where the same value $k$ was chosen for both signatures. Show how the adversary can efficiently calculate $k$.

    2. Given the same circumstances as part (a), show how the adversary can efficiently calculate $\sk$.

18. The Schnorr signing algorithm computes $C := \ro(A,Y,M)$.

    1. Show that the scheme is no longer a secure signature scheme if $C$ is computed as $\ro(A,M)$.

    2. Show that the scheme is no longer a secure signature scheme if $C$ is computed as $\ro(A,Y)$.

    3. Suppose we restrict the scheme to sign messages from the cyclic group $\G$, and compute $C$ as $\ro(A \cdot Y \cdot M)$. Multiplication here refers to the group operation in $\G$. Show that the resulting scheme is not a secure signature scheme.