Attack on Identification Scheme (from Katz-Lindell Textbook 3rd Ed., p. 483)

Question

I have a question about the attack on the identification scheme explained in the Katz-Lindell textbook (3rd Ed, p. 483) before the explanation on DSA/ECDSA. Suppose $\mathbb{G}$ is a cyclic group of prime order $q$ with generator $g$. We consider an identification scheme with the prover's private key is $x$ and the public key is $(\mathbb{G},q,g,y)$ where $y:= g^x$:

1. The prover chooses a uniform $k \in \mathbb{Z}_q^*$ and sends $I:= g^k$ to the verifier.
2. The verifier chooses a uniform $(\alpha,r) \in \mathbb{Z}_q\times \mathbb{Z}_q$ as the challenge.
3. Upon receiving $(\alpha,r)$, the prover sends $s:= [k^{-1} \cdot (\alpha + xr)] \bmod q $ as the response.
4. The verifier accepts if $s \neq 0$ and $g^{\alpha s^{-1}} \cdot y^{rs^{-1}} = I$.

In the book, we consider the attack in which the adversary outputs an initial message $I$ for which it can give correct responses $s_1,s_2 \in \mathbb{Z}_q^*$ to two distinct challenges $(\alpha,r_1),(\alpha,r_2) \in \mathbb{Z}_q \times \mathbb{Z}_q$. Here, we have: $$ g^{\alpha s_1^{-1}} \cdot y^{r_1 s_1^{-1}} = g^{\alpha s_2^{-1}} \cdot y^{r_2 s_2^{-1}} = I.$$

From this condition, we obtain $g^{\alpha(s_1^{-1}-s_2^{-1})} = y^{r_2s_2^{-1} -r_1s_1^{-1}}$, thus we have $g^{\alpha(s_1^{-1}-s_2^{-1})} = g^{x(r_2s_2^{-1} -r_1s_1^{-1})}$. We obtain $x = \alpha(s_1^{-1}-s_2^{-1})(r_2s_2^{-1} -r_1s_1^{-1})^{-1}$, where the operations are performed in $\mathbb{Z}_q$.

The book also says that we have a similar situation if the attacker gives correct responses to two distinct challenges $(\alpha_1,r),(\alpha_2,r) \in \mathbb{Z}_q \times \mathbb{Z}_q$. Here, we have: $$g^{\alpha_1 s_1^{-1}} \cdot y^{r s_1^{-1}} = g^{\alpha_2 s_2^{-1}} \cdot y^{r s_2^{-1}} = I.$$

From this condition, we obtain $g^{\alpha_1s_1^{-1}-\alpha_2s_2^{-1}} = y^{rs_2^{-1} -rs_1^{-1}}$, thus we have $g^{\alpha_1s_1^{-1}-\alpha_2s_2^{-1}} = g^{x(rs_2^{-1} -rs_1^{-1})}$. We obtain $x = (\alpha_1s_1^{-1}-\alpha_2s_2^{-1})(rs_2^{-1} -rs_1^{-1})^{-1}$, where the operations are performed in $\mathbb{Z}_q$.

My question. Why doesn't the book consider the two distinct challenges in general form (directly), i.e., we consider the two challenges as $(\alpha_1,r_1),(\alpha_2,r_2) \in \mathbb{Z}_q \times \mathbb{Z}_q$?

Hence, we combine both previously mentioned equations into $$g^{\alpha_1 s_1^{-1}} \cdot y^{r_1 s_1^{-1}} = g^{\alpha_2 s_2^{-1}} \cdot y^{r_2 s_2^{-1}} = I.$$

From this condition, we obtain $g^{\alpha_1s_1^{-1}-\alpha_2s_2^{-1}} = y^{r_2s_2^{-1} -r_1s_1^{-1}}$, thus we have $g^{\alpha_1s_1^{-1}-\alpha_2s_2^{-1}} = g^{x(r_2s_2^{-1} -r_1s_1^{-1})}$. We obtain $x = (\alpha_1s_1^{-1}-\alpha_2s_2^{-1})(r_2s_2^{-1} -r_1s_1^{-1})^{-1}$, where the operations are performed in $\mathbb{Z}_q$.

What is the motivation to split the cases into $(\alpha,r_1),(\alpha,r_2)$ (i.e., $\alpha$ is identical but the $r$'s are different) and $(\alpha_1,r),(\alpha_2,r)$ (i.e., $\alpha$'s are different but $r$ is identical)?

Answer 1

I'm not sure why the authors elected not to do this; your construction is completely valid. It also a good step towards understanding a broader principle: linear relations between unknown exponents can be verified via multiplication (or in more general cyclic groups, linear relations between unknown scalars can be verified via group operations), but revealing $n$ linear relationship between $n$ unknowns allows the unknowns to be recovered.

To make the linear algebra clearer, any challenge $(\alpha_i,r_i)$ leads to a response $s_i$ such that $$(s_i\ -r_i)\left(\matrix{k\\x}\right)=\alpha_i.$$ In particular, if we collect two signatures we have $$\begin{pmatrix}s_1&-r_1\\s_2&-r_2\end{pmatrix}\left(\matrix{k\\x}\right)=\begin{pmatrix}\alpha_1\\\alpha_2\end{pmatrix}$$ so that using Cramer's rule, we can recover your expression for $x$ by dividing both numerator and denominator by $s_1s_2$. Equally, we could write $$\left(\matrix{k\\x}\right)=\begin{pmatrix}s_1&-r_1\\s_2&-r_2\end{pmatrix}^{-1}\begin{pmatrix}\alpha_1\\\alpha_2\end{pmatrix},$$ note that your method/the above argument fail in the case where $(\alpha_1,r_1)$ and $(\alpha_2,r_2)$ are multiples of each other as this leads to a matrix with determinant zero (this minor complication may have been what discouraged the authors).

Note that this generalises to multiple commitments $k_i$ $1\le i\le n$ which can then provide up to $n$ responses to provide linear relationships with $n$ coefficients specified without revealing $x$, provided that the coefficients do not lead to a less than full rank linear system.