At we see, the matrices A and B are 2−SLT and matrix C is 2−Diag. Also AzoBz=Cz.
We 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=2ng=6 where t=ni+1=2 with generator γ=gmp−1=230≡49(mod181). Therefore,K={1,γ,γ2,...,γ5}={1,49,48,180,132,133}.
1- The Prover Selects s=(s1,...,ssAHP(0)) of random space R.
2- The Prover calculates O=Enc(mf=(A,B,C)) as encoded index as following:.
First, calculates the polynomial PFRrowA(x). Since matrix A has three non-zero entries that the first of them is in the second row, so c0=2 and PFRrowA(γ0)=ω2 , note that rows numbered of zero, the second is in the third row, so c1=3 and PFRrowA(γ1)=ω3 and the third is in the fourth row, so c2=4 and PFRrowA(γ2)=ω4. Note that to construct all three polynomials, we read the entries in the matrix in row or column order. Here they are read in row order.
According to the values defined for γ and ω, we have PFRrowA(1)=42, PFRrowA(43)=125 and PFRrowA(39)=135. Therefore based on Lagrange polynomials, have PFRrowA(x)=∑i=13yiLi(x), so PFRrowA(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 PFRrowA(x)=77x2+109x+37.
Now, calculates PFRcolA(x). Since matrix A has three non-zero entries that the first of them is in the first column, so r0=1 and PFRcolA(γ0)=ω1 , note that columns numbered of zero, the second is in the zero column, so r1=0 and PFRcolA(γ1)=ω0 and the third is in the third column, so r2=3 and PFRcolA(γ2)=ω3. Therefore PFRcolA(1)=59, PFRcolA(43)=1 and PFRcolA(39)=125. So PFRcolA(x)=59L1(x)+L2(x)+125L3(x)=109x2+81x+50.
3- The Prover calculates commitment by using of KZG commitment scheme as following:
Now, calculates PFRvalA(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, PFRvalA(x)=L1(x)+L2(x)+L3(x)=1.
Therefore, the matrix A is encoded by PFRrowA(x)=77x2+109x+37, PFRcolA(x)=109x2+81x+50 and PFRvalA(x)=1.
Now, encodes the matrix B. First, calculates 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 PFRrowB(γ1)=PFRrowB(γ2)=ω3 and the fourth is in the fourth row, so c3=4 and PFRrowB(γ3)=ω4. Therefore, PFRrowB(1)=42, PFRrowB(43)=125, PFRrowB(39)=125 and PFRrowB(48)=135. So PFRrowB(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 PFRrowB(x)=76x3+35x2+174x+119.
Now, calculates PFRcolB(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 PFRcolB(γ0)=PFRcolB(γ1)=PFRcolB(γ3)=ω0 and the third is in the second column, so r2=2 and PFRcolB(γ2)=ω2 . Therefore PFRcolB(1)=1, PFRcolB(43)=1, PFRcolB(39)=42and PFRcolB(48)=1. So PFRcolB(x)=L1(x)+L2(x)+42L3(x)+L4(x)=47x3+20x2+106x+9.
Now, calculates PFRvalB(x). Since matrix B has four non-zero entries that value of them are 5, 11, 1 and 26, respectively. Therefore v0=v1=v2=1PFRvalB(γ0)=5, PFRvalB(γ1)=11, PFRvalB(γ2)=1and PFRvalB(γ3)=26. So, PFRvalB(1)=5, PFRvalB(43)=11, PFRvalB(39)=1and PFRvalB(48)=26. Therefore, PFRvalB(x)=5L1(x)+11L2(x)+L3(x)+26L4(x)=177x3+148x2+42.
Therefore, the matrix B is encoded by PFRrowB(x)=76x3+35x2+174x+119, PFRcolB(x)=47x3+20x2+106x+9 and PFRvalB(x)=177x3+148x2+42.
Now, calculates polynomial PFRrowC(x). In a similar way, Since matrix C has three non-zero entries that are in the third, fourth and fifth rows, therefore PFRrowC(γ0)=ω2 , PFRrowC(γ1)=ω3 and PFRrowC(γ2)=ω4. Then PFRrowC(1)=42 , PFRrowC(43)=125 and PFRrowC(39)=135. SoPFRrowC(x)=42L1(x)+125L2(x)+135L3(x), therefore PFRrowC(x)=77x2+109x+37.
Now, since C is a diagonal matrix, polynomials PFRrowC(x) and PFRcolC(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, PFRvalC(x)=L1(x)+L2(x)+L3(x)=1.
Therefore, the matrix C is encoded by PFRrowC(x)=77x2+109x+37, PFRcolC(x)=77x2+109x+37 and PFRvalC(x)=1. Therefore, encoding of mf=(A,B,C) calculates as following:OPFR=(37,109,77,0,0,0,0,0,0,50,81,109,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,119,174,35,76,0,0,0,0,0,9,106,20,47,0,0,0,0,0,42,0,148,177,0,0,0,0,0,37,109,77,0,0,0,0,0,0,37,109,77,0,0,0,0,0,0,37,109,77,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0)
ComT=∑i=0degTaigτi=∑i=0degTaick(i) where ai is coefficient of xi in polynomial T(x).
PFRCom3=, PFRCom4=, PFRCom5=, PFRCom6=, PFRCom7= and PFRCom8=.
4- The Prover sends PFRCom= to the Verifier.
Commit(ck,mf=(A,B,C),s∈R):
1 - The Prover Selects s=(s1,...,ssAHP(0)) of random space R.
2- The Prover calculates OAHP=Enc(mf=(A,B,C)) as encoded index as following:
The polynomial AHProwA:K={1,49,48,180,132,133}→H={1,59,42,125,135} with AHProwA(k=γi)=ωri for 1≤i≤∣∣A∣∣ , and otherwise AHProwA(k) returns an arbitrary element in H.
So AHProwA(k) on K is a polynomial so that AHProwA(1)=42 , AHProwA(49)=125, AHProwA(48)=135 and otherwise AHProwA(k) returns arbitrary elements of H, for example AHProwA(180)=125, AHProwA(132)=135, AHProwA(133)=1 Therefore, AHProwA(x)=∑i=16yiLi(x)=162x5+62x4+161x3+169x2+88x+124.
Also, AHPcolA:K={1,49,48,180,132,133}→H={1,59,42,125,135} with AHPcolA(k=γi)=ωci for 1≤i≤∣∣A∣∣ and otherwise AHPcolA(k) returns an arbitrary element in H.
So AHPcolA(k) on K is a polynomial so that AHPcolA(1)=59 , AHPcolA(49)=1, AHPcolA(48)=125 and otherwise AHPcolA(k) returns arbitrary elements of H, for example AHPcolA(180)=125, AHPcolA(132)=135 and AHPcolA(133)=1. Therefore, AHPcolA(x)=∑i=16yiLi(x)=128x5+150x4+32x3+109x2+169x+14
and , AHPvalA:K={1,49,48,180,132,133}→H={1,59,42,125,135} with AHPvalA(k=γi)=uH(AHProwA(k),AHProwA(k))uH(AHPcolA(k),AHPcolA(k))vi for 1≤i≤∣∣A∣∣ where vi is value of ith nonzero entry and otherwise AHPvalA(k) returns zero. Note that based on definition of uH(x,y), for each x∈H, uH(x,x)=∣H∣x∣H∣−1=5x4. So AHPvalA(1)=(5AHProwA4(1))(5AHPcolA4(1))1=5×424×5×5941=1451≡5(mod181), AHPvalA(49)=(5AHProwA4(49))(5AHPcolA4(49))1=5×1254×5×141=1451≡5(mod181) , AHPvalA(48)=(5AHProwA4(48))(5AHPcolA4(48))1=5×1354×5×12541=481≡132(mod181) and AHPvalA(k)=0 for k∈K−{1,49,48}. Therefore AHPvalA(x)=∑i=16yiLi(x)=72x5+79x4+22x3+111x2+180x+84.
Now, AHProwA^, AHPcolA^ and AHPvalA^ are extensions of AHProwA, AHPcolA and AHPvalA so that are agree on K.
Similarly, AHProwB:K={1,49,48,180,132,133}→H={1,59,42,125,135} so that AHProwB(1)=42, AHProwB(49)=125, AHProwB(48)=125, AHProwB(180)=135 and for the rest values of K, AHProwB(k) returns arbitrary elements of H, for example AHProwB(132)=135 and AHProwB(133)=1. Therefore AHProwB(x)=∑i=16yiLi(x)=20x5+85x4+37x3+151x2+168x+124.
Also, AHPcolB:K={1,49,48,180,132,133}→H={1,59,42,125,135} so that AHPcolB(1)=1 , AHPcolB(49)=1, AHPcolB(48)=42, AHPcolB(180)=1 and for the rest values of K , AHPcolB(k) returns arbitrary elements of H, for example AHPcolB(132)=135 and AHPcolB(133)=1. Therefore AHPcolB(x)=∑i=16yiLi(x)=18x5+164x4+180x3+18x2+164x
and , AHPvalB:K={1,49,48,180,132,133}→H={1,59,42,125,135} so that AHPvalB(1)=(5AHProwB4(1))(5AHPcolB4(1))5=5×424×5×145=485≡117(mod181), AHPvalB(49)=(5AHProwB4(49))(5AHPcolB4(49))11=5×1254×5×1411=14511≡55(mod181) , AHPvalB(48)=(5AHProwB4(48))(5AHPcolB4(48))1=5×1254×5×4241=251≡29(mod181) , AHPvalB(180)=(5AHProwB4(180))(5AHPcolB4(180))26=5×1354×5×1426=2726≡68(mod181) and AHPvalB(k)=0 for k∈K−{1,49,48,180}. Therefore AHPvalB(x)=∑i=16yiLi(x)=86x5+53x4+34x3+55x2+176x+75.
Now, AHProwB^, AHPcolB^ and AHPvalB^ are extensions of AHProwB, AHPcolB and AHPvalB so that are agree on K.
Similarly, AHProwC:K={1,49,48,180,132,133}→H={1,59,42,125,135} so that AHProwC(1)=42, AHProwC(49)=125, AHProwC(48)=135 and for the rest values of K, AHProwC(k) returns arbitrary elements of H, for example AHProwC(180)=125, AHProwC(132)=135 and AHProwC(133)=1. Therefore AHProwC(x)=∑i=16yiLi(x)=162x5+62x4+161x3+169x2+88x+124.
Also, AHPcolC:K={1,49,48,180,132,133}→H={1,59,42,125,135} so that AHPcolC(1)=42 , AHPcolC(49)=125, AHPcolC(48)=135, AHPcolC(180)=125 and for the rest values of K , AHPcolC(k) returns arbitrary elements of H, for example AHPcolC(132)=135 and AHPcolC(133)=1. Therefore AHPcolC(x)=∑i=16yiLi(x)=162x5+62x4+161x3+169x2+88x+124.
and , AHPvalC:K={1,49,48,180,132,133}→H={1,59,42,125,135} so that AHPvalC(1)=(5AHProwC4(1))(5AHPcolC4(1))1=5×424×5×4241=271≡114(mod181), AHPvalC(49)=(5AHProwC4(49))(5AHPcolC4(49))1=5×1254×5×12541=1171≡82(mod181) , AHPvalC(48)=(5AHProwC4(48))(5AHPcolC4(48))1=5×1354×5×13541=1451≡5(mod181) and AHPvalC(k)=0 for k∈K−{1,49,48}. Therefore AHPvalC(x)=∑i=16yiLi(x)=65x5+61x4+157x3+53x2+16x+124.
Now, AHProwC^, AHPcolC^ and AHPvalC^ are extensions of AHProwC, AHPcolC and AHPvalC so that are agree on K.