Zero-knowledge part

Adding the zero-knowledge part – concealing the assignment

Adding the zero-knowledge part – concealing the assignment In a zk-SNARK Jennifer wants to conceal all information about her assignment. However the hidings E ( L ( s ) ) , E ( R ( s ) ) , E ( O ( s ) ) , E ( H ( s ) ) do provide some information about the assignment.

For example, given some other satisfying assignment ( c ′ 1 , … , c ′ m ) Ted could compute the corresponding L ′ , R ′ , O ′ , H ′ and hidings E ( L ′ ( s ) ) , E ( R ′ ( s ) ) , E ( O ′ ( s ) ) , E ( H ′ ( s ) ) . If these come out different from Jennifer’s hidings, he could deduce that ( c ′ 1 , … , c ′ m ) is not Jennifer’s assignment.

To avoid such information leakage about her assignment, Jennifer will conceal her assignment by adding a “random T -shift” to each polynomial. That is, she chooses random δ 1 , δ 2 , δ 3 ∈ F ∗ p , and defines L z := L + δ 1 ⋅ T , R z := R + δ 2 ⋅ T , O z := O + δ 3 ⋅ T .

Assume L , R , O were produced from a satisfying assignment; hence, L ⋅ R − O = T ⋅ H for some polynomial H . As we’ve just added a multiple of T everywhere, T also divides L z ⋅ R z − O z . Let’s do the calculation to see this:

L z ⋅ R z − O z = ( L + δ 1 ⋅ T ) ( R + δ 2 ⋅ T ) – O − δ 3 ⋅ T = ( L ⋅ R − O ) + L ⋅ δ 2 ⋅ T + δ 1 ⋅ T ⋅ R + δ 1 δ 2 ⋅ T 2 – δ 3 ⋅ T = T ⋅ ( H + L ⋅ δ 2 + δ 1 ⋅ R + δ 1 δ 2 ⋅ T – δ 3 ) .

Thus, defining H z = H + L ⋅ δ 2 + δ 1 ⋅ R + δ 1 δ 2 ⋅ T − δ 3 , we have that L z ⋅ R z − O z = T ⋅ H z . Therefore, if Jennifer uses the polynomials L z , R z , O z , H z instead of L , R , O , H , Ted will always accept. On the other hand, these polynomials evaluated at s ∈ F p with T ( s ) ≠ 0 (which is all but d s ’s), reveal no information about the assignment. For example, as T ( s ) is non-zero and δ 1 is random, δ 1 ⋅ T ( s ) is a random value, and therefore L z ( s ) = L ( s ) + δ 1 ⋅ T ( s ) reveals no information about L ( s ) as it is masked by this random value.