Example 2

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},1)=2$, $\hat{A}(\omega^{35},1)=1$, $\hat{A}(\omega^{36},1)=7$, 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)$ Therefore, $\hat{B}(x,y)=\hat{val'}_B(1)\frac{x^{37}-(\omega^{33})^{37}}{x-\omega^{33}}\frac{y^{37}-1}{y-1}+\hat{val'}_B(\gamma)\frac{x^{37}-(\omega^{33})^{37}}{x-\omega^{33}}\frac{y^{37}-(\omega)^{37}}{y-\omega}+\hat{val'}_B(\gamma^2)\frac{x^{37}-(\omega^{34})^{37}}{x-\omega^{34}}\frac{y^{37}-(\omega^2)^{37}}{y-\omega^2}+\hat{val'}_B(\gamma^3)\frac{x^{37}-(\omega^{35})^{37}}{x-\omega^{35}}\frac{y^{37}-1}{y-1}+\hat{val'}_B(\gamma^4)\frac{x^{37}-(\omega^{35})^{37}}{x-\omega^{35}}\frac{y^{37}-(\omega^{34})^{37}}{y-\omega^{34}}+\hat{val'}_B(\gamma^5)\frac{x^{37}-(\omega^{36})^{37}}{x-\omega^{36}}\frac{y^{37}-(\omega^{33})^{37}}{y-\omega^{33}}$. So, $r_B(10,x)=\sum_{k\in\mathbb{H}}r(10,k)\hat{B}(k,x)=$ where

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)$ Therefore, $\hat{C}(x,y)=\hat{val'}_C(1)\frac{x^{37}-(\omega^{33})^{37}}{x-\omega^{33}}\frac{y^{37}-(\omega^{33})^{37}}{y-\omega^{33}}+\hat{val'}_C(\gamma)\frac{x^{37}-(\omega^{34})^{37}}{x-\omega^{34}}\frac{y^{37}-(\omega^{34})^{37}}{y-\omega^{34}}+\hat{val'}_C(\gamma^2)\frac{x^{37}-(\omega^{35})^{37}}{x-\omega^{35}}\frac{y^{37}-(\omega^{35})^{37}}{y-\omega^{35}}+\hat{val'}_C(\gamma^3)\frac{x^{37}-(\omega^{36})^{37}}{x-\omega^{36}}\frac{y^{37}-(\omega^{36})^{37}}{y-\omega^{36}}$. So, where

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))$ where

Therefore, $r(\alpha,x)\sum_M \eta_M \hat{M}(x,\beta_1)=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$