Any Idea on this identification scheme's problem?

Question

I was looking at the exercises of Cryptography theory and practice and I could not find the answer to this question anyone has an idea?

Answer 1

Well, here's one obvious attack:

• Eve wants to impersonate Alice.

• Bob wants Eve to prove that she's Alice. Bob gives a value $x$ to Eve

• Eve turns around, and asks Alice to prove that she (Alice) is Alice. Eve gives $x$ to Alice

• Alice gives the value $y$ to Eve

• Eve then gives the value $y$ to Bob

Of course, that's not the attack that Stinson is looking for...

For the attack that Stinson is thinking of, here's a hint:

• For a random quadratic residue $x$, how many values of $y$ are there s.t. $y^2 = x$?

• Suppose Bob picks a random value $y$ and computes $x = y^2 \bmod n$ and gives it to Alice, what is the probability that Alice will compute a $y'$ that's neither $y$ nor $n-y$?

• If Bob knows $y$ and $y'$, what could he do with those values? Hint: consider $y^2 - y'^2 = (y + y')(y - y')$