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

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)?

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.
• Could you please elaborate on why the matrix determinant is zero if $(\alpha_1,r_1)$ is a scalar multiple of $(\alpha_2,r_2)$? Because the obvious argument is that the matrix determinant is zero if the $(s_1,-r_1)$ is the scalar multiple of $(s_2,-r_2)$. Nevertheless, I also obtain the following analysis. From the prover response, we have $s_i k = \alpha_i + r_i \cdot x$, Thus, we have the following matrix equation: $\begin{pmatrix} \alpha_1 & r_1 \\ \alpha_2 & r_2 \end{pmatrix} \begin{pmatrix} 1 \\ x\end{pmatrix}= k\begin{pmatrix} s_1 \\ s_2 \end{pmatrix}.$ But here we need $k$ to find $x$. Commented 2 days ago
• Ah, apparently, if $(\alpha_2,r_2) = \beta(\alpha_1,r_1)$ for some scalar $\beta$, then $\alpha_2 = \beta \alpha_1$ and $r_2 = \beta r_1$. This implies $s_2 k = \alpha_2 + xr_2 = \beta \alpha_1 + x \beta r_1 = \beta(\alpha_1 + xr_1) = \beta s_1 k$. Since $k \in \mathbb{Z}_q^*$, we conclude that $s_2 = \beta s_1$. Thus if $(\alpha_1,r_1)$ is a scalar multiple of $(\alpha_2,r_2)$, then $(s_2,-r_2)$ is a scalar multiple of $(s_1,-r_1)$. I think this answers my previous question. Thank you. Commented 2 days ago