# Geometric Cryptography and Zero-Knowledge Proofs

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?

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.