Example 1

The Prover sends $\pi_{PFR_{2}}=(179,101,0,0,0,0,0,0,0,2,80)$, $\pi_{PFR_{3}}=(0,179,0,0,0,0,0,0,0,0,2)$ , $\pi_{PFR_4}=(2,1)$, $\pi_{PFR_5}=(0,2)$ and $\pi_{PFR_6}=(51,168,169,64)$ to the Verifier.

2-2-3- The Verifier derives $h'_i=h_i+m_i$ through additive homomorphism. Then samples $\beta_1$, $\beta_2$ and $c$ of $\mathbb{F}^{*}-\mathbb{K}$ and sends $c$ to the Prover. Suppose $\beta_1=65$, $\beta_2=21$ and $c=171$. The Verifier sends $c=171$ to the Prover.

2-2-4- The Prover computes $q_2=r_1+cr_2+...+c^{t-1}r_t$ and the Verifier derives concrete oracle $q_2$ through additive homomorphism. Here, the Prover computes $q_2(x)=r_1(x)+cr_2(x)=2+x+171(2x)=162x+2$.

2-2-5- Let $M(x)=m_1(\alpha_1 x)+cm_2(\alpha_2 x)+...+c^{t-1}m_t(\alpha_t x)$. The Verifier computes $Z_{\mathbb{K}}(\beta_1)$, $Z_{\mathbb{K}}(\beta_2)$, queries $q_1(\beta_1)$and $q_2(\beta_2)$ and for $i\in \{1,2,..,t\}$, queries $h'_i(\alpha_i\beta_1)$ and $m_i(\alpha_i\beta_2)$to compute $F'(\beta_1)$ and $M(\beta_2)$. The Verifier asserts two identities $M(\beta_2)-q_2(\beta_2)Z_{\mathbb{K}}(\beta_2)=0$ and $F'(\beta_1)-q_1(\beta_1)Z_{\mathbb{K}}(\beta_1)=0$.

Here, $M(x)=m_1(\alpha_1 x)+cm_2(\alpha_2 x)=m_1(\gamma x)+171m_2(x)=162x^{10}+2x^9+19x+179$. The Verifier computes $Z_{\mathbb{K}}(\beta_1)=Z_{\mathbb{K}}(65)=65^9+180=0$ and $Z_{\mathbb{K}}(\beta_2)=Z_{\mathbb{K}}(21)=21^9+180=30$ and queries $q_1(\beta_1)=86$ and $q_2(\beta_2)=146$. Also queries values $h'_1(\alpha_1\beta_1)=h'_1(\gamma\times 65)=h'_1(80)=0$ , $h'_2(\alpha_2\beta_1)=h'_2(65)=0$, $m_1(\alpha_1\beta_2)=m_1(\gamma\times 21)=m_1(179)=147$ and $m_2(\alpha_2\beta_2)=m_2(21)=174$. Then checks$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)$.

3- The Prover and the Verifier run $Subset\hspace{1mm}over\hspace{1mm}\mathbb{K}$ between $row_A$ and $h$ to prove that $row_A(\mathbb{K})\subset h(\mathbb{K})$ where $row_A(\mathbb{K})=\{row_A(k):\hspace{1mm}k\in\mathbb{K}\}$and $h(\mathbb{K})=\{h(k)\hspace{1mm}:\hspace{1mm}k\in\mathbb{K}\}$.

3-5-1-2- Step 3- Subset over $\mathbb{K}$

4- The Prover and the Verifier run $Discrete-log\hspace{1mm} Comparison$ between $row_A$ and $col_A$ as following:

Let parameters $(\Delta \in \mathbb{F}, n = |\mathbb{H}|)$ such that $ord(\Delta) = 2n$ and $\Delta^2=\omega$. Here, $\omega=59$, $\Delta=56$ and $ord(\Delta)=2n=10$.

3-5-1-2- Step 4-Substep A- The Prover interpolates polynomial $s$ so that agrees with $\frac{row_A}{col_A}$ on $\mathbb{K}$. Then send them to the Verifier.

Here, $s(1)=\frac{row_A(1)}{col_A(1)}=\frac{42}{59}\equiv 59\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(43)=\frac{row_A(43)}{col_A(43)}\equiv125\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(39)=\frac{row_A(39)}{col_A(39)}=\frac{135}{125}\equiv59\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(48)=\frac{row_A(48)}{col_A(48)}=\frac{48}{45}\equiv 170\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(73)=\frac{row_A(73)}{col_A(73)}=\frac{36}{22}\equiv 51\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(62)=\frac{row_A(62)}{col_A(62)}=\frac{151}{166}\equiv 2\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(132)=\frac{row_A(132)}{col_A(132)}=\frac{21}{46}\equiv 28\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s(65)=\frac{row_A(65)}{col_A(65)}=\frac{131}{127}\equiv 135\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$ and $s(80)=\frac{row_A(80)}{col_A(80)}=\frac{6}{40}\equiv 154\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$. Therefore, $s(x)=59L_1(x)+125L_2(x)+59L_3(x)+170L_4(x)+51L_5(x)+2L_6(x)+28L_7(x)+135L_8(x)+$ $154L_9(x)$.

where $L_1(x)$, $L_2(x)$ and $L_3(x)$ are computed in step $1$ and the rest of $L_i(x)s$ are $L_4(x)=126x^8+75x^7+161x^6+126x^5+75x^4+161x^3+126x^2+75x+161$, $L_5(x)=169x^8+29x^7+126x^6+148x^5+125x^4+75x^3+45x^2+27x+161$, $L_6(x)=27x^8+45x^7+75x^6+125x^5+148x^4+126x^3+29x^2+169x+161$, $L_7(x)=75x^8+126x^7+161x^6+75x^5+126x^4+161x^3+75x^2+126x+161$, $L_8(x)=148x^8+27x^7+126x^6+45x^5+29x^4+75x^3+169x^2+125x+161$and $L_9(x)=29x^8+148x^7+75x^6+27x^5+169x^4+126x^3+125x^2+45x+161$.

Therefore $s(x)=41x^8+101x^7+34x^6+38x^5+x^4+25x^3+152x^2+123x+87$. The Prover sends $s(x)$ to the Verifier.

3-5-1-2- Step 4-Substep B- For $b\in\{row_A, col_A, s\}$, the Prover interpolates polynomial $b'$ so that for all $k\in \mathbb{K}$, $b'(k)=\Delta^{\log_{\omega}^{b(k)}}$.

Here, if $b=row_A$, $row'_A(k)=\Delta^{\log_{\omega}^{row_A(k)}}=56^{\log_{59}^{row_A(k)}}$that means $row'_A(1)=56^{\log_{59}^{42}}=56^2\equiv 59\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $row'_A(43)=56^{\log_{59}^{125}}=56^3\equiv 46\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $row'_A(39)=56^{\log_{59}^{135}}=56^4\equiv 42\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $row'_A(48)=56^{\log_{59}^{48}} \equiv 49\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $row'_A(73)=56^{\log_{59}^{36}} \equiv 114\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $row'_A(62)=56^{\log_{59}^{151}} \equiv \hspace{1mm}(\textrm{mod}\hspace{1mm}181)$.

Therefore $row'_A(x)=59L_1(x)+46L_2(x)+42L_3(x)+49L_4(x)+114L_5(x)+...$.

if $b=col_A$, $col'_A(k)=\Delta^{\log_{\omega}^{col_A(k)}}=56^{\log_{59}^{col_A(k)}}$that means $col'_A(1)=56^{\log_{59}^{59}}=56^1\equiv 56\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $col'_A(48)=56^{\log_{59}^{1}}=56^5\equiv 180\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$ and $col'_A(132)=56^{\log_{59}^{125}}=56^3\equiv 46\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$. Therefore $col'_A(x)=56L_1(x)+180L_2(x)+46L_3(x)=96x^2+47x+94$.

if $b=s$, $s'(k)=\Delta^{\log_{\omega}^{s(k)}}=56^{\log_{59}^{s(k)}}$that means $s'(1)=56^{\log_{59}^{59}}=56^1\equiv 56\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $s'(48)=56^{\log_{59}^{125}}=56^3\equiv 46\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$ and $s'(132)=56^{\log_{59}^{59}}=56^1\equiv 56\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$. Therefore $s'(x)=56L_1(x)+46L_2(x)+56L_3(x)=21x^2+103x+113$.

Then the Prover sends $row'_A$, $col'_A$ and $s'$ to the Verifier.

3-5-1-2- Step 4-Substep C- The Prover interpolates polynomial $h$ so that $seq_{\mathbf{K}}(h)=1,\Delta,\Delta^2,..,\Delta^{n-1},0,0,..,0$.

Here $seq_{\mathbf{K}}(h)=1, 56, 59, 46, 42$.

Since in this example $n_i=1$, therefore input and output are not vector. So, we denote input by $x$ and output by $y$ instead of $X$ and $Y$.

$Proof (\mathbb{F}_{181}, \mathbb{H}=\{1,59,42,125,135\}, \mathbb{K}=\{1,49,48,180,132,133\}, A, B, C, x=4,W=(20,31),y=82)$

1- The Prover puts $x=4$ in $Com_{AHP_X}^1$ . We consider $z=(1,x,w_1,w_2,y)$ where $w_1=5x$, $w_2=w_1+11$ and $y=26w_2$. Therefore $z=(1,x,W,y)=(1,4,20,31,82)$. The Prover calculates $z_A=Az=\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&1&0&0&0\\1&0&0&0&0\\0&0&0&1&0\\ \end{bmatrix}\begin{bmatrix}1\\4\\20\\31\\82\\\end{bmatrix}=\begin{bmatrix}0\\0\\4\\1\\31\\\end{bmatrix}$, $z_B=Bz=\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\5&0&0&0&0\\11&0&1&0&0\\26&0&0&0&0\\\end{bmatrix}\begin{bmatrix}1\\4\\20\\31\\82\end{bmatrix}=\begin{bmatrix}0\\0\\5\\31\\26\\\end{bmatrix}$and $z_C=Cz=\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\\end{bmatrix}\begin{bmatrix}1\\4\\20\\31\\82\\\end{bmatrix}=\begin{bmatrix}0\\0\\20\\31\\82\\\end{bmatrix}$

2- The Prover calculates the polynomial $z_A(x)$using indexing $z_A$ by elements of $\mathbb{H}$ that mean $z_A(x)$ is the polynomial where $z_A(1)=0$, $z_A(59)=0$, $z_A(42)=4$, $z_A(125)=1$ and $z_A(135)=31$.

Then calculates polynomial $\hat{z}_A(x)$ using the polynomial $z_A(x)$ such that $\hat{z}_A(x)\in \mathbb{F}^{<|\mathbb{H}|+b}[x]$ that agree with $z_A(x)$ on $\mathbb{H}$ . Note that values of up to $b$ locations in this polynomial reveals no information about the witness $w$provided the locations are in $\mathbb{F}-\mathbb{H}$. Here, for simplicity, let $b=2$. The Prover calculates $\hat{z}_A(x)$ such that agree with $z_A(x)$ on $\mathbb{H}$ and also $\hat{z}_A(150)=5$, $\hat{z}_A(80)=47$.

Therefore, we have $\hat{z}_A(x)=4L_3(x)+L_4(x)+31L_5(x)+5L_6(x)+47L_7(x)$ where $L_3(x)=133x^6+155x^5+117x^4+27x^3+48x^2+73x+171$, $L_4(x)=4x^6+123x^5+25x^4+48x^3+27x^2+113x+22$, $L_5(x)=75x^6+115x^5+27x^4+25x^3+117x^2+154x+30$, $L_6(x)=132x^6+119x^5+49x+62$ and $L_7(x)=97x^6+111x^5+84x+70$. So $\hat{z}_A(x)=116x^6+165x^5+63x^4+26x^3+45x^2+141x+168$