We now review the three main elements in the tuple.
Example
40380552: 02f407b3 mul a1,s0,5
4038055e: 004c addi a1,s0,11
40380552: 02f407b3 mul a1,s0,26
LD R1, 4
Mul R1, 5 => Gate 1, p=181
Add R1, 11 => Gate 2, p=181
Mul R1, 26 (== Div R1, 7) => Gate 3, p=181
Therefore
and similarly
D- Therefore, output
.................
AHP
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.
In this page, we will review function-hiding functional commitment zero-knowledge proof (ZKP) scheme. This scheme is a tuple (Setup,,Commit,Eval)that utilizes the following three protocols:
PC=(PC.Setup,PC.Commit,PC.Eval,PC.Check),
A proof of function relation (PFR) π=(Pf,Vf,kf,sf,df)contains kfwehre is the number of rounds, sf:N→N where that sf(i) is the number polynomials that the Prover Pfsends to the Verifier Vf in round i and df:N3→N so that df(N,i,j) is the degree bound for jthpolynomial in round . Let N be the maximum supported index size.
An algebric holographic proof AHP=(EncAHP,PAHP,VAHP,kAHP,sAHP,dAHP) contains kAHP where is the number of rounds, sAHP:N→N so that sAHP(i) is the number polynomials that the Prover PAHPsends to the Verifier VAHP in round i and dAHP:N3→N so that dAHP(N,i,j) is the degree bound for jth polynomial in round i.
Note that sAHP(0)=sf(0) and for all i∈[sAHP(0)], dAHP(N,0,i)=df(N,0,i).
Setup(1λ,N): The is function creates output pp=PC.Commit(1λ,d) where λ is security parameter and d={dAHP(N,i,j)}i∈[kAHP]⋃{0},j∈[sAHP(i)]}⋃{df(N,i,j)}i∈[kf],j∈[sf(i)].
For example, if polynomial commitment scheme KZG is used, pp=(g,gd,gd2,...,gdl)where g is a generator of field F with large prime order p such that log(p)=Ω(λ) and l is maximum degree of polynomials that want to commit them.
Commit(pp,i∈If,r∈R=RsAHP(0)):
This function contains the following steps:
A- Parse r=(r1,...,rsAHP(0)) and pp=(ck,vk).
B- Set o=EncAHP(i).
Note that If is a functional set that contains triple matrices i=(A,B,C)∈(Fn×n)3 so that for all input x∈X, there exists a unique y∈Y and a witness (intermediate) ω∈W such that AzoBz=Cz where z=(x,w,y).
Note that a triple of matrices (A,B,C)∈(Fn×n)3 is a functional triple if and only if A and B are t−strictly lower triangular matrices (t−SLT) and C is t-diagonal matrix (t−Diag). Here, t is the size of the input.
Note that the Prover obtains t−SLT matrices A, B and t−Diag matrix C for the arithmetic circuit based on the following construction:
1- Initialize three zero square matrices A,B,C over F of order ng+ni+1 where ng is the number of gates and ni is the number of inputs.
Here, the gate i is corresponding to tuple (li,ri,si) where li and ri are left and right input wire indices, respectively and si is gate selector, addition or multiplication. Also in the following construction ni is the number of inputs.
2- For i=0..,ng−1:a)C1+ni+i,1+ni+i=1b) if si is addition
- A1+ni+i,0=1
- B1+ni+i,li=1 ( if the left input is a number, value of input is placed )
- B1+ni+i,ri=1 ( if the right input is a number, value of input is placed)
c) If si is multiplication
- A1+ni+i,li=1 ( if the left input is a number, value of input is placed)
- B1+ni+i,ri=1 ( if the right input is a number, value of input is placed)
3- Outputs matrices A,B and C.
Note that the Prover encodes each matrix A,B and C by three polynomials such that encodes matrix M, M∈{A,B,C}, by polynomials rowM(x), colM(x) and valM(x) so that rowM(γi)=ωri, colM(γi)=ωci and valM(γi)=vi for i∈{0,1,2,..,m−1} where γ is a generator of multiplicative subgroup Kof F of order m (K=<γ> and ∣K∣=m) and ω is a generator of multiplicative subgroup H of F of order n (H=<ω> and ∣H∣=n). Also m is maximum of the number of nonzero entries in the matrix M. n is the order of the matrix. Also ri,ci∈{0,1,...,n−1} and vi∈F are row number, column number and value of ith nonzero entry, respectively. Therefore O=(rowA(x),colA(x),valA(x),rowB(x),colB(x),valB(x),rowC(x),colC(x),valC(x)).
C- For i∈sAHP(0), cO0,i=PC.Commit(ck,O[i],dAHP(N,0,i),rO0,i).
For example, if the polynomial commitment schemeKZG is used,
cO0,i=∏i∈{0,1,...,degO[i]}(gdi)ai where ai is coefficient of xi in polynomial O0,i.
We now review the last step for the commitment phase
D- Output c=(cO0,1,cO0,2,...,cO0,sAHP(0)).
Eval(PE(pp,i,r,x,y),VE(pp,c,x,y)). The Prover PE and the Verifier VE parse pp=(ck,vk).
. The Prover PE computes o=EncAHP(i).
. The Prover PE and the Verifier VE run polynomial interactive oracle proofs (piop) , AHP or PFR.
A- PFR commitment checking
The Prover Pf and the Verifier Vf run polynomial oracle proof PFR<Pf(O,,i),VfO()>. This polynomial oracle proof is described in Supplement1. Note that in this polynomial oracle proof, the Prover wants to prove three following claims:
1.O[1]=rowA(x) , O[2]=colA(x) andO[3]=valA(x)is encoding of a t−SLT matrix.
2.O[4]=rowB(x) , O[5]=colB(x) andO[6]=valB(x)is encoding of a t−SLT matrix.
3.O[7]=rowC(x) , O[8]=colC(x) andO[9]=valC(x)is encoding of a t−Diag matrix.
B- PFR andAHP proof generating and verifying
The Prover PAHP and the Verifier VAHP run polynomial oracle proof AHP<PAHP(i,(x,y),w),VAHPO((x,y))>. Note that in this polynomial oracle proof, by keeping the function (A,B,C) hidden, the Prover wants to prove that input x gives output y.
. For all i∈[kpiop] and j∈spiop(i) when Ppiop sends oracle polynomial oi,j . PE computes and sends coi,j=PC.Commit(ck,oi,j,dpiop(N,i,j),roi,j)
. When Vpiop derives an oracle o that is a linear combination of other oracles, VE derives co through the PCS homomorphism. PE similarly derives the commitment randomness ro.
.When Vpiop queries oracle polynomial o with degree bound doat z∈F to receive y=o(z) :
.VE sends z.
.PE retrieves ro, then computes π=PC.Eval(ck,o,do,ro,z)and sends π and y=o(z).
For example, if polynomial commitment scheme KZG is used, π=gq(d) where q(x)=x−zo(x)−y.
.PE retrieves ro, then computes π=PC.Eval(ck,o,do,ro,z)and sends π and y=o(z).
For example, if polynomial commitment scheme KZG is
used, π=gq(d) where q(x)=x−zo(x)−y.
.VE retrieves co and asserts 1=PC.Check(vk,co,do,z,y,π).
For example, if polynomial commitment scheme KZG is used, π check as following:
e(gyco,g)=e(π,gzgd) , e(go(d)−y,g)=e(gq(d),gd−z),
e(g,g)o(d)−y=e(g,g)q(d)(d−z) and o(d)−y=q(d)(d−z).
Supplement1
polyIOP PFR includes:
1)To prove strictly lower triangularity of the matrices A and B must prove that
logωrowM(γi)>logωcolM(γi) for i∈{0,1,..,m−1}and M∈{A,B}. This does by
Discrete−logcomparisonprotocol.
2) To prove the first t rows of A and B are all zeros must prove that
rowM(K)⊆{ωt,ωt+1,...,ωn−1}. This does by subsetoverKprotocol.
3) To prove the diagonality of the matrix C must prove that seqK(rowC)=seqK(colC)where seqK(h)=(h(k):k∈K). This does by Geometricsequence and zerooverKprotocols.
4) To prove the first t rows of C are all zeros must prove that there is a vector v∈(F∗)n−t so that seqK(valC)=v∣∣0 . This does by Geometricsequence and zerooverKprotocols.
3 and 4 result that all the non-zero entries of the matrix C are in the positions (ωt,ωt),(ωt+1,ωt+1),...,(ωn,ωn).
Suppose d=111213119. Run PC.Setup(1λ,d) based on KZG as following:
PC.Setup(1λ,d) outputs pp=(g,gd,gd2,...,gdl) where l is the maximum degree of polynomials that are used in scheme .
Let the computation be done in F of order p=181. A generator of F is g=2, therefore
pp=(g,gd,gd2,...,gdl)=(2,2111213119,...,21112131198). Because ord(2)=180, then
2111213119=(2180)6178502119≡2119≡66(mod181). Similarly, the rest of entries are computed and as a result pp=(2,66,83,91,96,24,2,66,83).
We consider z=(1,x,w1,w2,y) where w1=5x, w2=w1+11 and y=7w2. Therefore with input x=4, z=(1,4,20,31,82). Note that the inverse of number a in this field is ap−2(modp) , so 7−1≡26(mod181).
It can be seen that matrices A and B are 2−SLT and matrix C is 2−Diag.
Also AzoBz=00203182=Cz.
To encode matrix A, consider multiplicative subgroup H of order n=ng+ni+1=5 with generator
ω=236≡59(mod181). Note that if g is a generator of field F of order p, then gnp−1is a generator of a multiplicative subgroup of it of order n. Therefore H={1,ω,ω2,ω3,ω4}={1,59,42,125,135}.
Also, consider multiplicative subgroup K of order m=2n2−n−2t2−t=9 where t=ni+1 with generator γ=gmp−1=220≡43(mod181). Therefore K={1,γ,γ2,...,γ8}={1,43,39,48,73,62,132,65,80}.
First, build the polynomial rowA(x). Since matrix A has three non-zero entries the first of them is in the second row, so c0=2 and rowA(γ0)=ω2 , note that rows numbered of zero, the second is in the third row, so c1=3 and rowA(γ1)=ω3 and the third is in the fourth row, so c2=4 and rowA(γ2)=ω4.
According to the values defined for γ and ω, we have rowA(1)=42, rowA(43)=125 and rowA(39)=135. Therefore based on Lagrange polynomials, have rowA(x)=∑i=13yiLi(x), sorowA(x)=42L1(x)+125L2(x)+135L3(x), where L1(x)=(1−43)(1−39)(x−43)(x−39)=(−42)(−38)(x−43)(x−39). Now, since −42≡139(mod181), −38≡143(mod181), −43≡138(mod181)and −39≡142(mod181), therefore L1(x)=(139)(143)(x+138)(x+142)and since (139)(143)≡148(mod181)and 148−1≡170(mod181), have L1(x)=170(x+138)(x+142)=170x2+178x+15. We get in a similar way that L2(x)=167x2+17x+178 and L3(x)=25x2+167x+170. Therefore rowA(x)=77x2+109x+37.
Now, we obtain colA(x). Since matrix A has three non-zero entries the first of them is in the first column, so r0=1 and colA(γ0)=ω1 , note that columns numbered of zero, the second is in the zero column, so r1=0 and colA(γ1)=ω0 and the third is in the third column, so r2=3 and colA(γ2)=ω3. Therefore colA(1)=59, colA(43)=1 and colA(39)=125. So colA(x)=59L1(x)+L2(x)+125L3(x)=109x2+81x+50.
Now, we obtain valA(x). Since matrix A has three non-zero entries such that the value of all of them is one, therefore v0=v1=v2=1. So, valA(x)=L1(x)+L2(x)+L3(x)=1.
Therefore, the matrix A encodes by rowA(x)=77x2+109x+37, colA(x)=109x2+81x+50 and valA(x)=1.
Now, encode the matrix B. First, build the polynomial rowB(x). Since matrix B has four non-zero entries such that the first of them is in the second row, so c0=2 and rowB(γ0)=ω2 . The second and the third are in the third row, so c1=c2=3 and rowB(γ1)=rowB(γ2)=ω3 and the fourth is in the fourth row, so c3=4 and rowB(γ3)=ω4. Therefore, rowB(1)=42, rowB(43)=125, rowB(39)=125 and rowB(48)=135. So rowB(x)=42L1(x)+125L2(x)+125L3(x)+135L4(x) where L1(x)=(1−43)(1−39)(1−48)(x−43)(x−39)(x−48)=(139)(143)(134)(x+138)(x+142)(x+133)=103(x+138)(x+142)(x+133). Since 103−1≡58(mod181), so L1(x)=58(x+138)(x+142)(x+133)=58x3+62x2+116x+127. We get in a similar way that L2(x)=39x3+7x2+19x+116, L3(x)=138x3+155x2+7x+62 and L4(x)=127x3+138x2+39x+58. Therefore rowB(x)=76x3+35x2+174x+119.
Now, we obtain colB(x). Since matrix B has four non-zero entries that the first, second and fourth of them are in zero column, so r0=r1=r3=0 and colB(γ0)=colB(γ1)=colB(γ3)=ω0 and the third is in the second column, so r2=2 and colB(γ2)=ω2 . Therefore colB(1)=1, colB(43)=1, colB(39)=42and colB(48)=1. So colB(x)=L1(x)+L2(x)+42L3(x)+L4(x)=47x3+20x2+106x+9.
Now, we obtain valB(x). Since matrix B has four non-zero entries that value of them are 5, 11, 1 and 26, respectively. Therefore v0=v1=v2=1valB(γ0)=5, valB(γ1)=11, valB(γ2)=1and valB(γ3)=26. So, valB(1)=5, valB(43)=11, valB(39)=1and valB(48)=26. Therefore valB(x)=5L1(x)+11L2(x)+L3(x)+26L4(x)=177x3+148x2+42.
Therefore, the matrix B encodes by rowB(x)=76x3+35x2+174x+119, colB(x)=47x3+20x2+106x+9 and valB(x)=177x3+148x2+42.
Now, build polynomial rowC(x). In a similar way, Since matrix C has three non-zero entries that are in the third, fourth and fifth rows, therefore rowC(γ0)=ω2 , rowC(γ1)=ω3 and rowC(γ2)=ω4. Then rowC(1)=42 , rowC(43)=125 and rowC(39)=135. SorowC(x)=42L1(x)+125L2(x)+135L3(x), therefore rowC(x)=77x2+109x+37.
Now, since C is a diagonal matrix, polynomials rowC(x) and colC(x)are equal. Also, since the matrix C has three non-zero entries such that the value of all of them is one, therefore v0=v1=v2=1. So, valC(x)=L1(x)+L2(x)+L3(x)=1.
Therefore, the matrix C encodes by rowC(x)=77x2+109x+37, colC(x)=77x2+109x+37 and valC(x)=1.
Therefore encoding of i=(A,B,C) obtain as following:
