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 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=\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 $x'\in\mathbb{F}$ and queries $p(x')$. Also, can select as $x'=hash(s(22)))$.

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

4-4- Example 2