Could this be a valid variation of the Schnorr protocol?

Question

The Schnorr protocol is a 3-steps proof of knowledge of a discrete logarithm, whose interactive version works as follows.

Let $p$ and $q$ be two public primes, such that $q \mid (p-1)$, and let $G$ be a cyclic subgroup of $\mathbb Z^\times_p$ of order $q$ (i.e. a Schnorr group) with generator $g$. The prover $P$ wants to prove knowledge of $x=\log_g(y)$ to a verifier $V$, by the following steps:

1) $P$ commits himself to randomness $r \in \mathbb Z_q$, and sends $t=g^r \bmod p$ to $V$.

2) $V$ replies to $P$ with a challenge $c$ chosen at random from $\mathbb Z_q$.

3) After receiving $c$, the prover $P$ sends the response $s=r+cx \bmod q$ to $V$.

4) Finally, the verifier accepts if $g^s \equiv t y^c \bmod p$.

My question is:

What is the exact reason why the response $s$ of the prover in step 3 is that one, and not another one? For example, couldn't it also work if the response were, for example, $s=r+c+x$ or $s=rc+x$, and then the verifier had to check if $g^s \equiv t g^c y$ or $g^s \equiv t^c y$, respectively?

Answer 1

As noted by Perseids in a comment to this answer, the formula $s = r + c + x$ would allow an adversary (who has completed the protocol once in the role as verifier with $P$ and already got one valid triplet $t_1,c_1,s_1$) to compute responses to any arbitrary challenge, simply using the formulas $t_2 = t_1$, $s_2 = s1 + c_2 - c_1$.

Your other alternative $s = rc + x$ would however work, given a few additional restrictions:

1. $c \neq 0$. Since we are working in a prime order subgroup, this implies the existence of a multiplicative inverse $c^{-1}$ modulo the group order $q$. This is not a significant restriction to the original protocol, since $c = 0$ would entail the response $s = r + 0x = r$, which would not prove possession of $x$ and hence be pointless. With the alternative formula, however, $c = 0$ would entail $s = x + 0r = x$, which would leak the private key.
2. $t$ and $y$ belong to the same prime order subgroup as $g$. This is implicit from the protocol specification, but it might be stressed that $V$ is able to verify that this is indeed the case, by checking that $p, q$ are prime numbers such that $q|p-1$, and that $g^q = t^q = y^q = 1 \bmod p$.
3. We define $r = log_g(t) \bmod p$ and $x = log_g(y) \bmod p$. The attacker is not required to know the exact value $r$ and $x$ for the following math to work out.

We also need a security claim, in order to define exactly what it is we assume about the original protocol and want to prove with respect to the alternative one. The most appropriate claim would be that an adversary $A$, who does not know $x$ and does not have real-time oracle access to the authentic prover $P$, has only a negligible chance of successfully playing out the protocol with a honest verifier $V$.

It might be noted that an adversary $A$ with real-time oracle access to the authentic prover $P$, would be trivially able to successfully play out the protocol with any honest verifier $V$. Hence, in order not to prove something we already know, we have to assume this is not the case.

Suppose an adversary $A$ is able to impersonate $P$ and provide false proofs of $x$ using the alternative formula. Since $sc^{-1} = (rc + x)c^{-1} = r + xc^{-1}$, such an adversary would also be able to provide false proofs of $x$ using the original formula. Since the latter is impossible, so is the former.

A proof might be outlined as follows:

Let $A$ be an adversary who is able to successfully play out the protocol based on the alternative formula $s = rc + x$, given the restrictions listed above. Let $V$ be a (honest) verifier who expects the $s$ value to comply with the original formula, subject to the same restrictions (in particular that $c \neq 0$). Let $A'$ denote $A$ taking the role of a prover of the $x$ using the original formula.

Now, all we need to do is to add a few steps where $A'$ plays out the protocol steps with $A$ (i.e. himself):

1. $V$ asks $A'$ to commit
2. $A'$ asks $A$ to commit and gets a value $t$, such that $t^q = 1 \bmod p$, which $A'$ forwards to $V$.
3. $V$ replies with a challenge $c$ chosen at random from $\mathbb Z_q^*$
4. After receiving $c$, $A'$ sends $c^{-1}$ to $A$, gets a value $s$ and sends the response $s' = cs$ to $V$.
5. Finally, $V$ accepts if $g^{s'} = ty^c \bmod p$.

If $V$ doesn't accept $s'$ as a proof of $x$ given challenge $c$ in step 4, neither would a verifier who expected a response using the alternative formula accept the response $s$ to the challenge $c^{-1}$ as a proof of $x$.

So what does this prove with respect to the security claim? Firstly, assume that the original protocol meets the security claim, but the alternative protocol doesn't. If the alternative protocol doesn't meet the security claim, it means that the adversary $A$ has a non-negligible probability of successfully playing out the above protocol, but since we have just proved that this would mean that $A'$ also would have the same probability of successfully playing out the protocol, this would contradict our original assumption (that the original protocol meets the security claim), and hence it is not possible that the alternative protocol doesn't.

Answer 2

You have to look at the response from the perspective of the verifier. This specific construction allows him/her to verify the $P$'s knowledge of $x$:

If $P$ could answer two different request $c_1,c_2$ in step 2) then we would have $g^{s_1}=ty^{c_1}$ and $g^{s_2}=ty^{c_2}$. Dividing one equation by the other we get $g^{s_1-s_2}=y^{c_1-c_2}$. Let $(c_1-c_2)^{-1}$ be the inverse of $c_1-c_2$ modulo $q$ (which exist because $c_1-c_2\neq 0$ as they are distinct) then $y=g^{(s_1-s_2)*(c_1-c_2)^{-1}}$. It follows $x=(s_1-s_2)\cdot(c_1-c_2)^{-1}$ is the discrete logarithm of $y$. Thus if $P$ can answer two request, he/she will know $x$. If $P$ could only answer one of them the probability of $V$ choosing this exact one are very small (depending on the size of $q$).

I haven't tried hard but I believe the alternatives you mention cannot prove the knowledge of $x$.