Example 2

AHP Proof

$Proof (\mathbb{F}_{1678321}, \mathbb{H}, \mathbb{K}, A, B, C, X=(7 , 11 ,0 ,1 ,0 ,1 ,0 ,0 ,0 ,2 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,7 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0, 0),W=(12,22),Y=(32,84))$

1- The Prover puts $X=(7,11,0,1,0,1,0,0,0,2,0,0,0,0,0,0,0,0,7,0,0,...,0)$ in $Com_{AHP_X}^1$ . We consider $z=(1,x_1,x_2,...,x_{32},w_1,w_2,y_1,y_2)$ where $w_1=x_1+5$, $w_2=x_2\times x_{10}$ , $y_1=w_2+10$ and $y_2=w_1\times x_{19}$. Therefore $z=(1,X,W,Y)=(1,7,11,0,1,0,1,0,0,0,2,0,0,0,0,0,0,0,0,7,0,0,...,0,12,22,32,84)$ The Prover calculates:

$z_A=Az=\begin{bmatrix}0\\0\\0\\0\\0\\:\\1\\11\\1\\12\end{bmatrix}$, $z_B=Bz=\begin{bmatrix}0\\0\\0\\0\\0\\:\\12\\2\\32\\7\end{bmatrix}$, $z_C=Cz=\begin{bmatrix}0\\0\\0\\0\\0\\:\\12\\22\\32\\84\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)=...=z_A(\omega^{32})=0$, $z_A(\omega^{33})=1$, $z_A(\omega^{34})=11$, $z_A(\omega^{35})=1$ and $z_A(\omega^{36})=12$.

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(3)=3$, $\hat{z}_A(4)=4$.

Therefore, we have

$\hat{z}_A(x)=L_{34}(x)+11L_{35}(x)+L_{36}(x)+12L_{37}(x)+3L_{38}(x)+4L_{39}(x)=$ $287049x^{38} + 1530559x^{37} + 904146x^{36} + 766942x^{35} + 900649x^{34} + 705790x^{33} + 88593x^{32} + 1406132x^{31} + 222647x^{30} + 897917x^{29} + 981227x^{28} + 1080203x^{27} + 166128x^{26} + 1374718x^{25} + 150588x^{24} + 561332x^{23} + 607746x^{22} + 144534x^{21} + 876189x^{20} + 1124687x^{19} + 1070791x^{18} + 933185x^{17} + 446434x^{16} + 216721x^{15} + 654101x^{14} + 1319736x^{13} + 44719x^{12} + 1448628x^{11} + 482390x^{10} + 604857x^9 + 1459683x^8 + 1498609x^7 + 1506753x^6 + 1322746x^5 + 321181x^4 + 1167473x^3 + 1216744x^2 + 703489x + 692083$

Similarly, calculates polynomial $\hat{z}_B(x)$ so that $\hat{z}_B(x)\in \mathbb{F}^{<|\mathbb{H}|+b}[x]$ that agree with $z_B(x)$ on $\mathbb{H}$ that mean $\hat{z}_B(1)=...=\hat{z}_B(\omega^{32})=0$, $\hat{z}_B(\omega^{33})=12$, $\hat{z}_B(\omega^{34})=2$, $\hat{z}_B(\omega^{35})=32$ and $\hat{z}_B(\omega^{36})=7$ and also $b=2$ random locations $\hat{z}_B(3)=3$ and $\hat{z}_B(4)=4$. So, $\hat{z}_B(x)=12L_{34}(x)+2L_{35}(x)+32L_{36}(x)+7L_{37}(x)+3L_{38}(x)+4L_{39}(x)=$ $161089x^{38} + 1433536x^{37} + 238219x^{36} + 346226x^{35} + 1104416x^{34} + 613699x^{33} + 1378515x^{32} + 108992x^{31} + 95427x^{30} + 329078x^{29} + 86471x^{28} + 228443x^{27} + 395171x^{26} + 62079x^{25} + 1633970x^{24} + 379821x^{23} + 1501801x^{22} + 1249926x^{21} + 616403x^{20} + 1137937x^{19} + 1001808x^{18} + 883357x^{17} + 807358x^{16} + 1538605x^{15} + 1046489x^{14} + 969902x^{13} + 1160416x^{12} + 1109343x^{11} + 1454517x^{10} + 483212x^9 + 1314862x^8 + 565414x^7 + 875354x^6 + 128579x^5 + 915543x^4 + 1574629x^3 + 1309763x^2 + 450382x + 1197347$

Similarly, calculates polynomial $\hat{z}_C(x)$ such that $\hat{z}_C(x)\in \mathbb{F}^{<|\mathbb{H}|+b}[x]$ that agree with $z_C(x)$ on $\mathbb{H}$ that mean $\hat{z}_C(1)=...=\hat{z}_C(\omega^{32})=0$, $\hat{z}_C(\omega^{33})=12$ , $\hat{z}_C(\omega^{34})=22$, $\hat{z}_C(\omega^{35})=32$ and $\hat{z}_C(\omega^{36})=84$ and also $b=2$ random locations $\hat{z}_C(3)=3$ and $\hat{z}_C(4)=4$. So, $\hat{z}_C(x)=12L_{34}(x)+22L_{35}(x)+32L_{36}(x)+84L_{37}(x)+3L_{38}(x)+4L_{39}(x)=$ $411621x^{38 }+ 1135315x^{37} + 1041565x^{36} + 1267429x^{35} + 702672x^{34} + 1544342x^{33} + 1289612x^{32 }+ 70607x^{31} + 1084584x^{30} + 418963x^{29} + 406701x^{28} + 1248319x^{27} + 849425x^{26} + 1422362x^{25} + 1308156x^{24} + 475901x^{23} + 287621x^{22} + 1484809x^{21} + 835172x^{20} + 192385x^{19} + 1001678x^{18} + 1374779x^{17} + 456462x^{16} + 64473x^{15} + 948391x^{14} + 258251x^{13} + 1536835x^{12} + 1216001x^{11} + 27794x^{10} + 1666393x^9 + 1197528x^8 + 118632x^7 + 1415153x^6 + 1478306x^5 + 227473x^4 + 521470x^3 + 1270694x^2 + 856256x + 452290$

The Prover calculates polynomial $\hat{W}(x)\in \mathbb{F}^{<n_g+b}[x]$ that agree with $\bar{W}(x)$ on $\mathbb{H}[>|X|+1]$ where

$\bar{W}:\mathbb{H}[>|X|+1]=\{\omega^{33},\omega^{34},\omega^{35},\omega^{36}\}\to \mathbb{F}$

$\bar{W}(h)=\frac{W(h)-\hat{X}(h)}{v_{\mathbb{H}[\leq |X|+1]}(h)},\hspace{1mm}h\in\{w^{33},w^{34}\}$

$\bar{W}(h)=\frac{Y(h)-\hat{X}(h)}{v_{\mathbb{H}[\leq |X|+1]}(h)},\hspace{1mm}h\in\{w^{35},w^{36}\}$

and $v_{\mathbb{H}[\leq |X|+1]}(h)$ is vanishing polynomial on $\mathbb{H}[\leq |X|+1]=\{1,\omega,...,\omega^{32}\}$, therefore $v_{\mathbb{H}[\leq |X|+1]}(h)=(h-1)(h-\omega)...(h-\omega^{32})$. Also $\hat{X}(h)$ is the polynomial such that $\hat{X}(1)=1$ and $\hat{X}(\omega)=7$, $\hat{X}(\omega^2)=11$, $\hat{X}(\omega^4)=1$, $\hat{X}(\omega^6)=1$, $\hat{X}(\omega^{10})=2$, $\hat{X}(\omega^{19})=7$, $\hat{X}(\omega^i)=0$ for $i\in\{1,...,32\}-\{1,2,4,6,10,19\}$, therefore $\hat{X}(x)=1609426x^{32} + 145361x^{31} + 1059045x^{30} + 558036x^{29} + 838324x^{28} + 732837x^{27} + 976113x^{26} + 1264050x^{25} + 1273306x^{24} + 173112x^{23} + 551049x^{22} + 69676x^{21} + 904932x^{20} + 1127571x^{19} + 546454x^{18} + 227060x^{17} + 368192x^{16} + 552618x^{15} + 1053934x^{14} + 1614372x^{13} + 339618x^{12} + 826651x^{11} + 852561x^{10} + 649028x^9 + 350872x^8 + 760561x^7 + 761015x^6 + 1256843x^5 + 750361x^4 + 868552x^3 + 1432254x^2 + 741241x + 1618112$Therefore,

$\hat{w}(x)=379888x^5 + 1037474x^4 + 1130442x^3 + 55492x^2 + 1492556x + 1299562$

3- The Prover finds polynomial $h_0(x)$ so that $\hat{z}_A(x)\hat{z}_B(x)-\hat{z}_C(x)=h_0(x)v_{\mathbb{H}}(x)$. Since $\hat{z}_A(x)\hat{z}_B(x)-\hat{z}_C(x)=1014490x^{76} + 91446x^{75} + 1040499x^{74} + 247239x^{73} + 340507x^{72} + 198429x^{71} + 1248016x^{70} + 1122641x^{69} + 1067491x^{68} + 1268939x^{67} + 926637x^{66} + 270789x^{65} + 35309x^{64 }+ 1572201x^{63} + 1392158x^{62} + 1197501x^{61} + 1269609x^{60} + 225080x^{59} + 236470x^{58} + 1171130x^{57} + 988x^{56} + 1073543x^{55} + 1461879x^{54} + 1490686x^{53} + 314250x^{52} + 974543x^{51} + 772228x^{50} + 1301945x^{49} + 1393100x^{48} + 842325x^{47} + 148723x^{46} + 632720x^{45} + 1426141x^{44} + 178796x^{43} + 1520995x^{42} + 913282x^{41} + 716999x^{40 }+ 1535044x^{39} + 506626x^{38} + 188456x^{37} + 1431082x^{36} + 1337814x^{35} + 1479892x^{34 }+ 430305x^{33} + 555680x^{32} + 610830x^{31} + 409382x^{30} + 751684x^{29} + 1407532x^{28 }+ 1643012x^{27} + 106120x^{26} + 286163x^{25} + 480820x^{24} + 408712x^{23} + 1453241x^{22} + 1441851x^{21} + 507191x^{20} + 1677333x^{19} + 604778x^{18} + 216442x^{17} + 187635x^{16} + 1364071x^{15} + 703778x^{14 }+ 906093x^{13} + 376376x^{12} + 285221x^{11} + 835996x^{10} + 1529598x^9 + 1045601x^8 + 252180x^7 + 1499525x^6 + 157326x^5 + 765039x^4 + 961322x^3 + 807108x^2 + 1080249x + 449366$ and $v_{\mathbb{H}}(x)=\prod_{h\in\mathbb{H}}(x-h)=x^{37}+1$, The Prover finds $h_0(x)=1014490x^{39} + 91446x^{38} + 1040499x^{37} + 247239x^{36} + 340507x^{35} + 198429x^{34} + 1248016x^{33 }+ 1122641x^{32} + 1067491x^{31} + 1268939x^{30} + 926637x^{29} + 270789x^{28} + 35309x^{27} + 1572201x^{26} + 1392158x^{25} + 1197501x^{24} + 1269609x^{23} + 225080x^{22} + 236470x^{21} + 1171130x^{20 }+ 988x^{19} + 1073543x^{18} + 1461879x^{17} + 1490686x^{16 }+ 314250x^{15} + 974543x^{14} + 772228x^{13} + 1301945x^{12} + 1393100x^{11} + 842325x^{10} + 148723x^9 + 632720x^8 + 1426141x^7 + 178796x^6 + 1520995x^5 + 913282x^4 + 716999x^3 + 871213x^2 + 598072x + 1228955$

4- The Prover samples a fully random $s(x)\in\mathbb{F}^{<2|\mathbb{H}|+b-1=71}[x]$. Consider $s(x)=7x^{10}+100x^8+2x^3+1$. Then, the Prover computes sum $\sigma_1=\sum_{k\in \mathbb{H}}s(k)=4255$

5- The Prover sends $Com_{AHP_X}^2=\sum_{i=0}^{deg_{\hat{W}(x)}}\hat{w}_i\hspace{1mm}ck(i)=1058742$, $Com_{AHP_X}^{3}=\sum_{i=0}^{deg_{\hat{z}_A(x)}}\hat{z}_{A_i}ck(i)=1287898$, $Com_{AHP_X}^{4}=\sum_{i=0}^{deg_{\hat{z}_B(x)}}\hat{z}_{B_i}ck(i)= 937880$, $Com_{AHP_X}^{5}=\sum_{i=0}^{deg_{\hat{z}_C(x)}}\hat{z}_{C_i}ck(i)=1199255$, $Com_{AHP_X}^{6}=\sum_{i=0}^{deg_{h_0(x)}}h_{0_i}ck(i)= 255923$ and $Com_{AHP_X}^{7}=\sum_{i=0}^{deg_{s(x)}}s_i\hspace{1mm}ck(i)=490704$.

6- The Verifier chooses random numbers $\alpha$, $\eta_A$, $\eta_B$, $\eta_C$ and sends them to the Prover. ( Note that the Prover can choose $\alpha=hash(s(0))$, $\eta_A=hash(s(1))$, $\eta_B=hash(s(2))$, $\eta_C=hash(s(3))$. Let $\alpha=10$, $\eta_A=2$, $\eta_B=30$ and $\eta_C=100$.

7- The Prover finds polynomials $g_1(x)$ and $h_1(x)$ such that

$s(x)+r(\alpha,x)\sum_{M}\eta_M\hat{z}_M(x)-(\sum_{M}\eta_Mr_M(\alpha,x))\hat{z}(x)=h_1(x)v_{\mathbb{H}}(x)+xg_1(x)+\frac{\sigma_1}{|\mathbb{H}|}$ $(1)$

where $r(x,y)=u_{\mathbb{H}}(x,y)=\frac{v_{\mathbb{H}}(x)-v_{\mathbb{H}}(y)}{x-y}$ , $v_{\mathbb{H}}(x)=\prod_{h\in \mathbb{H}}(x-h)=x^{|\mathbb{H}|}-1$. Therefore $r(x,y)=\frac{x^{37}-y^{37}}{x-y}$ . Also $r_M(x,y)=\sum_{k\in \mathbb{H}}r(x,k)\hat{M}(k,y)$ for $M\in \{A,B,C\}$.

Now, since $\sum_M\eta_M\hat{z}_M(x)=\eta_A\hat{z}_A(x)+\eta_B\hat{z}_B(x)+\eta_C\hat{z} _C(x)$and $r(\alpha,x)=r(10,x)=\frac{10^{37}-x^{37}}{10-x}$, so the second term of the left of equation $(1)$ is $r(\alpha,x)\sum_M\eta_M\hat{z}_M(x)=1254201x^{74} + 951966x^{73} + 113589x^{72} + 498811x^{71} + 1098223x^{70} + 623670x^{69} + 506831x^{68} + 1427824x^{67 }+ 170669x^{66} + 1564892x^{65} + 456048x^{64} + 783754x^{63} + 911524x^{62} + 1557714x^{61} + 1027780x^{60} + 1574033x^{59} + 142618x^{58} + 1400297x^{57} + 282168x^{56} + 1384750x^{55} + 197195x^{54} + 1663151x^{53 }+ 118626x^{52} + 518880x^{51} + 143413x^{50 }+ 254527x^{49} + 1480415x^{48} + 1393054x^{47} + 890674x^{46} + 1601841x^{45} + 234410x^{44} + 600518x^{43 }+ 570901x^{42} + 601977x^{41} + 1491129x^{40} + 827957x^{39} + 851643x^{38} + 345650x^{37} + 347482x^{36} + 330919x^{35} + 857128x^{34} + 883439x^{33} + 1523863x^{32} + 1228455x^{31} + 1360072x^{30} + 1477512x^{29} + 1221548x^{28} + 1641696x^{27} + 92216x^{26} + 1513130x^{25} + 606487x^{24} + 1664443x^{23} + 814464x^{22} + 1431125x^{21} + 1550828x^{20} + 646554x^{19} + 1535880x^{18} + 1048877x^{17} + 1232429x^{16} + 1017318x^{15} + 1153784x^{14} + 1454648x^{13} + 885815x^{12} + 852481x^{11} + 26667x^{10} + 127017x^9 + 957446x^8 + 137943x^7 + 729959x^6 + 1418974x^5 + 1383097x^4 + 1529852x^3 + 637155x^2 + 1142934x + 830201$

Also, $\hat{z}(x)=\hat{W}(x)v_{\mathbb{H}[\leq |X|+1]}(x)+\hat{X}(x)=379888x^{38} + 554258x^{37} + 249703x^{36} + 693580x^{35} + 237592x^{34} + 1271221x^{33} + 247551x^{32} + 1512810x^{31} + 759758x^{30} + 1072537x^{29} + 253693x^{28} + 25719x^{27} + 1222503x^{26} + 1627866x^{25 }+ 1384100x^{24} + 548181x^{23} + 649897x^{22} + 258321x^{21} + 1617844x^{20} + 354870x^{19} + 637040x^{18 }+ 767176x^{17} + 1615730x^{16} + 1214248x^{15} + 326060x^{14} + 1213865x^{13} + 1172680x^{12} + 65141x^{11} + 118953x^{10} + 478016x^9 + 1051458x^8 + 1675614x^7 + 949880x^6 + 108738x^5 + 1497503x^4 + 486095x^3 + 958242x^2 + 1278901x + 1350868$ that agree with $z$ on $\mathbb{H}$. Also, $r_A(10,x)=\sum_{k\in \mathbb{H}}r(10,k)\hat{A}(k,x)$ where $\hat{A}(x,y)$ is a polynomial such that $\hat{A}(\omega^{33},1)=1$, $\hat{A}(\omega^{34},\omega^2)=1$, $\hat{A}(\omega^{35},1)=1$, $\hat{A}(\omega^{36},\omega^{33})=1$, and $\hat{A}(x,y)=0$ for the rest of points in $\mathbb{H}\times\mathbb{H}$. So, $\hat{A}(x,y)$ is a bivariate polynomial that passes from these 1369 points. This polynomial can obtain as following: $\hat{A}(x,y)=\sum_{k\in \mathbb{K}}u_{\mathbb{H}}(x,\hat{row'_A}(k))u_{\mathbb{H}}(y,\hat{col'_A}(k))\hat{val_A}(k)=\sum_{k\in \mathbb{K}}\frac{x^{37}-\hat{row'_A}(k)^{37}}{x-\hat{row'_A}(k)}\frac{y^{37}-\hat{col'_B}(k)^{37}}{y-\hat{col'_A}(k)}\hat{val'_A}(k)$ So $r_A(10,x)=\sum_{k\in\mathbb{H}}r(10,k)\hat{A}(k,x)=535865x^{36 }+ 426856x^{35} + 475596x^{34} + 458091x^{33} + 1506591x^{32} + 1335527x^{31} + 552969x^{30} + 1601654x^{29} + 745399x^{28} + 1280385x^{27} + 671303x^{26} + 934855x^{25} + 898910x^{24} + 1158968x^{23} + 641386x^{22} + 323675x^{21} + 1562721x^{20} + 775117x^{19} + 327316x^{18} + 1420073x^{17} + 1643380x^{16} + 1205782x^{15} + 1516893x^{14} + 985877x^{13} + 986845x^{12} + 1246093x^{11} + 815873x^{10} + 1148146x^9 + 734510x^8 + 147988x^7 + 284318x^6 + 1525335x^5 + 891280x^4 + 360740x^3 + 448902x^2 + 980633x + 1111155$ where

Now, calculates $\hat{B}(x,y)$ similarly as following: $\hat{B}(x,y)=\sum_{k\in \mathbb{K}}u_{\mathbb{H}}(x,\hat{row'_B}(k))u_{\mathbb{H}}(y,\hat{col'_B}(k))\hat{val_B}(k)=\sum_{k\in \mathbb{K}}\frac{x^{37}-\hat{row'_B}(k)^{37}}{x-\hat{row'_B}(k)}\frac{y^{37}-\hat{col'_B}(k)^{37}}{y-\hat{col'_B}(k)}\hat{val'_B}(k)$ So, $r_B(10,x)=\sum_{k\in\mathbb{H}}r(10,k)\hat{B}(k,x)=$ 1620326x^36 + 1066668x^35 + 96125x^34 + 603567x^33 + 558242x^32 + 351383x^31 + 1220164x^30 + 1113220x^29 + 511617x^28 + 218379x^27 + 543077x^26 + 178907x^25 + 1329682x^24 + 58568x^23 + 1146533x^22 + 948877x^21 + 45785x^20 + 1231010x^19 + 398692x^18 + 1334094x^17 + 506342x^16 + 28965x^15 + 158706x^14 + 657240x^13 + 506136x^12 + 484833x^11 + 713105x^10 + 498148x^9 + 1237146x^8 + 95520x^7 + 1145960x^6 + 1517154x^5 + 414812x^4 + 1548405x^3 + 614052x^2 + 1634786x + 1454002

Now, calculates $\hat{C}(x,y)$ similarly as following: $\hat{C}(x,y)=\sum_{k\in \mathbb{K}}u_{\mathbb{H}}(x,\hat{row'_C}(k))u_{\mathbb{H}}(y,\hat{col'_C}(k))\hat{val_C}(k)=\sum_{k\in \mathbb{K}}\frac{x^{37}-\hat{row'^{37}_C}(k)}{x-\hat{row'_C}(k)}\frac{y^{37}-\hat{col'^{37}_C}(k)}{y-\hat{col'_C}(k)}\hat{val'_C}(k)$ So, $r_C(10,x)=\sum_{k\in\mathbb{H}}r(10,k)\hat{C}(k,x)=$ 564874x^36 + 158712x^35 + 1068273x^34 + 705225x^33 + 585350x^32 + 1605845x^31 + 41353x^30 + 177119x^29 + 934488x^28 + 418387x^27 + 217275x^26 + 277881x^25 + 544871x^24 + 906984x^23 + 1088639x^22 + 730223x^21 + 114465x^20 + 205097x^19 + 1381442x^18 + 366209x^17 + 1014467x^16 + 30473x^15 + 1671297x^14 + 539462x^13 + 45399x^12 + 1575452x^11 + 676582x^10 + 1015618x^9 + 1425352x^8 + 26812x^7 + 661279x^6 + 93349x^5 + 1038786x^4 + 203161x^3 + 277282x^2 + 1676177x + 1111155

Therefore, the third term of the left of equation $(1)$ is

$(\sum_M \eta_M r_M(\alpha,x))\hat{z}(x)=(2r_A(10,x)+30r_B(10,x)+100r_C(10,x))\hat{z}(x)$

Therefore, the left of equation $(1)$ is $s(x)+r(\alpha,x)\sum_M \eta_M \hat{z}M(x)-(\sum_M \eta_M r_M(\alpha,x))\hat{z}(x)=$

Now, the Prover finds polynomials $g_1(x)$ and $h_1(x)$ such that $h_1(x)v_{\mathbb{H}}(x)+xg_1(x)+\frac{\sigma_1}{|\mathbb{H}|}=$

Therefore, the Prover finds polynomials $g_1(x)$ and $h_1(x)$

$g_1(x)=1399127x^{35} + 234054x^{34} + 551311x^{33} + 1464283x^{32} + 1033988x^{31} + 1393070x^{30} + 1584021x^{29} + 262549x^{28} + 468851x^{27} + 524434x^{26 }+ 730124x^{25} + 1548291x^{24} + 347787x^{23} + 1420568x^{22} + 686369x^{21} + 1104796x^{20 }+ 1652093x^{19} + 186165x^{18} + 1119820x^{17} + 336318x^{16} + 1203175x^{15} + 360741x^{14} + 187190x^{13} + 521109x^{12} + 284740x^{11} + 1422180x^{10} + 475884x^9 + 1047600x^8 + 1225116x^7 + 1150001x^6 + 290466x^5 + 829975x^4 + 1519190x^3 + 1077679x^2 + 852032x + 1610672$

$h_1(x)=560656x^{37 }+ 60831x^{36} + 218428x^{35} + 666069x^{34} + 1029772x^{33} + 758630x^{32} + 1446724x^{31} + 1077267x^{30} + 1190239x^{29} + 1586425x^{28} + 37621x^{27} + 1029983x^{26} + 1501234x^{25} + 721528x^{24} + 980207x^{23} + 1104424x^{22} + 980405x^{21} + 722662x^{20} + 459859x^{19} + 908256x^{18} + 1595013x^{17} + 1492468x^{16} + 546404x^{15} + 734174x^{14} + 405471x^{13} + 1348410x^{12} + 339556x^{11} + 1274900x^{10} + 676949x^9 + 1524717x^8 + 735990x^7 + 1659120x^6 + 1225339x^5 + 236096x^4 + 925377x^3 + 849078x^2 + 589799x + 404586$

The Prover sends, $Com_{AHP_X}^{8}=\sum_{i=0}^{deg_{g_1(x)}}g_{1_i}ck(i)=704382$ and $Com_{AHP_X}^{9}=\sum_{i=0}^{deg_{h_1(x)}}h_{1_i}ck(i)=1412858$ to the Verifier where $g_{1_i}$ is coefficient of $x^i$ of polynomial $g_1(x)$ and $h_{1_i}$ is coefficient of $x^i$ of polynomial $h_1(x)$.

8- The Verifier selects $\beta_1\in \mathbb{F}-\mathbb{H}$ and sends it to the Prover. (The Prover can selects $\beta_1=hash(s(8))$). Let $\beta_1=22$.

9- The Prover calculates $\sigma_2=\sum_{k\in\mathbb{H}}r(\alpha,k)\sum_{M}\eta_M\hat{M}(k,\beta_1)=378950$ .

Then, the Prover finds $g_2(x)$ and $h_2(x)$ such that $r(\alpha,x)\sum_M \eta_M\hat{M}(x,\beta_1)=h_2(x)v_{\mathbb{H}}(x)+xg_2(x)+\frac{\sigma_2}{|\mathbb{H}|}$

where $r(\alpha,x)\sum_M\eta_M \hat{M}(x,\beta_1)=r(10,x)(2\hat{A}(x,22)+30\hat{B}(x,22)+100\hat{C}(x,22))$

$=139x^{72} + 1209936x^{71} + 190587x^{70} + 504890x^{69} + 1288979x^{68} + 1468677x^{67} + 1440246x^{66} + 522806x^{65} + 1359862x^{64} + 80868x^{63 }+ 1206390x^{62} + 1046755x^{61} + 385478x^{60} + 565523x^{59} + 1148470x^{58} + 1201845x^{57} + 1116465x^{56} + 815461x^{55} + 1518339x^{54} + 1552482x^{53} + 226534x^{52} + 1483660x^{51} + 1193665x^{50} + 861411x^{49} + 598582x^{48} + 1195837x^{47} + 528169x^{46} + 785026x^{45 }+ 1054528x^{44 }+ 542637x^{43} + 1028077x^{42} + 1467957x^{41} + 539089x^{40 }+ 1014793x^{39} + 1213976x^{38} + 1577305x^{37} + 1642895x^{36} + 90614x^{35} + 1441442x^{34 }+ 12666x^{33} + 501190x^{32} + 200147x^{31 }+ 597144x^{30} + 1424505x^{29} + 783489x^{28} + 1343873x^{27} + 202672x^{26} + 1040663x^{25} + 540033x^{24} + 1541994x^{23} + 964649x^{22} + 1064430x^{21} + 1392111x^{20} + 366564x^{19} + 315215x^{18} + 1400207x^{17} + 1618951x^{16} + 95617x^{15} + 1118036x^{14} + 1344820x^{13} + 526493x^{12} + 1160359x^{11} + 97560x^{10} + 465203x^9 + 865325x^8 + 1087974x^7 + 1483111x^6 + 808894x^5 + 844762x^4 + 1305256x^3 + 751081x^2 + 786432x + 292698$

Hence, the Prover finds $g_2(x)=1642895x^{35} + 90753x^{34} + 973057x^{33} + 203253x^{32} + 1006080x^{31} + 1489126x^{30} + 387500x^{29} + 1186430x^{28} + 1306295x^{27} + 1025414x^{26} + 283540x^{25} + 568732x^{24} + 1586788x^{23} + 249151x^{22} + 1530172x^{21} + 534579x^{20} + 915635x^{19} + 1483029x^{18} + 1130676x^{17} + 1240225x^{16} + 1493112x^{15} + 322151x^{14} + 923375x^{13} + 860164x^{12} + 1387904x^{11} + 80620x^{10} + 1293397x^9 + 993372x^8 + 1650351x^7 + 464181x^6 + 347427x^5 + 158650x^4 + 634398x^3 + 166024x^2 + 87553x + 322087$ and

$h_2(x)=139x^{35} + 1209936x^{34} + 190587x^{33} + 504890x^{32} + 1288979x^{31} + 1468677x^{30} + 1440246x^{29 }+ 522806x^{28} + 1359862x^{27} + 80868x^{26} + 1206390x^{25} + 1046755x^{24} + 385478x^{23} + 565523x^{22} + 1148470x^{21} + 1201845x^{20} + 1116465x^{19} + 815461x^{18} + 1518339x^{17} + 1552482x^{16} + 226534x^{15} + 1483660x^{14} + 1193665x^{13} + 861411x^{12} + 598582x^{11} + 1195837x^{10} + 528169x^9 + 785026x^8 + 1054528x^7 + 542637x^6 + 1028077x^5 + 1467957x^4 + 539089x^3 + 1014793x^2 + 1213976x + 1577305$

The Prover sends , $Com_{AHP_X}^{10}=\sum_{i=0}^{deg_{g_2(x)}}g_{2_i}ck(i)=1380487$ and $Com_{AHP_X}^{11}=\sum_{i=0}^{deg_{h_2(x)}}h_{2_i}ck(i)=259428$ where $g_{2_i}$ is coefficient of $x^i$ of polynomial $g_2(x)$ and $h_{2_i}$ is coefficient of $x^i$ of polynomial $h_2(x)$.

10- The Verifier selects $\beta_2\in \mathbb{F}-\mathbb{H}$ and sends it to the Prover. For example $\beta_2=80$.

11- The Prover calculates $\sigma_3=\sum_{k\in\mathbb{K}}(\sum_M \eta_M\frac{v_{\mathbb{H}}(\beta_2)v_{\mathbb{H}}(\beta_1)\hat{val'_M}(k)}{(\beta_2-\hat{row'_M}(k))(\beta_1-\hat{col'_M}(k))})=1162153$ . Then, the Prover finds polynomials $g_3(x)$ and $h_3(x)$ such that $h_3(x)v_{\mathbb{K}}(x)=a(x)-b(x)(xg_3(x)+\frac{\sigma_3}{|\mathbb{K}|})$ 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))$ $=1296906x^{35} + 1631745x^{34} + 612500x^{33} + 526824x^{32} + 42462x^{31} + 818776x^{30} + 1402893x^{29} + 949566x^{28} + 616603x^{27} + 986171x^{26} + 460008x^{25} + 1582261x^{24} + 1077886x^{23} + 595820x^{22} + 1014838x^{21} + 1426636x^{20} + 118993x^{19} + 1092349x^{18} + 2468x^{17} + 425912x^{16} + 662080x^{15} + 665736x^{14} + 1149617x^{13} + 1658716x^{12} + 817522x^{11} + 616119x^{10} + 1252653x^9 + 1566732x^8 + 839662x^7 + 1069376x^6 + 1211198x^5 + 1604604x^4 + 1470873x^3 + 289754x^2 + 317183x + 1271979$ and $b(x)=\prod_{M\in\{A,B,C\}}(\beta_2-\hat{row'_M}(x))(\beta_1-\hat{col'_M}(x))=$$916454x^{42} + 1260873x^{41} + 570130x^{40} + 932807x^{39} + 205150x^{38} + 1351730x^{37} + 1505570x^{36} + 119616x^{35} + 661575x^{34} + 1229440x^{33} + 1192933x^{32} + 11364x^{31} + 164433x^{30} + 929209x^{29} + 661767x^{28} + 82832x^{27} + 968909x^{26} + 553623x^{25} + 282790x^{24} + 780101x^{23} + 444918x^{22} + 1247671x^{21} + 553487x^{20} + 1667118x^{19} + 498300x^{18} + 338714x^{17} + 1340147x^{16} + 917454x^{15} + 1066984x^{14} + 1408571x^{13} + 566713x^{12} + 741597x^{11} + 828088x^{10} + 727848x^9 + 1313411x^8 + 1457306x^7 + 827199x^6 + 569669x^5 + 24811x^4 + 1103826x^3 + 579226x^2 + 1603084x + 624045$

Therefore

$g_3(x)=423903x^6 + 1432943x^5 + 936488x^4 + 482019x^3 + 31948x^2 + 604913x + 651087$ and

$h_3(x)=75192x^{41} + 1425410x^{40} + 366361x^{39} + 15942x^{38} + 443512x^{37} + 1636377x^{36} + 1557044x^{35} + 746441x^{34} + 826820x^{33} + 1513071x^{32} + 1120754x^{31} + 901651x^{30} + 374419x^{29} + 278754x^{28} + 371149x^{27} + 659171x^{26} + 370586x^{25} + 494858x^{24} + 79718x^{23} + 229682x^{22} + 504490x^{21} + 1552618x^{20} + 1525264x^{19} + 146174x^{18} + 296224x^{17} + 968029x^{16} + 291466x^{15} + 934467x^{14} + 59156x^{13} + 1627926x^{12} + 1581132x^{11} + 243139x^{10} + 808890x^9 + 555919x^8 + 1106775x^7 + 417461x^6 + 990811x^5 + 591777x^4 + 284092x^3 + 1261059x^2 + 1522666x + 998008$

The Prover sends , $Com_{AHP_X}^{12}=\sum_{i=0}^{deg_{g_3(x)}}g_{3_i}ck(i)=1418032$ and $Com_{AHP_X}^{13}=\sum_{i=0}^{deg_{h_3(x)}}h_{3_i}ck(i)=1079279$ where $g_{3_i}$ is coefficient of $x^i$ of polynomial $g_3(x)$ and $h_{3_i}$ is coefficient of $x^i$ of polynomial $h_3(x)$.

12- The Prover sends $\pi_{AHP}^1=4255$, $\pi_{AHP}^2=(1299562, 1492556, 55492, 1130442,1037474, 379888)$, $\pi_{AHP}^3=( 692083, 703489,1216744, 1167473, 321181, 1322746, 1506753, 1498609, 1459683,604857, 482390, ...)$$\pi_{AHP}^4=()$, $\pi_{AHP}^5=()$, $\pi_{AHP}^6=()$ and $\pi_{AHP}^7=()$ to the Verifier that are value of $\sigma_1$, coefficients of polynomials $\hat{w}(x)$, $\hat{z}_A(x)$, $\hat{z}_B(x)$, $\hat{z}_C(x)$,$h_0(x)$ and $s(x)$, respectively.

13- The Prover sends $\pi_{AHP}^8=()$ and $\pi_{AHP}^{9}=()$ to the Verifier that are coefficients of polynomials $g_1(x)$ and $h_1(x)$, respectively.

14-The Prover sends $\pi_{AHP}^{10}=378950$, $\pi_{AHP}^{11}=()$ and $\pi_{AHP}^{12}=()$ that are value of $\sigma_2$ and coefficients of polynomials $g_2(x)$ and $h_2(x)$, respectively.

15- The Prover sends $\pi_{AHP}^{13}=1162153$, $\pi_{AHP}^{14}=()$ and $\pi_{AHP}^{15}=()$ that are value of $\sigma_3$ and coefficients of polynomials $g_3(x)$ and $h_3(x)$, respectively.

16- The Prover 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$.

17- The Prover calculates 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 Prover obtains $p(x)=1380454x^{41} + 849817x^{40} + 159830x^{39} + 1591067x^{38} + 1280259x^{37} + 129759x^{36} + 1642325x^{35 }+ 1231259x^{34} + 1091449x^{33} + 1071613x^{32} + 608376x^{31} + 1671687x^{30} + 1634568x^{29} + 794532x^{28} + 450142x^{27} + 1460185x^{26} + 849620x^{25} + 1337323x^{24} + 1094067x^{23} + 1046543x^{22} + 1173097x^{21} + 922535x^{20} + 166446x^{19} + 1212718x^{18} + 116006x^{17} + 657804x^{16} + 39944x^{15} + 289261x^{14} + 209333x^{13} + 1276111x^{12} + 363314x^{11} + 103604x^{10} + 554869x^9 + 513127x^8 + 586495x^7 + 1263408x^6 + 1598951x^5 + 20405x^4 + 276795x^3 + 1644690x^2 + 238507x + 242842$

18- The Prover calculates $p(x)$ in $x=x'$ (value of $x'$ is received from the Verifier), then puts it in $\pi_{AHP}^{16}$ . Therefore $\pi_{AHP}^{16}=p(x')=y'$. For example, if $x'=2$, then $\pi_{AHP}^{16}=p(2)=627433$.

19- The Prover computes $\pi_{AHP}^{17}=PC.Eval(ck,p(x),d_p,r_p,x')$ where $d_p$ is degree bound of $p(x)$ and $r_p$ is a random value. For example, if the polynomial commitment scheme $KZG$ is used, then the Prover builds polynomial $q(x)=\frac{p(x)-y'}{x-x'}=$ $1380454x^{40} + 254083x^{39} + 667996x^{38} + 1248738x^{37} + 421093x^{36} + 971945x^{35} + 229573x^{34} + 12084x^{33} + 1115617x^{32} + 1624526x^{31} + 500786x^{30} + 994938x^{29} + 267802x^{28 }+ 1330136x^{27} + 1432093x^{26} + 967729x^{25} + 1106757x^{24} + 194195x^{23} + 1482457x^{22} + 654815x^{21} + 804406x^{20} + 853026x^{19} + 194177x^{18} + 1601072x^{17} + 1639829x^{16} + 580820x^{15} + 1201584x^{14} + 1014108x^{13} + 559228x^{12 }+ 716246x^{11} + 117485x^{10} + 338574x^9 + 1232017x^8 + 1298840x^7 + 1505854x^6 + 918474x^5 + 79257x^4 + 178919x^3 + 634633x^2 + 1235635x + 1031456$ and calculates $\pi_{AHP}^{17}=gq(\tau)$ by using $ck$ as following: $\pi_{AHP}^{17}=\sum_{i=0}^{deg_{q(x)}}q_i\hspace{1mm}ck(i)=588602$ where $q_i$ is the coefficient of $x^i$ of $q(x)$.