Geometric Cryptography and Zero-Knowledge Proofs

Question

Trying to understand zero-knowledge proofs, I came across this page, which provides an excellent example of a simple cryptographic protocol. I will reproduce the protocol here for the sake of completion.

Assumptions: Let us assume that only (classical Greek) geometric construction is allowed. So we can only use a compass and a straight-edge and we can only perform those operations which can be geometrically constructed. Specifically, an arbitrary (given) angle cannot be trisected but any arbitrary angle can be tripled easily.

Initialization: Alice has a secret, an angle $X_A$. Maybe she wants to sell it or use it to prove her identity later. Alice constructs $Y_A=3*X_A$ and publishes it. Because trisecting an angle is impossible, Alice is confident that she is the only one who knows $X_A$.

Identification Protocol: Bob comes along and wants to buy $X_A$ or verify Alice's identity.

1. Bob initiates a check.
2. Alice selects an angle $K$ at random. Alice constructs $R = 3*K$ and gives $R$ to Bob.
3. Bob flips a coin and tells Alice the result.
4. If Bob says "heads", Alice gives Bob a copy of the angle $K$ and Bob checks that $3*K = R$.
5. If Bob says "tails", Alice gives Bob a copy of the angle $L = K + X_A$ and Bob checks that $3*L = R + Y_A$.
6. Bob can rinse and repeat as many times as he wants.

Question: Why are steps three and four a part of the protocol? Specifically, why is step four even necessary? What is wrong with

• Bob initiates a check.
• Alice come up with a new random $K$ and gives $R=3*K$ to Bob.
• Then Alice gives $K+X_A$ to Bob and Bob checks it.
• Bob initiates as many checks as he wants and stops when he is satisfied.

Why isn't this enough?

Answer 1

Suppose that the second approach is used, this would allow an attacker to impose Alice. The intuition is that, as long as an attacker knows what is Bob going to ask him, he will be able to make things as he wishes in order for verification to pass.

Basically, the attacker wants to give Bob a (chosen) value of $R$ such that when he gives $L'$ to Bob verification holds ($L'$ would be $L = K + X_A$ in the case of Alice). This means that $3\ast L'$ should be equal to $R + Y_A$. This is easy since he can choose at first a random value for $L'$ and then set $R$ to be $3\ast L' - Y_A$ (recall that $Y_A$ is public!), you can check that verification will pass.

Notice that this works since the attacker sends $L'$ and $R$ simultaneously. This fails in the former protocol since Alice is asked to commit to $R$ at the beginning and then compute $L$ from there depending on Bob's choice.