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 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=ηw^ComAHPX2+ηz^AComAHPX3+ηz^BComAHPX4+ηz^CComAHPX5+ηh0ComAHPX6+ηsComAHPX7+ηg1ComAHPX8+ηh1ComAHPX9+ηg2ComAHPX10+ηh2ComAHPX11+ηg3ComAHPX12+ηh3ComAHPX13Com_p=\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_sCom_{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}Com_{AHP_X}^{13}

2-3- The Verifier chooses random xFx'\in\mathbb{F} and queries p(x)p(x'). Also, can select as x=hash(s(22)))x'=hash(s(22))).

2-4- The Verifier computes result=PC.Check(vk,Comp,x,y=πAHP16,πAHP17)result=PC.Check(vk,Com_p,x',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,vkgx)e(Com_p-gy',g)=e(\pi_{AHP}^{17},vk-gx')

4-4- Example 2

Last updated