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}_{AHP_A}(k))u_{\mathbb{H}}(y,\hat{col}_{AHP_A}(k))\hat{val_A}(k)=\sum_{k\in \mathbb{K}}\frac{x^{37}-\hat{row}_{AHP_A}(k)^{37}}{x-\hat{row}_{AHP_A}(k)}\frac{y^{37}-\hat{col}_{AHP_B}(k)^{37}}{y-\hat{col}_{AHP_A}(k)}\hat{val}_{AHP_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}_{AHP_B}(k))u_{\mathbb{H}}(y,\hat{col}_{AHP_B}(k))\hat{val}_{AHP_B}(k)=\sum_{k\in \mathbb{K}}\frac{x^{37}-\hat{row}_{AHP_B}(k)^{37}}{x-\hat{row}_{AHP_B}(k)}\frac{y^{37}-\hat{col}_{AHP_B}(k)^{37}}{y-\hat{col}_{AHP_B}(k)}\hat{val}_{AHP_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}_{AHP_C}(k))u_{\mathbb{H}}(y,\hat{col}_{AHP_C}(k))\hat{val}_{AHP_C}(k)=\sum_{k\in \mathbb{K}}\frac{x^{37}-\hat{row}^{37}_{AHP_C}(k)}{x-\hat{row}_{AHP_C}(k)}\frac{y^{37}-\hat{col}^{37}_{AHP_C}(k)}{y-\hat{col}_{AHP_C}(k)}\hat{val}_{AHP_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}_{AHP_M}(k)}{(\beta_2-\hat{row}_{AHP_M}(k))(\beta_1-\hat{col}_{AHP_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}_{AHP_M}(x)\prod_{N\in\{A,B,C\}-\{M\}}(\beta_2-\hat{row}_{AHP_N}(x))(\beta_1-\hat{col}_{AHP_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

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)$, $1501801,379821,1633970,62079,395171,228443,86471,329078,95427, 108992,1378515,613699,$ $1104416,346226,238219,1433536,161089)$

$\pi^5_{AHP}=$ $(452290,856256,1270694,521470,227473,1478306,1415153,118632,1197528,1666393, 27794,$ $1484809,287621,475901,1308156,1422362,849425,1248319,406701,418963, 1084584,70607,$ $,1289612,1544342,702672,1267429,1041565,1135315,411621)$.

$\pi_{AHP}^6=$ $(1228955,598072,871213,716999,913282,1520995,178796,1426141,632720,148723,842325,$ $1393100,1301945,772228, 974543,1490686,1461879,1073543,988,1171130,236470, 225080,$ $1269609,1197501,1392158,1572201,35309,270789,926637,1268939,926637,1268939,$ $1067491,1122641,1248016,198429,340507,247239,1040499,91446,1014490)$ 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)$.

{
    "commitmentId": 64-bit,
    "class": 32-bit Integer,
    "input": 4
    "output": 82    
       
    "P_AHP1": 4255
    "P_AHP2": [1299562,1492556,55492,1130442,1037474,379888],
    "P_AHP3": [692083,703489,1216744,1167473,321181,1322746,1506753,1498609,1459683,604857,
            482390,1448628,44719,1319736,654101,216721,446434,933185,1070791,1124687,
            876189,144534,607746,561332,150588,1374718,166128,1080203,981227,897917,
            222647,1406132,88593,705790,900649,766942,904146,1530559,287049],
    "P_AHP4": [1197347,450382,1309763,1574629,915543,128579,875354,565414,1314862,483212,
               1454517,1109343,1160416,969902,1046489,1538605,807358,883357,1001808,1137937,
               616403,1249926,1501801,379821,1633970,62079,395171,228443,86471,329078,95427,
               108992,1378515,613699,1104416,346226,238219,1433536,161089],  
    "P_AHP5": [452290,856256,1270694,521470,227473,1478306,1415153,118632,1197528,1666393,
               27794,1216001,1536835,258251,948391,64473,456462,1374779,1001678,192385,
               835172,1484809,287621,475901,1308156,1422362,849425,1248319,406701,418963,
               1084584,70607,1289612,1544342,702672,1267429,1041565,1135315,411621],

    "P_AHP6": [1228955,598072,871213,716999,913282,
               1520995,178796,1426141,632720,148723,842325,1393100,1301945,772228,
               974543,1490686,1461879,1073543,988,1171130,236470,225080,1269609,
               1197501,1392158,1572201,35309,270789,926637,1268939,926637,1268939
               1067491,1122641,1248016,198429,340507,247239,1040499,91446,1014490],
    "P_AHP7": [],
    "P_AHP8": [],
    "P_AHP9": [],
    "P_AHP10": 
    "P_AHP11": [],
    "P_AHP12": [],
    "P_AHP13": 
    "P_AHP14": [],
    "P_AHP15": [],
    "P_AHP16": 
    "P_AHP17": 
    
    "Com_AHP1_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]
    "Com_AHP2_x": 1058742,
    "Com_AHP3_x": 1287898,
    "Com_AHP4_x": 937880,
    "Com_AHP5_x": 1199255,
    "Com_AHP6_x": 255923,  
    "Com_AHP7_x": 490704,
    "Com_AHP8_x": 704382,
    "Com_AHP9_x": 1412858,
    "Com_AHP10_x": 1380487,
    "Com_AHP11_x": 259428,
    "Com_AHP12_x": 1418032,
    "Com_AHP13_x": 1079279
}