4- Proof Verification Phase

In this section, we will review the proof verification phase of the protocol. This phase contains two parts; AHP and PFR. We also provide an example to clarify the method.

4-1- PFR Verify

Verify(F,H,K,comPFR,πPFR)Verify(\mathbb{F}, \mathbb{H}, \mathbb{K}, com_{PFR},\pi_{PFR}): This function outputs 11, if the following equations satisfies.

1)1) h(γpi)=aih(\gamma^{p_i})=a_i for i{1,2,...,v}i\in \{1,2,...,v\} where πPFR1=h(x)\pi_{PFR_1}=h(x).

2)2) M(β2)q2(β2)ZK(β2)=0M(\beta_2)-q_2(\beta_2)Z_{\mathbb{K}}(\beta_2)=0

4-2- AHP Verify

Verify(F,H,K,ComAHP,ΠAHP,X,Y)Verify(\mathbb{F}, \mathbb{H}, \mathbb{K}, Com_{AHP},\Pi_{AHP},X,Y): This function outputs 1 if

1- The following four equations satisfies for random value β3F\beta_3\in\mathbb{F} chosen by the Verifier.

h3(β3)vK(β3)=a(β3)b(β3)(β3g3(β3)+σ3K)(1)h_3(\beta_3)v_{\mathbb{K}}(\beta_3)=a(\beta_3)-b(\beta_3)(\beta_3g_3(\beta_3)+\frac{\sigma_3}{|\mathbb{K}|})\hspace{1cm}(1)

r(α,β2)σ3=h2(β2)vH(β2)+β2g2(β2)+σ2H(2)r(\alpha,\beta_2)\sigma_3=h_2(\beta_2)v_{\mathbb{H}}(\beta_2)+\beta_2g_2(\beta_2)+\frac{\sigma_2}{|\mathbb{H}|}\hspace{1.3cm}(2)

s(β1)+r(α,β1)(M{A,B,C}ηMz^M(β1))σ2z^(β1)=h1(β1)vH(β1)+β1g1(β1)+σ1H(3)s(\beta_1)+r(\alpha,\beta_1)(\sum_{M\in\{A,B,C\}}\eta_M\hat{z}_M(\beta_1))-\sigma_2\hat{z}(\beta_1)=h_1(\beta_1)v_{\mathbb{H}}(\beta_1)+\beta_1g_1(\beta_1)+\frac{\sigma_1}{|\mathbb{H}|}\hspace{2mm}(3)

z^A(β1)z^B(β1)z^C(β1)=h0(β1)vH(β1)(4)\hat{z}_A(\beta_1)\hat{z}_B(\beta_1)-\hat{z}_C(\beta_1)=h_0(\beta_1)v_{\mathbb{H}}(\beta_1)\hspace{2cm}(4)

where a(x)=M{A,B,C}ηMvH(β2)vH(β1)valM^(x)N{A,B,C}{M}(β2rowN^(x))(β1colN^(x))a(x)=\sum_{M\in \{A,B,C\}} \eta_M v_{\mathbb{H}}(\beta_2)v_{\mathbb{H}}(\beta_1)\hat{val'_M}(x)\prod_{N\in\{A,B,C\}-\{M\}}(\beta_2-\hat{row'_N}(x))(\beta_1-\hat{col'_N}(x))and b(x)=M{A,B,C}(β2rowM^(x))(β1colM^(x))b(x)=\prod_{M\in\{A,B,C\}}(\beta_2-\hat{row'_M}(x))(\beta_1-\hat{col'_M}(x)).

2- The output resultresult in following steps is 11.

2-1- The Verifier chooses random values ηw^\eta_{\hat{w}}, ηz^A\eta_{\hat{z}_A}, ηz^B\eta_{\hat{z}_B}, ηz^C\eta_{\hat{z}_C}, ηz^\eta_{\hat{z}}, ηh0\eta_{h_0}, ηs\eta_s, ηg1\eta_{g_1}, ηh1\eta_{h_1}, ηg2\eta_{g_2}, ηh2\eta_{h_2}, ηg3\eta_{g_3} and ηh3\eta_{h_3} of F\mathbb{F} The Verifier can choose as following: ηw^=hash(s(10))\eta_{\hat{w}}=hash(s(10)), ηz^A=hash(s(11))\eta_{\hat{z}_A}=hash(s(11)), ηz^B=hash(s(12))\eta_{\hat{z}_B}=hash(s(12)), ηz^C=hash(s(13))\eta_{\hat{z}_C}=hash(s(13)), ηh0=hash(s(14))\eta_{h_0}=hash(s(14)), ηs=hash(s(15))\eta_{s}=hash(s(15)), ηg1=hash(s(16))\eta_{g_1}=hash(s(16)), ηh1=hash(s(17))\eta_{h_1}=hash(s(17)), ηg2=hash(s(18))\eta_{g_2}=hash(s(18)), ηh2=hash(s(19))\eta_{h_2}=hash(s(19)), ηg3=hash(s(20))\eta_{g_3}=hash(s(20)), ηh3=hash(s(21))\eta_{h_3}=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)p(x)=\eta_{\hat{w}}\hat{w}(x)+\eta_{\hat{z}_A}\hat{z}_A(x)+\eta_{\hat{z}_B}\hat{z}_B(x)+\eta_{\hat{z}_C}\hat{z}_C(x)+\eta_{h_0}h_0(x)+\eta_ss(x)+\eta_{g_1}g_1(x) +ηh1h1(x)+ηg2g2(x)+ηh2h2(x)+ηg3g3(x)+ηh3h3(x)+\eta_{h_1}h_1(x)+\eta_{g_2}g_2(x)+\eta_{h_2}h_2(x)+\eta_{g_3}g_3(x)+\eta_{h_3}h_3(x).

2-3- The Verifier derives commitment of p(x)p(x), CompCom_p, by using polynomial commitment scheme homomorphism. For example, if polynomial commitment scheme KZGKZG is used, then Comp=(ComAHPX1)ηw^(ComAHPX2)ηz^A(ComAHPX3)ηz^B(ComAHPX4)ηz^C(ComAHPX5)ηh0(ComAHPX6)ηsCom_p=(Com_{AHP_X}^1)^{\eta_{\hat{w}}}(Com_{AHP_X}^2)^{\eta_{\hat{z}_A}}(Com_{AHP_X}^3)^{\eta_{\hat{z}_B}}(Com_{AHP_X}^4)^{\eta_{\hat{z}_C}}(Com_{AHP_X}^5)^{\eta_{h_0}}(Com_{AHP_X}^6)^{\eta_{s}}(ComAHPX7)ηg1(ComAHPX8)ηh1(ComAHPX9)ηg2(ComAHPX10)ηh2(ComAHPX11)ηg3(ComAHPX12)ηh3(Com_{AHP_X}^7)^{\eta_{g_1}}(Com_{AHP_X}^8)^{\eta_{h_1}}(Com_{AHP_X}^{9})^{\eta_{g_2}}(Com_{AHP_X}^{10})^{\eta_{h_2}}(Com_{AHP_X}^{11})^{\eta_{g_3}}(Com_{AHP_X}^{12})^{\eta_{h_3}}.

2-4- The Verifier chooses random zFz\in\mathbb{F} and queries p(z)p(z). Also, can select as z=hash(s(22)))z=hash(s(22))).

2-5- The Verifier computes result=PC.Check(vk,Comp,z,y=πAHP16,πAHP17)result=PC.Check(vk,Com_p,z,y'=\pi_{AHP}^{16},\pi_{AHP}^{17}). For example, if polynomial commitment scheme KZGKZG is used, then the following equation checks: e(Compgy,g)=e(πAHP17,vkgz)e(\frac{Com_p}{g^{y'}},g)=e(\pi_{AHP}^{17},\frac{vk}{g^z})

4-3- Example

4-3-1- PFR Verify

Verify(F,H,K,comPFR,πPFR)Verify(\mathbb{F}, \mathbb{H}, \mathbb{K}, com_{PFR},\pi_{PFR}):

1)1) The Verifier checks h(γp1)=h(γ0)=a1=ω2h(\gamma^{p_1})=h(\gamma^0)=a_1=\omega^2 and h(γp2)=h(γ3)=a2=0h(\gamma^{p_2})=h(\gamma^3)=a_2=0. Here, the Verifier checks h(1)=42h(1)=42 and h(48)=0h(48)=0.

2)2) M(β2)q2(β2)ZK(β2)=0M(\beta_2)-q_2(\beta_2)Z_{\mathbb{K}}(\beta_2)=0 , that means 3630×146=36360(mod181)36-30\times 146=36-36\equiv 0\hspace{1mm}(\textrm{mod}\hspace{1mm}181), and F(β1)q1(β1)ZK(β1)=0F'(\beta_1)-q_1(\beta_1)Z_{\mathbb{K}}(\beta_1)=0, that means 086×00(mod181)0-86\times 0\equiv 0\hspace{1mm}(\textrm{mod}\hspace{1mm}181).

4-3-2- AHP Verify

Verify(F,H,K,ComAHP,ΠAHP,x=4,y=82)Verify(\mathbb{F}, \mathbb{H}, \mathbb{K}, Com_{AHP},\Pi_{AHP},x=4,y=82) :

Since h3(β3)=h3(5)=170h_3(\beta_3)=h_3(5)=170 and vK(β3)=vK(5)=134v_{\mathbb{K}}(\beta_3)=v_{\mathbb{K}}(5)=134, therefore, the left of equation (1)(1) is h3(β3)vK(β3)=155h_3(\beta_3)v_{\mathbb{K}}(\beta_3)=155 . Also, since a(β3)=a(5)=17a(\beta_3)=a(5)=17, b(β3)=b(5)=32b(\beta_3)=b(5)=32 and β3g3(β3)+σ3K=7\beta_3g_3(\beta_3)+\frac{\sigma_3}{|\mathbb{K}|}=7, therefore, the right of the equation (1)(1) is a(β3)b(β3)(σ3g3(β3)+σ3K)=155a(\beta_3)-b(\beta_3)(\sigma_3g_3(\beta_3)+\frac{\sigma_3}{|\mathbb{K}|})=155. So, the equation (1)(1) is established.

Since r(α,β2)=α5β25αβ2=1058051080=142r(\alpha,\beta_2)=\frac{\alpha^5-\beta_2^5}{\alpha-\beta_2}=\frac{10^5-80^5}{10-80}=142, σ3=84\sigma_3=84, therefore, the left of equation (2)(2) is r(α,β2)σ3=163r(\alpha,\beta_2)\sigma_3=163 and since h2(β2)=h2(80)=42h_2(\beta_2)=h_2(80)=42, vH(β2)=vH(80)=72v_{\mathbb{H}}(\beta_2)=v_{\mathbb{H}}(80)=72, β2g2(β2)+σ2H=35\beta_2g_2(\beta_2)+\frac{\sigma_2}{|\mathbb{H}|}=35, therefore, the right of equation (2)(2) is h2(β2)vH+β2g2(β2)+σ2H=163h_2(\beta_2)v_{\mathbb{H}}+\beta_2g_2(\beta_2)+\frac{\sigma_2}{|\mathbb{H}|}=163. So, equation (2)(2) is established.

Since s(β1)=s(22)=138s(\beta_1)=s(22)=138, r(α,β1)=130r(\alpha,\beta_1)=130, M{A,B,C}ηMz^M(β1)=121\sum_{M\in\{A,B,C\}}\eta_M\hat{z}_M(\beta_1)=121, z^(β1)=53\hat{z}(\beta_1)=53, σ2=70\sigma_2=70, therefore, the left of the equation (3)(3) is s(β1)+r(α,β1)(M{A,B,C}ηMz^M(β1))σ2z^(β1)=31s(\beta_1)+r(\alpha,\beta_1)(\sum_{M\in\{A,B,C\}}\eta_M\hat{z}_M(\beta_1))-\sigma_2\hat{z}(\beta_1)=31. Also since h1(β1)=h1(22)=94h_1(\beta_1)=h_1(22)=94, vH(β1)=vH(22)=18v_{\mathbb{H}}(\beta_1)=v_{\mathbb{H}}(22)=18, g1(β1)=g1(22)=100g_1(\beta_1)=g_1(22)=100, σ1=62\sigma_1=62, therefore the right of the equation (3)(3) is h1(β1)vH(β1)+β1g1(β1)+σ1H=31h_1(\beta_1)v_{\mathbb{H}}(\beta_1)+\beta_1g_1(\beta_1)+\frac{\sigma_1}{|\mathbb{H}|}=31. So, the equation (3)(3) is established.

Since z^A(β1)=z^A(22)=140\hat{z}_A(\beta_1)=\hat{z}_A(22)=140, z^B(β1)=z^B(22)=115\hat{z}_B(\beta_1)=\hat{z}_B(22)=115, z^C(β1)=z^C(22)=125\hat{z}_C(\beta_1)=\hat{z}_C(22)=125, therefore, the left of the equation (4)(4) is z^A(β1)z^B(β1)z^C(β1)=47\hat{z}_A(\beta_1)\hat{z}_B(\beta_1)-\hat{z}_C(\beta_1)=47. Also since h0(β1)=h0(22)=73h_0(\beta_1)=h_0(22)=73 and vH(β1)=vH(22)=18v_{\mathbb{H}}(\beta_1)=v_{\mathbb{H}}(22)=18, therefore the right of the equation (4)(4) is h0(β1)vH(β1)=47h_0(\beta_1)v_{\mathbb{H}}(\beta_1)=47. So the equation (4)(4) is established.

2- The output resultresult in following steps is 11.

2-1- The Verifier chooses random values ηw^\eta_{\hat{w}}, ηz^A\eta_{\hat{z}_A}, ηz^B\eta_{\hat{z}_B}, ηz^C\eta_{\hat{z}_C}, ηh0\eta_{h_0}, ηs\eta_s, ηg1\eta_{g_1}, ηh1\eta_{h_1}, ηg2\eta_{g_2}, ηh2\eta_{h_2}, ηg3\eta_{g_3} and ηh3\eta_{h_3} of F\mathbb{F} For example, ηw^=1\eta_{\hat{w}}=1, ηz^A=4\eta_{\hat{z}_A}=4, ηz^B=10\eta_{\hat{z}_B}=10, ηz^C=8\eta_{\hat{z}_C}=8, ηh0=32\eta_{h_0}=32, ηs=45\eta_s=45, ηg1=92\eta_{g_1}=92, ηh1=11\eta_{h_1}=11, ηg2=1\eta_{g_2}=1, ηh2=5\eta_{h_2}=5, ηg3=25\eta_{g_3}=25 and ηh3=63\eta_{h_3}=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)p(x)=\eta_{\hat{w}}\hat{w}(x)+\eta_{\hat{z}_A}\hat{z}_A(x)+\eta_{\hat{z}_B}\hat{z}_B(x)+\eta_{\hat{z}_C}\hat{z}_C(x)+\eta_{h_0}h_0(x)+\eta_ss(x)+\eta_{g_1}g_1(x) +ηh1h1(x)+ηg2g2(x)+ηh2h2(x)+ηg3g3(x)+ηh3h3(x)+\eta_{h_1}h_1(x)+\eta_{g_2}g_2(x)+\eta_{h_2}h_2(x)+\eta_{g_3}g_3(x)+\eta_{h_3}h_3(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+25p(x)=134x^{47}+34x^{46}+ 70x^{45}+ 48x^{44}+169x^{43}+ 162x^{42}+ 106x^{41}+ 43x^{40}+ 97x^{39}+ 45x^{38}+ 11x^{37}+ 84x^{36}+ 16x^{35}+ 145x^{34}+ 161x^{33}+ 84x^{32}+ 147x^{31}+ 166x^{30}+ 97x^{29}+18x^{28}+ 146x^{27}+ 158x^{26}+ 101x^{25}+ 119x^{24}+ 118x^{23}+ 100x^{22}+ 35x^{21}+ 41x^{20}+ 60x^{19}+ 161x^{18} +145x^{17}+ 2x^{16}+ 121x^{15}+ 152x^{14}+ 157x^{13}+ 69x^{12}+ 5x^{11}+ 45x^{10}+144x^9+ 81x^8+ 43x^7+ 146x^6+ 98x^5+ 99x^4+ 137x^3+ 116x^2+ 162x+ 25

2-3- The Verifier derives commitment of p(x)p(x), CompCom_p, by using polynomial commitment scheme homomorphism. For example, if polynomial commitment scheme KZGKZG is used, then Comp=(ComAHPx1)ηw^(ComAHPx2)ηz^A(ComAHPx3)ηz^B(ComAHPx4)ηz^C(ComAHPx6)ηh0(ComAHPx7)ηsCom_p=(Com_{AHP_x}^1)^{\eta_{\hat{w}}}(Com_{AHP_x}^2)^{\eta_{\hat{z}_A}}(Com_{AHP_x}^3)^{\eta_{\hat{z}_B}}(Com_{AHP_x}^4)^{\eta_{\hat{z}_C}}(Com_{AHP_x}^6)^{\eta_{h_0}}(Com_{AHP_x}^7)^{\eta_{s}} =(ComAHPx1)ηw^(ComAHPx2)ηz^A(ComAHPx3)ηz^B(ComAHPx4)ηz^C(ComAHPx5)ηh0(ComAHPx6)ηs=(Com_{AHP_x}^1)^{\eta_{\hat{w}}}(Com_{AHP_x}^2)^{\eta_{\hat{z}_A}}(Com_{AHP_x}^3)^{\eta_{\hat{z}_B}}(Com_{AHP_x}^4)^{\eta_{\hat{z}_C}}(Com_{AHP_x}^5)^{\eta_{h_0}}(Com_{AHP_x}^6)^{\eta_{s}}(ComAHPx7)ηg1(ComAHPx8)ηh1(ComAHPx9)ηg2(ComAHPx10)ηh2(ComAHPx11)ηg3(ComAHPx12)ηh3=(Com_{AHP_x}^7)^{\eta_{g_1}}(Com_{AHP_x}^8)^{\eta_{h_1}}(Com_{AHP_x}^{9})^{\eta_{g_2}}(Com_{AHP_x}^{10})^{\eta_{h_2}}(Com_{AHP_x}^{11})^{\eta_{g_3}}(Com_{AHP_x}^{12})^{\eta_{h_3}}=5614844410128663262451489233111391545552511263=15256^1\hspace{1mm}48^4\hspace{1mm}44^{10}\hspace{1mm}12^8\hspace{1mm}66^{32}\hspace{1mm}62^{45}\hspace{1mm}148^{92}\hspace{1mm}33^{11}\hspace{1mm}139^1\hspace{1mm}54^5\hspace{1mm}55^{25}\hspace{1mm}112^{63}=152

2-4- The Verifier chooses random zFz\in\mathbb{F} and queries p(z)p(z). For example, z=2z=2.

2-5- The Verifier computes result=PC.Check(vk,Comp,z,y=πAHP16,πAHP17)result=PC.Check(vk,Com_p,z,y'=\pi_{AHP}^{16},\pi_{AHP}^{17}). For example, if polynomial commitment scheme KZGKZG is used, then the following equation checks: e(Compgy,g)=e(πAHP17,vkgz)e(\frac{Com_p}{g^{y'}},g)=e(\pi_{AHP}^{17},\frac{vk}{g^z}) where e(Compgy,g)=e(15226,2)=e(152×99,2)=e(25,2)=e(2132,2)=e(2,2)132e(\frac{Com_p}{g^{y'}},g)=e(\frac{152}{2^6},2)=e(152\times 99,2)=e(25,2)=e(2^{132},2)=e(2,2)^{132} and e(πAHP17,vkgz)=e(67,6622)=e(67,66×136)=e(67,107)=e(2102,2117)=e(2,2)11934e(\pi_{AHP}^{17},\frac{vk}{g^z})=e(67,\frac{66}{2^2})=e(67,66\times 136)=e(67,107)=e(2^{102},2^{117})=e(2,2)^{11934}

Last updated