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(\mathbb{F}, \mathbb{H}, \mathbb{K}, com_{PFR},\pi_{PFR})$: This function outputs $1$, if the following equations satisfies.

$1)$ $h(\gamma^{p_i})=a_i$ for $i\in \{1,2,...,v\}$ where $\pi_{PFR_1}=h(x)$.

$2)$ $M(\beta_2)-q_2(\beta_2)Z_{\mathbb{K}}(\beta_2)=0$

4-2- AHP Verify

$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 $\beta_3\in\mathbb{F}$ chosen by the Verifier.

$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(\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(\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)$

$\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)=\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)=\prod_{M\in\{A,B,C\}}(\beta_2-\hat{row'_M}(x))(\beta_1-\hat{col'_M}(x))$.

2- The output $result$ in following steps is $1$.

2-1- The Verifier chooses random values $\eta_{\hat{w}}$, $\eta_{\hat{z}_A}$, $\eta_{\hat{z}_B}$, $\eta_{\hat{z}_C}$, $\eta_{\hat{z}}$, $\eta_{h_0}$, $\eta_s$, $\eta_{g_1}$, $\eta_{h_1}$, $\eta_{g_2}$, $\eta_{h_2}$, $\eta_{g_3}$ and $\eta_{h_3}$ of $\mathbb{F}$ The Verifier can choose as following: $\eta_{\hat{w}}=hash(s(10))$, $\eta_{\hat{z}_A}=hash(s(11))$, $\eta_{\hat{z}_B}=hash(s(12))$, $\eta_{\hat{z}_C}=hash(s(13))$, $\eta_{h_0}=hash(s(14))$, $\eta_{s}=hash(s(15))$, $\eta_{g_1}=hash(s(16))$, $\eta_{h_1}=hash(s(17))$, $\eta_{g_2}=hash(s(18))$, $\eta_{h_2}=hash(s(19))$, $\eta_{g_3}=hash(s(20))$, $\eta_{h_3}=hash(s(21))$.

2-2- The Verifier builds the linear combination$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)$ $+\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)$, $Com_p$, by using polynomial commitment scheme homomorphism. For example, if polynomial commitment scheme $KZG$ is used, then $Com_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}}$$(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 $z\in\mathbb{F}$ and queries $p(z)$. Also, can select as $z=hash(s(22)))$.

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

4-3- Example

4-3-1- PFR Verify

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

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

$2)$ $M(\beta_2)-q_2(\beta_2)Z_{\mathbb{K}}(\beta_2)=0$ , that means $36-30\times 146=36-36\equiv 0\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, and $F'(\beta_1)-q_1(\beta_1)Z_{\mathbb{K}}(\beta_1)=0$, that means $0-86\times 0\equiv 0\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$.

4-3-2- AHP Verify

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

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

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

Since $s(\beta_1)=s(22)=138$, $r(\alpha,\beta_1)=130$, $\sum_{M\in\{A,B,C\}}\eta_M\hat{z}_M(\beta_1)=121$, $\hat{z}(\beta_1)=53$, $\sigma_2=70$, therefore, the left of the equation $(3)$ is $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)=31$. Also since $h_1(\beta_1)=h_1(22)=94$, $v_{\mathbb{H}}(\beta_1)=v_{\mathbb{H}}(22)=18$, $g_1(\beta_1)=g_1(22)=100$, $\sigma_1=62$, therefore the right of the equation $(3)$ is $h_1(\beta_1)v_{\mathbb{H}}(\beta_1)+\beta_1g_1(\beta_1)+\frac{\sigma_1}{|\mathbb{H}|}=31$. So, the equation $(3)$ is established.

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

2- The output $result$ in following steps is $1$.

2-1- The Verifier chooses random values $\eta_{\hat{w}}$, $\eta_{\hat{z}_A}$, $\eta_{\hat{z}_B}$, $\eta_{\hat{z}_C}$, $\eta_{h_0}$, $\eta_s$, $\eta_{g_1}$, $\eta_{h_1}$, $\eta_{g_2}$, $\eta_{h_2}$, $\eta_{g_3}$ and $\eta_{h_3}$ of $\mathbb{F}$ For example, $\eta_{\hat{w}}=1$, $\eta_{\hat{z}_A}=4$, $\eta_{\hat{z}_B}=10$, $\eta_{\hat{z}_C}=8$, $\eta_{h_0}=32$, $\eta_s=45$, $\eta_{g_1}=92$, $\eta_{h_1}=11$, $\eta_{g_2}=1$, $\eta_{h_2}=5$, $\eta_{g_3}=25$ and $\eta_{h_3}=63$.

2-2- The Verifier builds the linear combination$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)$ $+\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 obtains$p(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)$, $Com_p$, by using polynomial commitment scheme homomorphism. For example, if polynomial commitment scheme $KZG$ is used, then $Com_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}}$ $=(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}}$$(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}}=$$56^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 $z\in\mathbb{F}$ and queries $p(z)$. For example, $z=2$.

2-5- The Verifier computes $result=PC.Check(vk,Com_p,z,y'=\pi_{AHP}^{16},\pi_{AHP}^{17})$. For example, if polynomial commitment scheme $KZG$ is used, then the following equation checks: $e(\frac{Com_p}{g^{y'}},g)=e(\pi_{AHP}^{17},\frac{vk}{g^z})$ where $e(\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(\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}$