Initial Inspection

First, let us try to define more precisely the goal of the puzzle just from the instructions, without looking into the code yet.

Given a group $G$ of order $q,$ we will write vectors of scalars and vectors of group elements in bold font, e.g. $a = (a_{0}, \dots, a_{n - 1}) \in (Z_{q})^{n}$ and $G = (G_{0}, \dots, G_{n - 1}) \in G^{n} .$ For two vectors $a = (a_{0}, \dots, a_{n - 1}) \in (Z_{q})^{n}$ and $b = (b_{0}, \dots, b_{n - 1}) \in (Z_{q})^{n},$ their scalar product is defined as $⟨ a, b ⟩ : = i = 0 \sum n - 1 a_{i} b_{i} mod q .$ Similarly, given $a = (a_{0}, \dots, a_{n - 1}) \in (Z_{q})^{n}$ and $G = (G_{0}, \dots, G_{n - 1}) \in G^{n},$ we let $⟨ a, G ⟩ : = i = 0 \sum n - 1 a_{i} G_{i} .$

Definition of the Proof System

Let us first try to specify the language for which the proof system is designed. We assume that the cyclic group $G$ of prime order $q$ and generators $G = (G_{0}, \dots, G_{n - 1})$ and $H$ are agreed upon by the prover and the verifier. Then, from the puzzle's description (and also from the code, as we will see), the language $L$ of interest is defined by the relation $R = {(x, w) ∣ x = (C_{a}, b) \in G \times (Z_{q})^{n}, w = (a, α) \in G^{n} \times Z_{q}, C_{a} = ⟨ a, G ⟩ + α H} .$

Recall that the language $L$ defined by this relation consists of all instances $x$ such that there exists a witness $w$ such that $(x, w) \in R .$

The protocol itself goes as follows:

$Prover parameters: (G, q, G, H) instance: (C_{a}, b) \in G \times (Z_{q})^{n} witness: (a, α) \in G^{n} \times Z_{q} relation: C_{a} = ⟨ a, G ⟩ + α H r \leftarrow_{$} (Z_{q})^{n} ρ, τ, ν \leftarrow_{$} Z_{q} C_{r} : = ⟨ r, G ⟩ + ρ H C_{1} : = ⟨ a, b ⟩ G_{1} + τ H C_{2} : = ⟨ r, b ⟩ G_{1} + ν H s : = a + γ r mod q u : = α + γ ρ mod q t : = τ + γ ν mod q C_{r}, C_{1}, C_{2} γ s, u, t Verifier parameters: (G, q, G, H) instance: (C_{a}, b) \in G \times (Z_{q})^{n} γ \leftarrow_{$} Z_{q} check that ⟨ s, G ⟩ + u H = C_{a} + γ C_{r} ⟨ s, b ⟩ G_{1} + t H = C_{1} + γ C_{2}$

The protocol is complete, meaning that for any instance $(C_{a}, b) \in L,$ an honestly generated proof is always accepted by the verifier. This holds because $⟨ s, G ⟩ + u H = ⟨ a + γ r, G ⟩ + (α + γ ρ) H = (⟨ a, G ⟩ + α H) + γ (⟨ r, G ⟩ + ρ H) = C_{a} + γ C_{r}$ and $⟨ s, b ⟩ G_{1} + t H = ⟨ a + γ r, b ⟩ G_{1} + (τ + γ ν) H = (⟨ a, b ⟩ G_{1} + τ H) + γ (⟨ r, b ⟩ G_{1} + ν H) = C_{1} + γ C_{2} .$

Proof of Knowledge

One can also check that the proof system is extractable, which follows from a property called special soundness: for any instance in language $L,$ given two accepting transcripts with the same commitments $(C_{r}, C_{1}, C_{2})$ but different challenges $γ^{(1)}$ and $γ^{(2)},$ one can compute a witness. Indeed, let $((C_{r}, C_{1}, C_{2}), γ^{(1)}, (s^{(1)}, u^{(1)}, t^{(1)})), ((C_{r}, C_{1}, C_{2}), γ^{(2)}, (s^{(2)}, u^{(2)}, t^{(2)}))$ be two accepting transcripts for some instance $(C_{a}, b)$ such that $γ^{(1)} \neq = γ^{(2)} .$ Let $a : = \frac{γ ^{(1)} s ^{(2)} - γ ^{(2)} s ^{(1)}}{γ ^{(1)} - γ ^{(2)}}, α : = \frac{γ ^{(1)} u ^{(2)} - γ ^{(2)} u ^{(1)}}{γ ^{(1)} - γ ^{(2)}} .$ Since both transcripts are accepting, we have $⟨ s^{(1)}, G ⟩ + u^{(1)} H = C_{a} + γ^{(1)} C_{r}, ⟨ s^{(2)}, G ⟩ + u^{(2)} H = C_{a} + γ^{(2)} C_{r} .$ Then $⟨ a, G ⟩ + α H = \frac{1}{γ ^{(1)} - γ ^{(2)}} (γ^{(1)} ⟨ s^{(2)}, G ⟩ - γ^{(2)} ⟨ s^{(1)}, G ⟩ + γ^{(1)} u^{(2)} H - γ^{(2)} u^{(1)} H) = \frac{1}{γ ^{(1)} - γ ^{(2)}} (γ^{(1)} (C_{a} + γ^{(2)} C_{r} - u^{(2)} H) - γ^{(2)} (C_{a} + γ^{(1)} C_{r} - u^{(1)} H) + γ^{(1)} u^{(2)} H - γ^{(2)} u^{(1)} H) = C_{a} .$ Hence, the relation defining the language is satisfied and $(a, α)$ is indeed a witness that the instance $(C_{a}, b)$ is in $L .$

Zero-Knowledge?

The puzzle instructions asks us to find $a,$ which is part of the witness, from a few proofs generated by Bob. If the protocol is zero-knowledge, this shouldn't be possible. Is it zero-knowledge, though, from a theoretical point of view?

The answer is yes. Namely, the interactive protocol as defined above can be shown to be honest-verifier zero-knowledge. The simulator, whose task is to generate a fake transcript distributed as a true transcript between a prover and an honest verifier without knowing the witness $(a, α),$ works as follows:

$s \leftarrow_{$} (Z_{q})^{n}, u \leftarrow_{$} Z_{q}, t \leftarrow_{$} Z_{q} γ \leftarrow_{$} Z_{q} C_{r} : = γ^{- 1} (⟨ s, G ⟩ + u H - C_{a}) C_{1} \leftarrow_{$} G C_{2} : = γ^{- 1} (⟨ s, b ⟩ G_{1} + t H - C_{1}) return ((C_{r}, C_{1}, C_{2}), γ, (s, u, t))$

Something Strange

There is something odd with the way we described the proof system: vector $b$ plays no role in the relation $R = {(x, w) ∣ x = (C_{a}, b) \in G \times (Z_{q})^{n}, w = (a, α) \in G^{n} \times Z_{q}, C_{a} = ⟨ a, G ⟩ + α H} .$ In particular, note that the proof that the system is extractable did not use the second equation checked by the verifier (meaning extractability still holds even if this check is omitted).

For this reason, it would make more sense to actually include $C_{1},$ the commitment to the inner product $⟨ a, b ⟩,$ in the instance and randomness $τ$ in the witness and to define the relation as $R^{'} = {(σ, ω) ∣ σ = (C_{a}, C_{1}, b) \in G \times G \times (Z_{q})^{n}, ω = (a, α, τ) \in G^{n} \times Z_{q} \times Z_{q}, C_{a} = ⟨ a, G ⟩ + α H, C_{1} = ⟨ a, b ⟩ G_{1} + τ H} .$

By doing this, the protocol would now be specified as follows:

$Prover parameters: (G, q, G, H) instance: (C_{a}, C_{1}, b) \in G \times G \times (Z_{q})^{n} witness: (a, α, τ) \in G^{n} \times Z_{q} \times Z_{q} relation: C_{a} = ⟨ a, G ⟩ + α H C_{1} = ⟨ a, b ⟩ G_{1} + τ H r \leftarrow_{$} (Z_{q})^{n} ρ, ν \leftarrow_{$} Z_{q} C_{r} : = ⟨ r, G ⟩ + ρ H C_{2} : = ⟨ r, b ⟩ G_{1} + ν H s : = a + γ r mod q u : = α + γ ρ mod q t : = τ + γ ν mod q C_{r}, C_{2} γ s, u, t Verifier parameters: (G, q, G, H) instance: (C_{a}, C_{1}, b) \in G \times G \times (Z_{q})^{n} γ \leftarrow_{$} Z_{q} check that ⟨ s, G ⟩ + u H = C_{a} + γ C_{r} ⟨ s, b ⟩ G_{1} + t H = C_{1} + γ C_{2}$

However, this is not important for solving the puzzle and we will stick to the original, albeit unnatural, description.

Crypto Book (Work in Progress)