To-be-Adaptive-is-to-be-Strong.md

To-be-Adaptive-is-to-be-Strong.md

This hack describes a proof system that utilize Fiat-Shamir transform to make it non-interactive. However, in the proposed system, verifier computes the challenge e only from (commit_key, proof.commitment). To be more specific, e = b2s_hash_to_field(commit_key, proof.commitment).

If the adversary want to commit to two different values (let's call them $a_1, a_2$) in the offline phase, then he can use two different value (let's call them $x_1, x_2$) in the step 1 of online phase. And then he computes $$ C_\rho = x_1*g + \rho h, $$ $$ C_\tau = x_2g + \tau *h. $$

where $(g, h)$ is the commit key. Note that the verifier checks if

$$ sg + uh = C_\rho + e \times (a_1g + r_1h), $$ $$ sg + th = C_\tau + e \times (a_2g + r_2h). $$

This implies that $(x_1 - x_2) + e \times (a_1 - a_2) = 0$ holds almost with probability 1 due to the fact that the discrete log of g with respect to h(vice versa) is not known to anyone.

Since e does not depend on $a_1, a_2$, only depends on $g, h, x_1, x_2$. It's easy to find $a_1, a_2$, which we describe it here:

1. sample a random element $x_1$, then let $x_2 = x_1 + 1$.
2. compute e as described above. If $e = 0$, go to step 1. Note that the probability that $e = 0$ is negligible.
3. sample a random element $a_1$, then let $a_2 = a_1 - \frac{(x_2 - x_1)}{e}$.

Given these $a_1, a_2$. We can construct an attack vector as follows:

1. $s = x_1 + e \times a_1 = x_2 + e \times a_2$.
2. $u = \rho + e \times r_1$.
3. $t = \tau + e \times r_2$.

It's easy to see that our attack vector is valid.

The above attack is inspired by citation 1.

Reference

1. Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios" (PDF). In Wang, Xiaoyun; Sako, Kazue (eds.). Advances in Cryptology – ASIACRYPT 2012. pp. 626–643.