Zero-Knowledge Proof (ZKP) Scheme

Function-hiding functional commitment

In this page, we will review function-hiding functional commitment zero-knowlege proof (ZKP) scheme.

In this scheme, F\mathbf{F} is a field of large prime order pp such that log(p)=(λ)log(p) = Ω(λ) where λ\lambda is the security parameter.

1)1) The Prover obtains matrices AA, BB and CC for the arithmetic circuit so that matrices AA and BB are tt-strictly lower triangular matrices and matrix CC is tt-diagonal matrix. Here, tt is the size of the input. Also, these matrices apply in AzoBz=CzAz\hspace{1mm} o\hspace{1mm} Bz=Cz where z=(x,w,y)z=(x,w,y), xx is input, ww is witness (intermediate) and yy is output.

The Prover does the following stage based on the following construction:

11)1-1) Initialize three zero square matrices A,B,CA, B, C over F\mathbf{F} of order ng+no+1n_g +n_o + 1 where ngn_g is the number of gates and non_o is the number of outputs.

Here, the gate ii is corresponding to tuple (li,ri,si)(l_i, r_i, s_i) where lil_i and rir_i are left and right input wire indices, respectively and sis_i is gate selector, addition or multiplication. Also in the following construction nin_i is the number of inputs.

12)1-2)For i=1,..,ng: i=1,.., n_g: a)a) C1+ni+i,1+ni+i=1C_{1+n_i+i,1+n_i+i}=1 b)b) if si s_i is addition - A1+ni+i,1=1A_{1+n_i+i,1}=1 - B1+ni+i,1+li=1B_{1+n_i+i,1+l_i}=1 ( if the left input is a number, its value is set) - B1+ni+i,1+ri=1B_{1+n_i+i,1+r_i}=1 ( if the right input is a number, its value is set) c)c) If sis_i is multiplication - A1+ni+i,1+li=1A_{1+n_i+i,1+l_i}=1 ( if the left input is a number, its value is set) - B1+ni+i,1+ri=1B_{1+n_i+i,1+r_i}=1 ( if the right input is a number, its value is set) 13)1-3) Outputs matrices A,BA, B and CC.

2)2) The Prover encodes each matrix A,BA, B and CC by three polynomials. In such a way that encodes matrix MM, M{A,B,C}M\in\{A, B, C\}, by polynomials rowM(x)row_{M}(x), colM(x)col_M(x) and valM(x)val_M(x) so that rowM(γi)=ωrirow_M(\gamma^i)=\omega^{r_i}, colM(γi)=ωcicol_M(\gamma^i)=\omega^{c_i} and valM(γi)=vival_M(\gamma^i)=v_i for i{0,1,2,..,m1}i\in\{0,1,2,..,m-1\} where γ\gamma is a generator of multiplicative subgroup K\mathbf{K}of F\mathbf{F} of order mm (K=<γ>\mathbf{K}=<\gamma> and K=m|\mathbf{K}|=m) and ω\omega is a generator of multiplicative subgroup H\mathbf{H} of F\mathbf{F} of order n (H=<ω>\mathbf{H}=<\omega> and H=n|\mathbf{H}|=n). Also mm is the number of nonzero elements in the matrix MM. nn is the order of the matrix. Also rir_i, cic_i (ri,ci{0,1,...,n1}r_i,c_i\in \{0,1,...,n-1\}) and viv_i (viFv_i\in \mathbf{F}) are row number, column number and value of ithi^{th} nonzero element, respectively.

3)3) The Prover sends obtained nine polynomials to the Verifier.

4)4) A Polynomial interactive oracle proofs (polyIOP) does between the Prover and the Verifier to verify that three polynomials rowArow_A, colAcol_A and valAval_A, also three polynomials rowBrow_B, colBcol_B, valBval_B are corresponding to tt-strictly lower triangular matrices and three polynomials rowCrow_C, colCcol_C, valCval_C is corresponding to a tt-diagonal matrix. This polyIOP includes:

41)4-1) To prove strictly lower triangularity of the matrices AA and BB must prove that logωrowM(γi)>logωcolM(γi)\log^{row_M(\gamma^i)}_{\omega}> \log^{col_M(\gamma^i)}_{\omega} for i{0,1,..,m1}i \in \{0,1,..,m-1\}and M{A,B}M\in\{A,B\}. This does by Discrete\red{Discrete}Discretelogcomparisonprotocol\red{Discrete-log\hspace{1mm} comparison\hspace{1mm} protocol}. 42)4-2) To prove the first tt rows of AA and BB are all zeros must prove that rowM(K){ωt,ωt+1,...,ωn1}row_M(\mathbf{K})\subseteq\{\omega^t,\omega^{t+1},...,\omega^{n-1}\}. This does by subsetoverKprotocol\red{subset\hspace{1mm} over \hspace{1mm}\mathbf{K}\hspace{1mm} protocol}. 43)4-3) To prove the diagonality of the matrix CC must prove that seqK(rowC)=seqK(colC)seq_{\mathbf{K}}(row_C)=seq_{\mathbf{K}}(col_C)where seqK(h)=(h(k):kK)seq_{\mathbf{K}}(h)=(h(k):k\in\mathbf{K}). This does by Geometricsequence\red{Geometric\hspace{1mm} sequence} and zerooverKprotocols\red{zero\hspace{1mm}over\hspace{1mm}\mathbf{K}\hspace{1mm}protocols}. 44)4-4) To prove the first tt rows of CC are all zeros must prove that there is a vector v(F)ntv\in(\mathbf{F^*})^{n-t} so that seqK(valC)=v0seq_{\mathbf{K}}(val_C)=\vec{v}||\vec{0} . This does by Geometricsequence\red{Geometric\hspace{1mm} sequence} and zerooverKprotocols\red{zero\hspace{1mm}over\hspace{1mm}\mathbf{K}\hspace{1mm}protocols}. 434-3 and 444-4 result that all the non-zero entries of the matrix CC are in the positions (ωt,ωt),(ωt+1,ωt+1),...,(ωn,ωn)(\omega^t,\omega^t),(\omega^{t+1},\omega^{t+1}),...,(\omega^n,\omega^n).

Now, we will show the steps through an example.

Example\red{Example}:

R1(1)4=0R_1^{(1)}-4=0 R1(2)5R1(1)=0R_1^{(2)}-5R_1^{(1)}=0 R1(3)R1(2)11=0R_1^{(3)}-R_1^{(2)}-11=0 R1(4)R1(3)7=0R_1^{(4)}-\frac{R_1^{(3)}}{7}=0

1)1) Let the computation be done in F\mathbf{F} of order p=181p=181. We consider z=(1,x,w1,w2,y)z=(1,x,w_1,w_2,y) where w1=5xw_1=5x, w2=w1+11w_2=w_1+11 and y=w27y=\frac{w_2}{7}. Therefore with input x=4x=4, z=(1,4,20,31,82)z=(1,4,20,31,82). Note that the inverse of number aa in this field is ap2(modp)a^{p-2} (\textrm{mod}\hspace{1mm}p) , so 71=267^{-1}=26.

Based on stage 1 obtain:

A=[0000000000010001000000010]A=\begin{bmatrix} 0&0&0&0&0\\ 0&0&0&0&0\\ 0&1&0&0&0\\ 1&0&0&0&0\\ 0&0&0&1&0\\ \end{bmatrix}, B=[000000000050000110100260000]B=\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\5&0&0&0&0\\11&0&1&0&0\\26&0&0&0&0\\\end{bmatrix}and C=[0000000000001000001000001]C=\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\\end{bmatrix}.

It can be seen that matrices AA and BB are 22-strictly lower triangular and matrix CC is 22-diagonal. Also AzoBz=[00203182]=CzAz\hspace{1mm}o\hspace{1mm}Bz=\begin{bmatrix}0\\0\\20\\31\\82\\\end{bmatrix}=Cz.

2)2) To encode matrix AA, consider multiplicative subgroup H\mathbf{H} of order n=5n=5 with generator ω=23659(mod181)\omega=2^{36}\equiv 59 (\textrm{mod}\hspace{1mm}181). Note that if gg is a generator of field F\mathbf{F} of order pp, then gp1ng^{\frac{p-1}{n}}is a generator of a multiplicative subgroup of it of order nn. Therefore H={1,ω,ω2,ω3,ω4}={1,59,42,125,135}\mathbf{H}=\{1,\omega,\omega^2,\omega^3,\omega^4\}=\{1,59,42,125,135\}.

Also, consider multiplicative subgroup K\mathbf{K} of order m=3m=3 with generator γ=26048(mod181)\gamma=2^{60}\equiv48(\textrm{mod}\hspace{1mm}181). Therefore K={1,γ,γ2}={1,48,132}\mathbf{K}=\{1,\gamma,\gamma^2\}=\{1,48,132\}.

First, build a polynomial rowA(x)row_A(x). Since matrix AA has three non-zero entries the first of them is in the second row, and then c0=2c_0=2 and rowA(γ0)=ω2row_A(\gamma^0)=\omega^2 , note that rows numbered zero, the second is in the third row, and then c1=3c_1=3 and rowA(γ1)=ω3row_A(\gamma^1)=\omega^3 and the third is in the fourth row, then c2=4c_2=4 and rowA(γ2)=ω4row_A(\gamma^2)=\omega^4.

According to the values ​​defined for γ\gamma and ω\omega, we have rowA(1)=42row_A(1)=42, rowA(48)=125row_A(48)=125 and rowA(132)=135row_A(132)=135. Therefore based on Lagrange polynomials, have rowA(x)=i=13yiLi(x)row_A(x)=\sum_{i=1}^{3}y_iL_i(x), sorowA(x)=42L1(x)+125L2(x)+135L3(x)row_A(x)=42L_1(x)+125L_2(x)+135L_3(x), where L1(x)=(x48)(x132)(148)(1132)=(x48)(x132)(47)(131)L_1(x)=\frac{(x-48)(x-132)}{(1-48)(1-132)}=\frac{(x-48)(x-132)}{(-47)(-131)}. Now, since 47134(mod181)-47\equiv134\hspace{1mm}(\textrm{mod}\hspace{1mm}181), 13150(mod181)-131\equiv50\hspace{1mm}(\textrm{mod}\hspace{1mm}181), 48133(mod181)-48\equiv133\hspace{1mm}(\textrm{mod}\hspace{1mm}181)and 13249(mod181)-132\equiv49\hspace{1mm}(\textrm{mod}\hspace{1mm}181), therefore L1(x)=(x+133)(x+49)(134)(50)L_1(x)=\frac{(x+133)(x+49)}{(134)(50)}and since (134)(50)3(mod181)(134)(50)\equiv 3\hspace{1mm}(\textrm{mod}\hspace{1mm}181)and 31121(mod181)3^{-1}\equiv 121\hspace{1mm}(\textrm{mod}\hspace{1mm}181), have L1(x)=121(x+133)(x+49)=121(x2+x+1)=121x2+121x+121L_1(x)=121(x+133)(x+49)=121(x^2+x+1)=121x^2+121x+121. We get in a similar way that L2(x)=16x2+44x+121L_2(x)=16x^2+44x+121 and L3(x)=44x2+16x+121L_3(x)=44x^2+16x+121. Therefore rowA(x)=171x2+72x+161row_A(x)=171x^2+72x+161.

Now, we obtain colA(x)col_A(x). Since matrix AA has three non-zero entries the first of them is in the first column, then r0=1r_0=1 and colA(γ0)=ω1col_A(\gamma^0)=\omega^1 , note that columns numbered zero, the second is in the zero column, and then r1=0r_1=0 and colA(γ1)=ω0col_A(\gamma^1)=\omega^0 and the third is in the third column, then r2=3r_2=3 and rowA(γ2)=ω3row_A(\gamma^2)=\omega^3. Therefore colA(1)=59col_A(1)=59, colA(48)=1col_A(48)=1 and colA(132)=125col_A(132)=125. So colA(x)=59L1(x)+L2(x)+125L3(x)=166x2+133x+122col_A(x)=59L_1(x)+L_2(x)+125L_3(x)=166x^2+133x+122.

Now, we obtain valA(x)val_A(x). Since matrix AA has three non-zero entries such that the value of all of them is one, therefore v0=v1=v2=1v_0=v_1=v_2=1. So, valA(x)=L1(x)+L2(x)+L3(x)=1val_A(x)=L_1(x)+L_2(x)+L_3(x)=1.

Therefore, the matrix AA encodes by rowA(x)=171x2+72x+161row_A(x)=171x^2+72x+161, colA(x)=166x2+133x+122col_A(x)=166x^2+133x+122 and valA(x)=1val_A(x)=1.

Now, to encode the matrix BB, consider multiplicative subgroup K\mathbf{K}, a subgroup of order 44 with generator γ=21804=245162(mod181)\gamma=2^{\frac{180}{4}}=2^{45}\equiv162\hspace{1mm}(\textrm{mod}\hspace{1mm}181). Therefore K={1,γ,γ2,γ3}={1,162,180,19}\mathbf{K}=\{1,\gamma,\gamma^2,\gamma^3\}=\{1,162,180,19\}.

First, build a polynomial rowB(x)row_B(x). Since matrix BB has four non-zero entries such that the first of them is in the second row, then c0=2c_0=2 and rowB(γ0)=ω2row_B(\gamma^0)=\omega^2 , the second and the third are in the third row, and then c1=c2=3c_1=c_2=3 and rowB(γ1)=rowB(γ2)=ω3row_B(\gamma^1)=row_B(\gamma^2)=\omega^3 and the fourth is in the fourth row, then c3=4c_3=4 and rowB(γ3)=ω4row_B(\gamma^3)=\omega^4. Therefore, rowB(1)=42row_B(1)=42, rowB(162)=125row_B(162)=125, rowB(180)=125row_B(180)=125 and rowB(19)=135row_B(19)=135. So rowB(x)=42L1(x)+125L2(x)+125L3(x)+135L3(x)row_B(x)=42L_1(x)+125L_2(x)+125L_3(x)+135L_3(x) where L1(x)=(x162)(x180)(x19)(1162)(1180)(119)=(x+19)(x+1)(x+162)(20)(2)(163)=(x+19)(x+1)(x+162)4L_1(x)=\frac{(x-162)(x-180)(x-19)}{(1-162)(1-180)(1-19)}=\frac{(x+19)(x+1)(x+162)}{(20)(2)(163)}=\frac{(x+19)(x+1)(x+162)}{4}. Since 41136(mod181)4^{-1}\equiv136\hspace{1mm}(\textrm{mod}\hspace{1mm}181), then L1(x)=136(x+19)(x+1)(x+162)=136(x3+x2+x+1)=136x3+136x2+136x+136L_1(x)=136(x+19)(x+1)(x+162)=136(x^3+x^2+x+1)=136x^3+136x^2+136x+136. We get in a similar way that L2(x)=131x3+45x2+50x+136L_2(x)=131x^3+45x^2+50x+136, L3(x)=45x3+136x2+45x+136L_3(x)=45x^3+136x^2+45x+136 and L4(x)=50x3+45x2+131x+136L_4(x)=50x^3+45x^2+131x+136. Therefore rowB(x)=72x3+22x2+158x+152row_B(x)=72x^3+22x^2+158x+152.

Now, we obtain colB(x)col_B(x). Since matrix BB has four non-zero entries that the first, second and fourth of them are in zero column, then r0=r1=r3=0r_0=r_1=r_3=0 and colB(γ0)=colB(γ1)=colB(γ3)=ω0col_B(\gamma^0)=col_B(\gamma^1)=col_B(\gamma^3)=\omega^0 and the third is in the second column, then r2=2r_2=2 and colB(γ2)=ω2col_B(\gamma^2)=\omega^2 . Therefore colB(1)=1col_B(1)=1, colB(162)=1col_B(162)=1, colB(180)=42col_B(180)=42and colB(19)=1col_B(19)=1. So colB(x)=L1(x)+L2(x)+42L3(x)+L4(x)=35x3+146x2+col_B(x)=L_1(x)+L_2(x)+42L_3(x)+L_4(x)=35x^3+146x^2+ 35x+14735x+147.

Now, we obtain valB(x)val_B(x). Since matrix BB has four non-zero entries that value of them are 55, 1111, 11 and 2626, respectively. Therefore v0=v1=v2=1v_0=v_1=v_2=1valB(γ0)=5val_B(\gamma^0)=5, valB(γ1)=11val_B(\gamma^1)=11, valB(γ2)=1val_B(\gamma^2)=1and valB(γ3)=26val_B(\gamma^3)=26. So, valB(1)=5val_B(1)=5, valB(162)=11val_B(162)=11, valB(180)=1val_B(180)=1and valB(19)=26val_B(19)=26. Therefore valB(x)=5L1(x)+val_B(x)=5L_1(x)+ 11L2(x)+L3(x)+26L4(x)=27x3+128x2+156x+5611L_2(x)+L_3(x)+26L_4(x)=27x^3+128x^2+156x+56.

Therefore, the matrix BB encodes by rowB(x)=171x2+72x+161row_B(x)=171x^2+72x+161 rowB(x)=72x3+22x2+158x+152row_B(x)=72x^3+22x^2+158x+152, colB(x)=35x3+146x2+col_B(x)=35x^3+146x^2+ 35x+14735x+147and valB(x)=27x3+128x2+156x+56val_B(x)=27x^3+128x^2+156x+56.

Now, to encode the matrix CC, consider multiplicative subgroup K\mathbf{K}, a subgroup of order 33 with generator γ=21803=26048(mod181)\gamma=2^{\frac{180}{3}}=2^{60}\equiv48\hspace{1mm}(\textrm{mod}\hspace{1mm}181). Therefore K={1,γ,γ2}={1,48,132}\mathbf{K}=\{1,\gamma,\gamma^2\}=\{1,48,132\}.

First, build a polynomial rowC(x)row_C(x). In a similar way, Since matrix CC has three non-zero entries that are in the third, fourth and fifth rows, therefore rowC(γ0)=ω2row_C(\gamma^0)=\omega^2 , rowC(γ1)=ω3row_C(\gamma^1)=\omega^3 and rowC(γ2)=ω4row_C(\gamma^2)=\omega^4. Then rowC(1)=42row_C(1)=42 , rowC(48)=125row_C(48)=125 and rowC(132)=135row_C(132)=135. SorowC(x)=42L1(x)+125L2(x)+135L3(x)row_C(x)=42L_1(x)+125L_2(x)+135L_3(x), therefore rowC(x)=171x2+72x+161row_C(x)=171x^2+72x+161.

Now, since CC is a diagonal matrix, polynomials rowC(x)row_C(x) and colC(x)col_C(x)are equal. Also, since the matrix CC has three non-zero entries such that the value of all of them is one, therefore v0=v1=v2=1v_0=v_1=v_2=1. So, valC(x)=L1(x)+L2(x)+L3(x)=1val_C(x)=L_1(x)+L_2(x)+L_3(x)=1.

Therefore, the matrix CC encodes by rowC(x)=171x2+72x+161row_C(x)=171x^2+72x+161, colC(x)=171x2+72x+161col_C(x)=171x^2+72x+161 and valC(x)=1val_C(x)=1.

3)3) The Prover sends obtained nine polynomials to the Verifier.

4)4) A Polynomial interactive oracle proof (polyIOP) is between the Prover and the Verifier to verify that three polynomials rowArow_A, colAcol_A and valAval_A, also three polynomials rowBrow_B, colBcol_B, valBval_B are corresponding to tt-strictly lower triangular matrices and three polynomials rowCrow_C, colCcol_C, valCval_C is corresponding to a tt-diagonal matrix. This polyIOP includes:

The first, see polyIOP to prove tt-strictly lower triangularity of the matrix AA.

41)4-1) 411)4-1-1) The Prover interpolates polynomial hh such that seqK(h)=ωt,ωt+1,..,ωn1,0,..,0seq_{\mathbf{K}}(h)=\omega^t,\omega^{t+1},..,\omega^{n-1},0,..,0. Here t=2t=2 and n=5n=5, therefore seqK(h)=ω2,ω3,ω4,0,0seq_{\mathbf{K}}(h)=\omega^2,\omega^3,\omega^4,0,0. this means that {h(k):kK={1,48,132}}={ω2,ω3,ω4,0,0}={42,125,135,0,0}\{h(k):\hspace{1mm}k\in\mathbf{K}=\{1,48,132\}\}=\{\omega^2,\omega^3,\omega^4,0,0\}=\{42,125,135,0,0\}. Therefore h(1)=42h(1)=42, h(48)=125h(48)=125 and h(132)=135h(132)=135. So h(x)=42L1(x)+125L2(x)+135L3(x)=171x2+72x+161h(x)=42L_1(x)+125L_2(x)+135L_3(x)=171x^2+72x+161.

412)4-1-2) The Prover sends hh to the Verifier.

413)4-1-3) The Prover and the Verifier do GeometricSequenceTest\red{Geometric\hspace{1mm}Sequence\hspace{1mm}Test} on hh (to verify correct construction of polynomial hh). In GeometricSequenceTestGeometric\hspace{1mm} Sequence\hspace{1mm} Test want to prove that SeqK(h)=a1,a1r,..,a1rc11,a2,a2r,...,a2rc21,...,an,anr,...,anrcn1Seq_{\mathbf{K}}(h)=a_1,a_1r,..,a_1r^{c_1-1},a_2, a_2r,..., a_2r^{c_2-1},...,a_n,a_nr,...,a_nr^{c_n-1}. Since h(γ0)=ω2h(\gamma^0)=\omega^2, h(γ1)=ω3h(\gamma^1)=\omega^3 and h(γ2)=ω4h(\gamma^2)=\omega^4, then Geometric Sequence Test with a1=ω2a_1=\omega^2, r=ωr=\omega, c1=3c_1=3 and n=1n=1run. Let pi=j<icjp_i=\sum_{j<i}c_j for i{1,2,...,n}i\in \{1,2,...,n\}. Here p1=0p_1=0.

4131)4-1-3-1) The Verifier checks h(γpi)=aih(\gamma^{p_i})=a_i for i{1,2,...,n}i\in \{1,2,...,n\}. Here checks h(γ0)=a1=ω2h(\gamma^0)=a_1=\omega^2.

4132)4-1-3-2) The Prover and the Verifier run ZeroOverK\red{Zero\hspace{1mm}Over\hspace{1mm}\mathbf{K}} to check that for all kKk\in\mathbf{K}, have (h(γk)rh(k))i=1n(kγpi+ci1)=0(h(\gamma k)-rh(k))\prod_{i=1}^{n}(k-\gamma^{p_i+c_i-1})=0. Here, ZeroOverKZero\hspace{1mm}Over\hspace{1mm}\mathbf{K} run to check that for all kK={1,γ,γ2}k\in\mathbf{K}=\{1,\gamma,\gamma^2\}, have (h(γk)ωh(k))(kγ2)=0(h(\gamma k)-\omega h(k))(k-\gamma^2)=0. NoteNote: It is clear that if the construction of hh is correct, it applies this equality, because if k=1k=1, h(γk)=h(γ)=ωh(1)h(\gamma k)=h(\gamma)=\omega h(1) then h(γk)ωh(k)=0h(\gamma k)-\omega h(k)=0. If k=γk=\gamma, h(γk)=h(γ2)=ωh(γ)h(\gamma k)=h(\gamma^2)=\omega h(\gamma), then h(γk)ωh(k)=0h(\gamma k)-\omega h(k)=0. If k=γ2k=\gamma^2, then kγ2=0k-\gamma^2=0.

In ZeroOverKZero\hspace{1mm}Over\hspace{1mm}\mathbf{K}, want to prove that for all kKk\in\mathbf{K}, F(k)=0F(k)=0 where F(x)=G(x,fj1(α1x),fj2(α2x),...,fjt(αtx))F(x)=G(x,f_{j_1}(\alpha_1x),f_{j_2}(\alpha_2x),...,f_{j_t}(\alpha_tx)). Here F(x)=(h(γx)ωh(x))(xγ2)F(x)=(h(\gamma x)-\omega h(x))(x-\gamma^2), therefore since t=2t=2, F(x)=G(x,fj1(α1x),fj2(α2x))=(h(γx)ωh(x))(xγ2)F(x)=G(x,f_{j_1}(\alpha_1x),f_{j_2}(\alpha_2x))=(h(\gamma x)-\omega h(x))(x-\gamma^2), so fj1=fj2=hf_{j_1}=f_{j_2}=h, α1=γ\alpha_1=\gamma and α2=1\alpha_2=1.

41321)4-1-3-2-1) The Prover selects polynomials riF<2[x]r_i\in \mathbf{F}^{<2}[x], i{1,2,..,t}i\in \{1,2,..,t\}. Then computes masks mi(x)=ri(αi1x)ZK(αi1x)m_i(x)=r_i(\alpha_i^{-1}x)\mathbf{Z_K}(\alpha_i^{-1}x) and computes hi(x)=hi(x)+mi(x)h'_i(x)=h_i(x)+m_i(x) for i{1,2,..,t}i\in\{1,2,..,t\}. Here, selects r1,r2r_1,r_2.For example, let r1(x)=2+xr_1(x)=2+x and r2(x)=2xr_2(x)=2x. Therefore m1(x)=r1(α11x)ZK(α11x)m_1(x)=r_1(\alpha_1^{-1}x)\mathbf{Z_K}(\alpha_1^{-1}x) where α1=γ=48\alpha_1=\gamma=48, K={1,48,132}\mathbf{K}=\{1,48,132\}and ZK(x)=xK(xk)=(x1)(x48)(x132)\mathbf{Z_K}(x)=\prod_{x\in\mathbf{K}}(x-k)=(x-1)(x-48)(x-132). Therefore m1(x)=r1(132x)ZK(132x)=(2+132x)(132x1)(132x48)(132x132)=132x4+2x3+49x+179m_1(x)=r_1(132x)\mathbf{Z_K}(132x)=(2+132x)(132x-1)(132x-48)(132x-132)=132x^4+2x^3+49x+179 m2(x)=r2(α21x)ZK(α21x)=r2(x)ZK(x)=2x(x1)(x48)(x132)=2x4+179xm_2(x)=r_2(\alpha_2^{-1}x)\mathbf{Z_K}(\alpha_2^{-1}x)=r_2(x)\mathbf{Z_K}(x)=2x(x-1)(x-48)(x-132)=2x^4+179x. Then computes h1(x)=h1(x)+m1(x)=h(x)+m1(x)=132x4+2x3+171x2+121x+159h'_1(x)=h_1(x)+m_1(x)=h(x)+m_1(x)=132x^4+2x^3+171x^2+121x+159 and h2(x)=h2(x)+m2(x)=h(x)+m2(x)=2x4+171x2+70x+161h'_2(x)=h_2(x)+m_2(x)=h(x)+m_2(x)=2x^4+171x^2+70x+161.

41322)4-1-3-2-2) The Prover computes F(x)=G(x,h1(α1x),h2(α2x),...,ht(αtx))F'(x)=G(x,h'_1(\alpha_1x),h'_2(\alpha_2x),...,h'_t(\alpha_tx)) and q1(x)=F(x)ZK(x)q_1(x)=\frac{F'(x)}{\mathbf{Z_K}(x)} then the Prover sends {mi}i\{m_i\}_i, {ri}i\{r_i\}_i and q1q_1. Here F(x)=G(x,h1(48x),h2(x))=(h1(48x)ωh2(x))(xγ2)=64x5+61x4+92x3+117x2+120x+89F'(x)=G(x,h'_1(48x),h'_2(x))=(h'_1(48x)-\omega h'_2(x))(x-\gamma^2)=64x^5+61x^4+92x^3+117x^2+120x+89 and then q1(x)=F(x)ZK(x)=64x2+61x+92q_1(x)=\frac{F'(x)}{\mathbf{Z_K}(x)}=64x^2+61x+92. The Prover sends m1(x)=132x4+2x3+49x+179m_1(x)=132x^4+2x^3+49x+179, m2(x)=2x4+179xm_2(x)=2x^4+179x, r1(x)=2+xr_1(x)=2+x , r2(x)=2xr_2(x)=2x and q1(x)=64x2+61x+92q_1(x)=64x^2+61x+92 to the Verifier.

41323)4-1-3-2-3) The Verifier derives hi=hi+mih'_i=h_i+m_i through additive homomorphism. Then samples β1\beta_1, β2\beta_2 and cc of FKF^{*}-\mathbf{K} and sends cc to the Prover. Suppose β1=65\beta_1=65, β2=21\beta_2=21 and c=171c=171. The Verifier sends c=171c=171 to the Prover.

41324)4-1-3-2-4) The Prover computes q2=r1+cr2+...+ct1rtq_2=r_1+cr_2+...+c^{t-1}r_t and the Verifier derives concrete oracle q2q_2 through additive homomorphism. Here, the Prover computes q2(x)=r1(x)+cr2(x)=2+x+171(2x)=162x+2q_2(x)=r_1(x)+cr_2(x)=2+x+171(2x)=162x+2.

41325)4-1-3-2-5) Let M(x)=m1(α1x)+cm2(α2x)+...+ct1mt(αtx)M(x)=m_1(\alpha_1 x)+cm_2(\alpha_2 x)+...+c^{t-1}m_t(\alpha_t x). The Verifier computes ZK(β1)\mathbf{Z_K}(\beta_1), ZK(β2)\mathbf{Z_K}(\beta_2), queries q1(β1)q_1(\beta_1)and q2(β2)q_2(\beta_2) and for i{1,2,..,t}i\in \{1,2,..,t\}, queries hi(αiβ1)h'_i(\alpha_i\beta_1) and mi(αiβ2)m_i(\alpha_i\beta_2)to compute F(β1)F'(\beta_1) and M(β2)M(\beta_2). The Verifier asserts two identities M(β2)q2(β2)ZK(β2)=0M(\beta_2)-q_2(\beta_2)\mathbf{Z_K}(\beta_2)=0 and F(β1)q1(β1)ZK(β1)=0F'(\beta_1)-q_1(\beta_1)\mathbf{Z_K}(\beta_1)=0. Here, M(x)=m1(α1x)+cm2(α2x)=162x4+2x3+19x+179M(x)=m_1(\alpha_1 x)+cm_2(\alpha_2 x)=162x^4+2x^3+19x+179. The Verifier computes ZK(β1)=ZK(65)=47\mathbf{Z_K}(\beta_1)=\mathbf{Z_K}(65)=47 and ZK(β2)=ZK(21)=29\mathbf{Z_K}(\beta_2)=\mathbf{Z_K}(21)=29 and queries q1(β1)=61q_1(\beta_1)=61 and q2(β2)=146q_2(\beta_2)=146. Also queries values h1(α1β1)=h1(γ×65)=h1(43)=80h'_1(\alpha_1\beta_1)=h'_1(\gamma\times 65)=h'_1(43)=80 , h2(α2β1)=h2(65)=118h'_2(\alpha_2\beta_1)=h'_2(65)=118, m1(α1β2)=m1(γ×21)=m1(103)=124m_1(\alpha_1\beta_2)=m_1(\gamma\times 21)=m_1(103)=124 and m2(α2β2)=m2(21)=132m_2(\alpha_2\beta_2)=m_2(21)=132. Then checks M(β2)q2(β2)ZK(β2)=0M(\beta_2)-q_2(\beta_2)\mathbf{Z_K}(\beta_2)=0 , that means 71146×29=71+110=1810(mod181)71-146\times 29=71+110=181\equiv 0\hspace{1mm}(\textrm{mod}\hspace{1mm}181), and F(β1)q1(β1)ZK(β1)=0F'(\beta_1)-q_1(\beta_1)\mathbf{Z_K}(\beta_1)=0, that means 15261×47=152+290(mod181)152-61\times 47=152+29\equiv 0\hspace{1mm}(\textrm{mod}\hspace{1mm}181).

4133)4-1-3-3) The Verifier outputs accept if all checks pass, otherwise reject. Here, outputs accept.

414)4-1-4) The Prover and the Verifier run SubsetoverK\red{Subset\hspace{1mm}over\hspace{1mm}\mathbf{K}} between rowArow_A and hh.

415)4-1-5) The Prover and the Verifier run DiscretelogComparison\red{Discrete-log\hspace{1mm} Comparison} between rowArow_A and colAcol_A as following: Let parameters (Δ,n=H)(\Delta, n = |\mathbf{H}|) such that ord(Δ)=2nord(\Delta) = 2n and Δ2=ω\Delta^2=\omega. Here, ω=59\omega=59, Δ=125\Delta=125 and n=5n=5.

4151)4-1-5-1) The Prover interpolates polynomial ss so that agrees with rowAcolA\frac{row_A}{col_A} on K\mathbf{K}. Here, s(1)=rowA(1)colA(1)=4259=42×135=59s(1)=\frac{row_A(1)}{col_A(1)}=\frac{42}{59}=42\times 135=59, s(48)=rowA(48)colA(48)=1251=125s(48)=\frac{row_A(48)}{col_A(48)}=\frac{125}{1}=125 and s(132)=rowA(132)colA(132)=135125=42×135=59s(132)=\frac{row_A(132)}{col_A(132)}=\frac{135}{125}=42\times 135=59. Therefore, s(x)=59L1(x)+125L2(x)+59L3(x)=151x2+8x+81s(x)=59L_1(x)+125L_2(x)+59L_3(x)=151x^2+8x+81.

4152)4-1-5-2) For b{rowA,colA,s}b\in\{row_A, col_A, s\}, the Prover interpolates polynomial bb' so that for all kKk\in \mathbf {K}, b(k)=Δlogωb(k)b'(k)=\Delta^{\log_{\omega}^{b(k)}}.

Here, if b=rowAb=row_A, rowA(k)=ΔlogωrowA(k)=125log59rowA(k)row'_A(k)=\Delta^{\log_{\omega}^{row_A(k)}}=125^{\log_{59}^{row_A(k)}}that means rowA(1)=125log5942=125259(mod181)row'_A(1)=125^{\log_{59}^{42}}=125^2\equiv 59\hspace{1mm}(\textrm{mod}\hspace{1mm}181), rowA(48)=125log59125=1253135(mod181)row'_A(48)=125^{\log_{59}^{125}}=125^3\equiv 135\hspace{1mm}(\textrm{mod}\hspace{1mm}181) and rowA(132)=125log59135=125442(mod181)row'_A(132)=125^{\log_{59}^{135}}=125^4\equiv 42\hspace{1mm}(\textrm{mod}\hspace{1mm}181). Therefore rowA(x)=59L1(x)+135L2(x)+42L3(x)=130x2+86x+24row'_A(x)=59L_1(x)+135L_2(x)+42L_3(x)=130x^2+86x+24.

if b=colAb=col_A, colA(k)=ΔlogωcolA(k)=125log59colA(k)col'_A(k)=\Delta^{\log_{\omega}^{col_A(k)}}=125^{\log_{59}^{col_A(k)}}that means colA(1)=125log5959=1251125(mod181)col'_A(1)=125^{\log_{59}^{59}}=125^1\equiv 125\hspace{1mm}(\textrm{mod}\hspace{1mm}181), colA(48)=125log591=12551(mod181)col'_A(48)=125^{\log_{59}^{1}}=125^5\equiv 1\hspace{1mm}(\textrm{mod}\hspace{1mm}181) and colA(132)=125log59125=1253135(mod181)col'_A(132)=125^{\log_{59}^{125}}=125^3\equiv 135\hspace{1mm}(\textrm{mod}\hspace{1mm}181). Therefore colA(x)=125L1(x)+L2(x)+135L3(x)=85x2+134x+87col'_A(x)=125L_1(x)+L_2(x)+135L_3(x)=85x^2+134x+87.

if b=sb=s, s(k)=Δlogωs(k)=125log59s(k)s'(k)=\Delta^{\log_{\omega}^{s(k)}}=125^{\log_{59}^{s(k)}}that means s(1)=125log5959=1251125(mod181)s'(1)=125^{\log_{59}^{59}}=125^1\equiv 125\hspace{1mm}(\textrm{mod}\hspace{1mm}181),

References:

[1] Boneh, Dan, Wilson Nguyen, and Alex Ozdemir. "Efficient functional commitments: How to commit to a private function." Cryptology ePrint Archive (2021).‏

[2] de Castro, Leo, and Chris Peikert. "Functional commitments for all functions, with transparent setup and from SIS." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer Nature Switzerland, 2023.‏

[3] Gabizon, Ariel, and Zachary J. Williamson. "plookup: A simplified polynomial protocol for lookup tables." Cryptology ePrint Archive (2020).‏

[4] Wee, Hoeteck, and David J. Wu. "Lattice-based functional commitments: Fast verification and cryptanalysis." International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer Nature Singapore, 2023.‏

Last updated