Zero-Knowledge proof The zero-knowledge property can be attacked using a brute-force attack on the coecients of the polynomial: the protocol must be secure even if there is only one coecient and it is 1. The checks that the Verier performs are: gp = (gp) = gp (cid:0) gH(r) (cid:1) Z(r) (verication of polynomial roots) (verication of correct use of polynomial) The zero-knowledge property can be preserved for brute force attacks by reapplying a shift on the values of a value. To extract information, the Verier would have to nd this value, which is considered computationally infeasible. Moreover, randomization is statistically indistinguishable from chance. 33 , The Veriers operations thus become: (gp) = gH(r) Z(r) (cid:16) (gp) (cid:17) = (cid:16)(cid:0) gp (cid:16) (cid:17)

(cid:1) (cid:17) Non-interactivity and trusted setup The only one who can be certain of the validity of an interactive zero-knowledge proof is the Verier. From an outside observers point of view, the Verier may have colluded with the Prover by telling him the secret values r and . This is useful in some applications where you do not want to allow the proof to be replicated to other , but in the case of distributed systems such as the blockchain it is inecient to recreate the proof for everyone. The parameters you want to keep secret are Z(r) and . One could use the same method used to encrypt the powers of r, but as already mentioned homomorphic encryption does not allow multiplication of two cipher values.

The solution is the use of bilinear cryptographic maps, i.e., a function e(g, g) that given two cipher inputs ga and gb produces deterministically, using a map, their multiplied representation e(ga, gb) = e(g, g)ab. Since the function uses two dierent groups as domain and co-domain, it is not possible to multiply the result by another cipher value. The main properties, obtained using elliptic curves, can be expressed as the following equations: e(ga, gb) = e(gb, ga) = e(gab, g1) = e(g1, gab) = e(g1, ga)b = e(g1, g1)ab We assume there is a trusted participant who generates the secrets r and and after computing the cipher powers and their -shifts decides to eliminate the plaintext values. These parameters are called common reference string (CRS). They are divided into two groups: Proving key: i Proving key: i 0, . . . , d } Verication key: (gZ(r), g) : (gri , gri ) Using the verication key and having obtained gp, gp and gH(r) from the Prover, the

Verier checks: e(gp, g1) = e(gZ(r), gH(r)) e(gp, g) = e(gp , g1) 34 The problem with this approach is that one must trust that secret values, which are named toxic waste, will be eliminated. Eli Ben-Sasson et al. described in 2015 a method to minimize this assumption by using a multiparty computation (MPC) , in which an arbitrary number of participants contribute and at least one of them is required to delete their generated values to make the procedure secure. ZCash, an anonymous blockchain based on SNARK , organized the ceremony of powers of tau to generate its own common reference string.