4-1- PFR Verify
Verify(F,H,K,comPFR,πPFR): This function outputs 1, if the following equations satisfies.
1) h(γpi)=ai for i∈{1,2,...,v} where πPFR1=h(x).
2) M(β2)−q2(β2)ZK(β2)=0
4-2- AHP Verify
Verify(F,H,K,ComAHP,ΠAHP,X,Y): This function outputs 1 if
1- The following four equations satisfies for random value β3∈F chosen by the Verifier.
h3(β3)vK(β3)=a(β3)−b(β3)(β3g3(β3)+∣K∣σ3)(1)
r(α,β2)σ3=h2(β2)vH(β2)+β2g2(β2)+∣H∣σ2(2)
s(β1)+r(α,β1)(∑M∈{A,B,C}ηMz^M(β1))−σ2z^(β1)=h1(β1)vH(β1)+β1g1(β1)+∣H∣σ1(3)
z^A(β1)z^B(β1)−z^C(β1)=h0(β1)vH(β1)(4)
where a(x)=∑M∈{A,B,C}ηMvH(β2)vH(β1)valM′^(x)∏N∈{A,B,C}−{M}(β2−rowN′^(x))(β1−colN′^(x))and b(x)=∏M∈{A,B,C}(β2−rowM′^(x))(β1−colM′^(x)).
2- The output result in following steps is 1.
2-1- The Verifier chooses random values ηw^, ηz^A, ηz^B, ηz^C, ηz^, ηh0, ηs, ηg1, ηh1, ηg2, ηh2, ηg3 and ηh3 of F The Verifier can choose as following:
ηw^=hash(s(10)), ηz^A=hash(s(11)), ηz^B=hash(s(12)), ηz^C=hash(s(13)), ηh0=hash(s(14)), ηs=hash(s(15)), ηg1=hash(s(16)), ηh1=hash(s(17)), ηg2=hash(s(18)), ηh2=hash(s(19)), ηg3=hash(s(20)), ηh3=hash(s(21)).
2-2- The Verifier builds the linear combinationp(x)=ηw^w^(x)+ηz^Az^A(x)+ηz^Bz^B(x)+ηz^Cz^C(x)+ηh0h0(x)+ηss(x)+ηg1g1(x)
+ηh1h1(x)+ηg2g2(x)+ηh2h2(x)+ηg3g3(x)+ηh3h3(x).
2-3- The Verifier derives commitment of p(x), Comp, by using polynomial commitment scheme homomorphism.
For example, if polynomial commitment scheme KZG is used, then Comp=(ComAHPX1)ηw^(ComAHPX2)ηz^A(ComAHPX3)ηz^B(ComAHPX4)ηz^C(ComAHPX5)ηh0(ComAHPX6)ηs(ComAHPX7)ηg1(ComAHPX8)ηh1(ComAHPX9)ηg2(ComAHPX10)ηh2(ComAHPX11)ηg3(ComAHPX12)ηh3.
2-4- The Verifier chooses random z∈F and queries p(z). Also, can select as z=hash(s(22))).
2-5- The Verifier computes result=PC.Check(vk,Comp,z,y′=πAHP16,πAHP17).
For example, if polynomial commitment scheme KZG is used, then the following equation checks:
e(gy′Comp,g)=e(πAHP17,gzvk)
4-3- Example
4-3-1- PFR Verify
Verify(F,H,K,comPFR,πPFR):
1) The Verifier checks h(γp1)=h(γ0)=a1=ω2 and h(γp2)=h(γ3)=a2=0. Here, the Verifier checks h(1)=42 and h(48)=0.
2) M(β2)−q2(β2)ZK(β2)=0 , that means 36−30×146=36−36≡0(mod181), and F′(β1)−q1(β1)ZK(β1)=0, that means 0−86×0≡0(mod181).
4-3-2- AHP Verify
Verify(F,H,K,ComAHP,ΠAHP,x=4,y=82) :
Since h3(β3)=h3(5)=170 and vK(β3)=vK(5)=134, therefore, the left of equation (1) is h3(β3)vK(β3)=155 . Also, since a(β3)=a(5)=17, b(β3)=b(5)=32 and β3g3(β3)+∣K∣σ3=7, therefore, the right of the equation (1) is a(β3)−b(β3)(σ3g3(β3)+∣K∣σ3)=155. So, the equation (1) is established.
Since r(α,β2)=α−β2α5−β25=10−80105−805=142, σ3=84, therefore, the left of equation (2) is r(α,β2)σ3=163 and since h2(β2)=h2(80)=42, vH(β2)=vH(80)=72, β2g2(β2)+∣H∣σ2=35, therefore, the right of equation (2) is h2(β2)vH+β2g2(β2)+∣H∣σ2=163. So, equation (2) is established.
Since s(β1)=s(22)=138, r(α,β1)=130, ∑M∈{A,B,C}ηMz^M(β1)=121, z^(β1)=53, σ2=70, therefore, the left of the equation (3) is s(β1)+r(α,β1)(∑M∈{A,B,C}ηMz^M(β1))−σ2z^(β1)=31. Also since h1(β1)=h1(22)=94, vH(β1)=vH(22)=18, g1(β1)=g1(22)=100, σ1=62, therefore the right of the equation (3) is h1(β1)vH(β1)+β1g1(β1)+∣H∣σ1=31. So, the equation (3) is established.
Since z^A(β1)=z^A(22)=140, z^B(β1)=z^B(22)=115, z^C(β1)=z^C(22)=125, therefore, the left of the equation (4) is z^A(β1)z^B(β1)−z^C(β1)=47. Also since h0(β1)=h0(22)=73 and vH(β1)=vH(22)=18, therefore the right of the equation (4) is h0(β1)vH(β1)=47. So the equation (4) is established.
2- The output result in following steps is 1.
2-1- The Verifier chooses random values ηw^, ηz^A, ηz^B, ηz^C, ηh0, ηs, ηg1, ηh1, ηg2, ηh2, ηg3 and ηh3 of F For example, ηw^=1, ηz^A=4, ηz^B=10, ηz^C=8, ηh0=32, ηs=45, ηg1=92, ηh1=11, ηg2=1, ηh2=5, ηg3=25 and ηh3=63.
2-2- The Verifier builds the linear combinationp(x)=ηw^w^(x)+ηz^Az^A(x)+ηz^Bz^B(x)+ηz^Cz^C(x)+ηh0h0(x)+ηss(x)+ηg1g1(x)
+ηh1h1(x)+ηg2g2(x)+ηh2h2(x)+ηg3g3(x)+ηh3h3(x).
The Verifier obtainsp(x)=134x47+34x46+70x45+48x44+169x43+162x42+106x41+43x40+97x39+45x38+11x37+84x36+16x35+145x34+161x33+84x32+147x31+166x30+97x29+18x28+146x27+158x26+101x25+119x24+118x23+100x22+35x21+41x20+60x19+161x18+145x17+2x16+121x15+152x14+157x13+69x12+5x11+45x10+144x9+81x8+43x7+146x6+98x5+99x4+137x3+116x2+162x+25
2-3- The Verifier derives commitment of p(x), Comp, by using polynomial commitment scheme homomorphism.
For example, if polynomial commitment scheme KZG is used, then Comp=(ComAHPx1)ηw^(ComAHPx2)ηz^A(ComAHPx3)ηz^B(ComAHPx4)ηz^C(ComAHPx6)ηh0(ComAHPx7)ηs =(ComAHPx1)ηw^(ComAHPx2)ηz^A(ComAHPx3)ηz^B(ComAHPx4)ηz^C(ComAHPx5)ηh0(ComAHPx6)ηs(ComAHPx7)ηg1(ComAHPx8)ηh1(ComAHPx9)ηg2(ComAHPx10)ηh2(ComAHPx11)ηg3(ComAHPx12)ηh3=5614844410128663262451489233111391545552511263=152
2-4- The Verifier chooses random z∈F and queries p(z). For example, z=2.
2-5- The Verifier computes result=PC.Check(vk,Comp,z,y′=πAHP16,πAHP17).
For example, if polynomial commitment scheme KZG is used, then the following equation checks:
e(gy′Comp,g)=e(πAHP17,gzvk)
where e(gy′Comp,g)=e(26152,2)=e(152×99,2)=e(25,2)=e(2132,2)=e(2,2)132 and e(πAHP17,gzvk)=e(67,2266)=e(67,66×136)=e(67,107)=e(2102,2117)=e(2,2)11934