Zero-Knowledge Proof (ZKP) Scheme

Function-hiding functional commitment

Function-hiding functional commitment

In this page, we will review function-hiding functional commitment zero-knowledge proof (ZKP) scheme. This scheme is a tuple $\red{(Setup,\hspace{1mm}, Commit,\hspace{1mm}Eval)}$that utilizes the following three protocols:

1- A polynomial commitment scheme

$PC=(PC.\hspace{1mm} Setup,\hspace{1mm} PC.\hspace{1mm}Commit,\hspace{1mm} PC.\hspace{1mm}Eval,\hspace{1mm}PC.\hspace{1mm}Check)$,

2- A proof of function relation (PFR)

A proof of function relation ($PFR$) $\pi=(P_{f}, \hspace{1mm}V_{f},\hspace{1mm}k_{f},\hspace{1mm}s_{f},\hspace{1mm}d_{f})$contains $k_f$wehre is the number of rounds, $s_f:\mathbb{N}\to\mathbb{N}$ where that $s_f(i)$ is the number polynomials that the Prover $P_f$sends to the Verifier $V_f$ in round $i$ and $d_f:\mathbb{N}^3\to\mathbb{N}$ so that $d_f(N,i,j)$ is the degree bound for $j^{th}$polynomial in round . Let $N$ be the maximum supported index size.

3- An algebric holographic proof (AHP)

An algebric holographic proof $AHP=(Enc_{AHP},P_{AHP}, \hspace{1mm}V_{AHP},\hspace{1mm}k_{AHP},\hspace{1mm}s_{AHP},\hspace{1mm}d_{AHP})$ contains $k_{AHP}$ where is the number of rounds, $s_{AHP}:\mathbb{N}\to\mathbb{N}$ so that $s_{AHP}(i)$ is the number polynomials that the Prover $P_{AHP}$sends to the Verifier $V_{AHP}$ in round $i$ and $d_{AHP}:\mathbb{N}^3\to\mathbb{N}$ so that $d_{AHP}(N,i,j)$ is the degree bound for $j^{th}$ polynomial in round $i$.

• Note that $s_{AHP}(0)=s_{f}(0)$ and for all $i\in [s_{AHP}(0)]$, $d_{AHP}(N,0,i)=d_{f}(N,0,i)$.

We now review the three main elements in the tuple.

• $\red{Setup(1^{\lambda},N)}$: The is function creates output $pp=PC.Commit(1^{\lambda},d)$ where $\lambda$ is security parameter and $d= \{d_{AHP}(N,i,j)\}_{i\in [k_{AHP}]\bigcup\{0\},j\in [s_{AHP}(i)]}\}\bigcup\{d_f(N,i,j)\}_{i\in[k_f],j\in[s_f(i)]}$. For example, if polynomial commitment scheme $KZG$ is used, $pp=(g,\hspace{1mm}g^d,\hspace{1mm}g^{d^2},...,\hspace{1mm}g^{d^l})$where $g$ is a generator of field $\mathbb{F}$ with large prime order $p$ such that $log(p) = Ω(λ)$ and $l$ is maximum degree of polynomials that want to commit them.
• $\red{Commit(pp,i\in \textit{I}_f,r\in R=\mathbb{R}^{s_{AHP}(0)})}$: This function contains the following steps: A- Parse $r=(r_1,...,r_{s_{AHP}(0)})$ and $pp=(ck,vk)$. B- Set $\overrightarrow{o}=Enc_{AHP}(i)$.

Note that $\textit{I}_f$ is a functional set that contains triple matrices $i=(A,B,C)\in (\mathbb{F}^{n\times n})^3$ so that for all input $x\in X$, there exists a unique $y\in Y$ and a witness (intermediate) $\omega \in W$ such that $Az\hspace{1mm} o\hspace{1mm} Bz=Cz$ where $z=(x,w,y)$. Note that a triple of matrices $(A,B,C)\in (\mathbb{F}^{n\times n})^3$ is a functional triple if and only if $A$ and $B$ are $t-$strictly lower triangular matrices $(t-SLT)$ and $C$ is $t$-diagonal matrix $(t-Diag)$. Here, $t$ is the size of the input. Note that the Prover obtains $t-SLT$ matrices $A$, $B$ and $t-Diag$ matrix $C$ for the arithmetic circuit based on the following construction: 1- Initialize three zero square matrices $A, B, C$ over $\mathbb{F}$ of order $n_g +n_i + 1$ where $n_g$ is the number of gates and $n_i$ is the number of inputs. Here, the gate $i$ is corresponding to tuple $(l_i, r_i, s_i)$ where $l_i$ and $r_i$ are left and right input wire indices, respectively and $s_i$ is gate selector, addition or multiplication. Also in the following construction $n_i$ is the number of inputs. 2- For $i=0.., n_g-1:$ $a)$ $C_{1+n_i+i, 1+n_i+i}=1$ $b)$ if $s_i$ is addition - $A_{1+n_i+i,0}=1$ - $B_{1+n_i+i,l_i}=1$ ( if the left input is a number, value of input is placed ) - $B_{1+n_i+i,r_i}=1$ ( if the right input is a number, value of input is placed) $c)$ If $s_i$ is multiplication - $A_{1+n_i+i,l_i}=1$ ( if the left input is a number, value of input is placed) - $B_{1+n_i+i,r_i}=1$ ( if the right input is a number, value of input is placed) 3- Outputs matrices $A, B$ and $C$. Note that the Prover encodes each matrix $A, B$ and $C$ by three polynomials such that encodes matrix $M$, $M\in\{A, B, C\}$, by polynomials $row_{M}(x)$, $col_M(x)$ and $val_M(x)$ so that $row_M(\gamma^i)=\omega^{r_i}$, $col_M(\gamma^i)=\omega^{c_i}$ and $val_M(\gamma^i)=v_i$ for $i\in\{0,1,2,..,m-1\}$ where $\gamma$ is a generator of multiplicative subgroup $\mathbb{K}$of $\mathbb{F}$ of order $m$ ($\mathbb{K}=<\gamma>$ and $|\mathbb{K}|=m$) and $\omega$ is a generator of multiplicative subgroup $\mathbb{H}$ of $\mathbb{F}$ of order n ($\mathbb{H}=<\omega>$ and $|\mathbb{H}|=n$). Also $m$ is maximum of the number of nonzero entries in the matrix $M$. $n$ is the order of the matrix. Also $r_i,c_i\in \{0,1,...,n-1\}$ and $v_i\in \mathbb{F}$ are row number, column number and value of $i^{th}$ nonzero entry, respectively. Therefore $\overrightarrow{O}=(row_A(x),col_A(x),val_A(x),row_B(x),col_B(x),val_B(x),row_C(x),col_C(x),val_C(x))$. C- For $i\in s_{AHP}(0)$, $c_{O_{0,i}}=PC.Commit(ck,\overrightarrow{O}[i],d_{AHP}(N,0,i),r_{O_{0,i}})$.

For example, if the polynomial commitment scheme$KZG$ is used, $c_{O_{0,i}}=\prod_{i\in\{0,1,...,deg_{\overrightarrow{O}[i]}\}}(g^{d^i})^{a_i}$ where $a_i$ is coefficient of $x^i$ in polynomial $O_{0,i}$.

We now review the last step for the commitment phase D- Output $c=(c_{O_{0,1}},c_{O_{0,2}},...,c_{O_{0,s_{AHP}(0)}})$.

• $\red{Eval(P_E(pp,i,r,x,y),V_E(pp,c,x,y))}$ $\huge{\bold{.}}$ The Prover $P_E$ and the Verifier $V_E$ parse $pp=(ck,vk)$. $\huge{\bold{.}}$ The Prover $P_E$ computes $\overrightarrow{o}=Enc_{AHP}(i)$. $\huge{\bold{.}}$ The Prover $P_E$ and the Verifier $V_E$ run polynomial interactive oracle proofs ($piop$) , $AHP$ or $PFR$.

A- $PFR$ commitment checking The Prover $P_f$ and the Verifier $V_f$ run polynomial oracle proof $PFR$ $<P_f(\overrightarrow{O},,i),V_f^{\overrightarrow{O}}()>$. This polynomial oracle proof is described in $\red{ Supplement \hspace{1mm}1}$. Note that in this polynomial oracle proof, the Prover wants to prove three following claims: $1.$ $\overrightarrow{O}[1]=row_A(x)$ , $\overrightarrow{O}[2]=col_A(x)$ and$\overrightarrow{O}[3]=val_A(x)$is encoding of a $t-SLT$ matrix. $2.$ $\overrightarrow{O}[4]=row_B(x)$ , $\overrightarrow{O}[5]=col_B(x)$ and$\overrightarrow{O}[6]=val_B(x)$is encoding of a $t-SLT$ matrix. $3.$ $\overrightarrow{O}[7]=row_C(x)$ , $\overrightarrow{O}[8]=col_C(x)$ and$\overrightarrow{O}[9]=val_C(x)$is encoding of a $t-Diag$ matrix.

B- $PFR$ and$AHP$ proof generating and verifying The Prover $P_{AHP}$ and the Verifier $V_{AHP}$ run polynomial oracle proof $AHP$ $<P_{AHP}(i,(x,y),w),V_{AHP}^{\overrightarrow{O}}((x,y))>$. Note that in this polynomial oracle proof, by keeping the function $(A,B,C)$ hidden, the Prover wants to prove that input $x$ gives output $y$.

$\huge{\bold{.}}$ For all $i\in[k_{piop}]$ and $j\in s_{piop}(i)$ when $P_{piop}$ sends oracle polynomial $o_{i,j}$ . $P_E$ computes and sends $c_{o_{i,j}}=PC.Commit(ck,o_{i,j},d_{piop}(N,i,j),r_{o_{i,j}})$

$\huge{\bold{.}}$ When $V_{piop}$ derives an oracle $o$ that is a linear combination of other oracles, $V_E$ derives $c_o$ through the $PCS$ homomorphism. $P_E$ similarly derives the commitment randomness $r_o$.

$\huge{\bold{.}}$When $V_{piop}$ queries oracle polynomial $o$ with degree bound $d_o$at $z\in \mathbb{F}$ to receive $y=o(z)$ : $\huge{.}$ $V_E$ sends $z$. $\huge{.}$ $P_E$ retrieves $r_o$, then computes $\pi=PC.Eval(ck,o,d_o,r_o,z)$and sends $\pi$ and $y=o(z)$. For example, if polynomial commitment scheme $KZG$ is used, $\pi=g^{q(d)}$ where $q(x)=\frac{o(x)-y}{x-z}$.

$\huge{.}$ $P_E$ retrieves $r_o$, then computes $\pi=PC.Eval(ck,o,d_o,r_o,z)$and sends $\pi$ and $y=o(z)$.

For example, if polynomial commitment scheme $KZG$ is used, $\pi=g^{q(d)}$ where $q(x)=\frac{o(x)-y}{x-z}$.

$\huge{.}$$V_E$ retrieves $c_o$ and asserts $1=PC.Check(vk,c_o,d_o,z,y,\pi)$. For example, if polynomial commitment scheme $KZG$ is used, $\pi$ check as following: $e(\frac{c_o}{g^y},g)=e(\pi,\frac{g^d}{g^z})$ , $e(g^{o(d)-y},g)=e(g^{q(d)},g^{d-z})$, $e(g,g)^{o(d)-y}=e(g,g)^{q(d)(d-z)}$ and $o(d)-y=q(d)(d-z)$.

$\red{Supplement\hspace{1mm}1}$

polyIOP $PFR$ includes: $1)$To prove strictly lower triangularity of the matrices $A$ and $B$ must prove that $\log^{row_M(\gamma^i)}_{\omega}> \log^{col_M(\gamma^i)}_{\omega}$ for $i \in \{0,1,..,m-1\}$and $M\in\{A,B\}$. This does by $\red{Discrete-log\hspace{1mm} comparison\hspace{1mm} protocol}$. $2)$ To prove the first $t$ rows of $A$ and $B$ are all zeros must prove that $row_M(\mathbb{K})\subseteq\{\omega^t,\omega^{t+1},...,\omega^{n-1}\}$. This does by $\red{subset\hspace{1mm} over \hspace{1mm}\mathbb{K}\hspace{1mm} protocol}$. $3)$ To prove the diagonality of the matrix $C$ must prove that $seq_{\mathbb{K}}(row_C)=seq_{\mathbb{K}}(col_C)$where $seq_{\mathbb{K}}(h)=(h(k):k\in\mathbb{K})$. This does by $\red{Geometric\hspace{1mm} sequence}$ and $\red{zero\hspace{1mm}over\hspace{1mm}\mathbb{K}\hspace{1mm}protocols}$. $4)$ To prove the first $t$ rows of $C$ are all zeros must prove that there is a vector $v\in(\mathbb{F^*})^{n-t}$ so that $seq_{\mathbb{K}}(val_C)=\vec{v}||\vec{0}$ . This does by $\red{Geometric\hspace{1mm} sequence}$ and $\red{zero\hspace{1mm}over\hspace{1mm}\mathbb{K}\hspace{1mm}protocols}$.

$3$ and $4$ result that all the non-zero entries of the matrix $C$ are in the positions $(\omega^t,\omega^t),(\omega^{t+1},\omega^{t+1}),...,(\omega^n,\omega^n)$.

$\red{Supplement\hspace{1mm}2}$

polyIOP $AHP$ includes:

Example

40380552: 02f407b3 mul a1,s0,5 4038055e: 004c addi a1,s0,11 40380552: 02f407b3 mul a1,s0,26

LD R1, 4 Mul R1, 5 => Gate 1, p=181 Add R1, 11 => Gate 2, p=181 Mul R1, 26 (== Div R1, 7) => Gate 3, p=181

$R_1^{(1)}-4=0$ $R_1^{(2)}-5R_1^{(1)}=0$ $R_1^{(3)}-R_1^{(2)}-11=0$ $R_1^{(4)}-\frac{R_1^{(3)}}{7}=0$

• $\red{Setup(1^{\lambda},N)}$:

Suppose $d=111213119$. Run $PC.\hspace{1mm}Setup(1^{\lambda},d)$ based on $KZG$ as following: $PC.\hspace{1mm}Setup(1^{\lambda},d)$ outputs $pp=(g,\hspace{1mm}g^d,\hspace{1mm}g^{d^2},...,\hspace{1mm}g^{d^l})$ where $l$ is the maximum degree of polynomials that are used in scheme . Let the computation be done in $\mathbb{F}$ of order $p=181$. A generator of $\mathbb{F}$ is $g=2$, therefore $pp=(g,\hspace{1mm}g^d,\hspace{1mm}g^{d^2},...,\hspace{1mm}g^{d^l})=(2,2^{111213119},...,2^{111213119^8})$. Because $ord(2)=180$, then $2^{111213119}=(2^{180})^{617850}2^{119} \equiv2^{119}\equiv66(\textrm{mod}\hspace{1mm}181)$. Similarly, the rest of entries are computed and as a result $pp=(2,66,83,91,96,24,2,66,83)$.

• $\red{Commit(pp=(2,66,83,91,96,24,2,66,83),i=(A,B,C),r\in R=\mathbb{R}^{s_{AHP}(0)})}$:

A- Parse $r=(r_1,...,r_{s_{AHP}(0)})$ and $pp=(ck,vk)$.

B- Set $\overrightarrow{o}=Enc_{AHP}(i)$.

We consider $z=(1,x,w_1,w_2,y)$ where $w_1=5x$, $w_2=w_1+11$ and $y=\frac{w_2}{7}$. Therefore with input $x=4$, $z=(1,4,20,31,82)$. Note that the inverse of number $a$ in this field is $a^{p-2} (\textrm{mod}\hspace{1mm}p)$ , so $7^{-1}\equiv 26\hspace{1mm}(mod\hspace{1mm}181)$.

Based on $\blue{\bold{Construction}}$ obtain:

$A=\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}$, $B=\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}$and $C=\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}$.

It can be seen that matrices $A$ and $B$ are $2-SLT$ and matrix $C$ is $2-Diag$. Also $Az\hspace{1mm}o\hspace{1mm}Bz=\begin{bmatrix}0\\0\\20\\31\\82\\\end{bmatrix}=Cz$.

To encode matrix $A$, consider multiplicative subgroup $\mathbb{H}$ of order $n=n_g+n_i+1=5$ with generator $\omega=2^{36}\equiv 59 (\textrm{mod}\hspace{1mm}181)$. Note that if $g$ is a generator of field $\mathbb{F}$ of order $p$, then $g^{\frac{p-1}{n}}$is a generator of a multiplicative subgroup of it of order $n$. Therefore $\mathbb{H}=\{1,\omega,\omega^2,\omega^3,\omega^4\}=\{1,59,42,125,135\}$.

Also, consider multiplicative subgroup $\mathbb{K}$ of order $m=\frac{n^2-n}{2}-\frac{t^2-t}{2}=9$ where $t=n_i+1$ with generator $\gamma=g^{\frac{p-1}{m}}=2^{20}\equiv43(\textrm{mod}\hspace{1mm}181)$. Therefore $\mathbb{K}=\{1,\gamma,\gamma^2,...,\gamma^8\}=\{1,43,39,48,73,62,132,65,80\}$.

First, build the polynomial $row_A(x)$. Since matrix $A$ has three non-zero entries the first of them is in the second row, so $c_0=2$ and $row_A(\gamma^0)=\omega^2$ , note that rows numbered of zero, the second is in the third row, so $c_1=3$ and $row_A(\gamma^1)=\omega^3$ and the third is in the fourth row, so $c_2=4$ and $row_A(\gamma^2)=\omega^4$.

According to the values ​​defined for $\gamma$ and $\omega$, we have $row_A(1)=42$, $row_A(43)=125$ and $row_A(39)=135$. Therefore based on Lagrange polynomials, have $row_A(x)=\sum_{i=1}^{3}y_iL_i(x)$, so$row_A(x)=42L_1(x)+125L_2(x)+135L_3(x)$, where $L_1(x)=\frac{(x-43)(x-39)}{(1-43)(1-39)}=\frac{(x-43)(x-39)}{(-42)(-38)}$. Now, since $-42\equiv139\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $-38\equiv143\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $-43\equiv138\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$and $-39\equiv142\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, therefore $L_1(x)=\frac{(x+138)(x+142)}{(139)(143)}$and since $(139)(143)\equiv 148\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$and $148^{-1}\equiv 170\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, have $L_1(x)=170(x+138)(x+142)=170x^2+178x+15$. We get in a similar way that $L_2(x)=167x^2+17x+178$ and $L_3(x)=25x^2+167x+170$. Therefore $row_A(x)=77x^2+109x+37$.

Now, we obtain $col_A(x)$. Since matrix $A$ has three non-zero entries the first of them is in the first column, so $r_0=1$ and $col_A(\gamma^0)=\omega^1$ , note that columns numbered of zero, the second is in the zero column, so $r_1=0$ and $col_A(\gamma^1)=\omega^0$ and the third is in the third column, so $r_2=3$ and $col_A(\gamma^2)=\omega^3$. Therefore $col_A(1)=59$, $col_A(43)=1$ and $col_A(39)=125$. So $col_A(x)=59L_1(x)+L_2(x)+125L_3(x)=109x^2+81x+50$.

Now, we obtain $val_A(x)$. Since matrix $A$ has three non-zero entries such that the value of all of them is one, therefore $v_0=v_1=v_2=1$. So, $val_A(x)=L_1(x)+L_2(x)+L_3(x)=1$.

Therefore, the matrix $A$ encodes by $row_A(x)=77x^2+109x+37$, $col_A(x)=109x^2+81x+50$ and $val_A(x)=1$.

Now, encode the matrix $B$. First, build the polynomial $row_B(x)$. Since matrix $B$ has four non-zero entries such that the first of them is in the second row, so $c_0=2$ and $row_B(\gamma^0)=\omega^2$ . The second and the third are in the third row, so $c_1=c_2=3$ and $row_B(\gamma^1)=row_B(\gamma^2)=\omega^3$ and the fourth is in the fourth row, so $c_3=4$ and $row_B(\gamma^3)=\omega^4$. Therefore, $row_B(1)=42$, $row_B(43)=125$, $row_B(39)=125$ and $row_B(48)=135$. So $row_B(x)=42L_1(x)+125L_2(x)+125L_3(x)+135L_4(x)$ where $L_1(x)=\frac{(x-43)(x-39)(x-48)}{(1-43)(1-39)(1-48)}=\frac{(x+138)(x+142)(x+133)}{(139)(143)(134)}=\frac{(x+138)(x+142)(x+133)}{103}$. Since $103^{-1}\equiv58\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, so $L_1(x)=58(x+138)(x+142)(x+133)=58x^3+62x^2+116x+127$. We get in a similar way that $L_2(x)=39x^3+7x^2+19x+116$, $L_3(x)=138x^3+155x^2+7x+62$ and $L_4(x)=127x^3+138x^2+39x+58$. Therefore $row_B(x)=76x^3+35x^2+174x+119$.

Now, we obtain $col_B(x)$. Since matrix $B$ has four non-zero entries that the first, second and fourth of them are in zero column, so $r_0=r_1=r_3=0$ and $col_B(\gamma^0)=col_B(\gamma^1)=col_B(\gamma^3)=\omega^0$ and the third is in the second column, so $r_2=2$ and $col_B(\gamma^2)=\omega^2$ . Therefore $col_B(1)=1$, $col_B(43)=1$, $col_B(39)=42$and $col_B(48)=1$. So $col_B(x)=L_1(x)+L_2(x)+42L_3(x)+L_4(x)=47x^3+20x^2+106x+9$.

Now, we obtain $val_B(x)$. Since matrix $B$ has four non-zero entries that value of them are $5$, $11$, $1$ and $26$, respectively. Therefore $v_0=v_1=v_2=1$$val_B(\gamma^0)=5$, $val_B(\gamma^1)=11$, $val_B(\gamma^2)=1$and $val_B(\gamma^3)=26$. So, $val_B(1)=5$, $val_B(43)=11$, $val_B(39)=1$and $val_B(48)=26$. Therefore $val_B(x)=5L_1(x)+11L_2(x)+L_3(x)+26L_4(x)=177x^3+148x^2+42$.

Therefore, the matrix $B$ encodes by $row_B(x)=76x^3+35x^2+174x+119$, $col_B(x)=47x^3+20x^2+106x+9$ and $val_B(x)=177x^3+148x^2+42$.

Now, build polynomial $row_C(x)$. In a similar way, Since matrix $C$ has three non-zero entries that are in the third, fourth and fifth rows, therefore $row_C(\gamma^0)=\omega^2$ , $row_C(\gamma^1)=\omega^3$ and $row_C(\gamma^2)=\omega^4$. Then $row_C(1)=42$ , $row_C(43)=125$ and $row_C(39)=135$. So$row_C(x)=42L_1(x)+125L_2(x)+135L_3(x)$, therefore $row_C(x)=77x^2+109x+37$.

Now, since $C$ is a diagonal matrix, polynomials $row_C(x)$ and $col_C(x)$are equal. Also, since the matrix $C$ has three non-zero entries such that the value of all of them is one, therefore $v_0=v_1=v_2=1$. So, $val_C(x)=L_1(x)+L_2(x)+L_3(x)=1$.

Therefore, the matrix $C$ encodes by $row_C(x)=77x^2+109x+37$, $col_C(x)=77x^2+109x+37$ and $val_C(x)=1$.

Therefore encoding of $i=(A,B,C)$ obtain as following:

$\overrightarrow{O}=(row_A(x),col_A(x),val_A(x),row_B(x),col_B(x),val_B(x),row_C(x),col_C(x),val_C(x))$.

C- Now, by using of KZG commitment scheme obtain commitment to each of entry $\overrightarrow{O}[i]=O_{0,i}$ as following:

$c_{O_{0,i}}=\prod_{i\in\{0,1,...,deg_{\overrightarrow{O}[i]}\}}(g^{d^i})^{a_i}$ where $a_i$ is coefficient of $x^i$ in polynomial $O_{0,i}$.

Therefore

$c_{row_A(x)}=\prod_{i=0}^{2}(g^{d^i})^a_i=\prod_{i=0}^{2}ck(i)^{a_i}=ck(0)^{37}ck(1)^{109}ck(2)^{77}=2^{37}66^{109}83^{77}\equiv118\times 57\times76\equiv 32\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$

$c_{col_A(x)}=\prod_{i=0}^{2}(g^{d^i})^a_i=\prod_{i=0}^{2}ck(i)^{a_i}=ck(0)^{50}ck(1)^{81}ck(2)^{109}=2^{50}66^{81}83^{109}\equiv116\times 31\times58\equiv 56\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$

$c_{val_A(x)}=\prod_{i=0}^{0}(g^{d^i})^a_i=ck(0)^{a_0}=ck(0)^{1}=2^{1}\equiv 2\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$

and similarly

$c_{row_B(x)}=135$, $c_{col_B(x)}=3$, $c_{val_B(x)}=50$, $c_{row_C(x)}=73$, $c_{col_C(x)}=73$ and $c_{val_C(x)}=2$.

D- Therefore, output

$c=(32,56,2,135,3,50,73,73,2)$.

-$\red{Eval(P_E(pp,i,r,x,y),V_E(pp,c,x,y))}$

$\huge{\bold{.}}$ The Prover $P_E$ and the Verifier $V_E$ parse $pp=(ck,vk)$.

$\huge{\bold{.}}$ The Prover $P_E$ computes$\overrightarrow{O}=Enc_{AHP}(i)=(row_A(x),col_A(x),val_A(x),row_B(x),col_B(x),val_B(x),row_C(x),col_C(x),val_C(x))$.

$\huge{\bold{.}}$ The Prover $P_E$ and the Verifier $V_E$ run polynomial interactive oracle proofs ($piop$) , $AHP$ or $PFR$.

A- $PFR$ commitment checking

The Prover $P_f$ and the Verifier $V_f$ run polynomial oracle proof $PFR$ $<P_f(\overrightarrow{O},,i),V_f^{\overrightarrow{O}}()>$ as following:

A- $PFR$ commitment checking The Prover

This $piop$ want to verify that three polynomials $row_A(x)$, $col_A(x)$ and $val_A(x)$, also three polynomials $row_B(x)$, $col_B(x)$, $val_B(x)$ are corresponding to $t-SLT$ and three polynomials $row_C(x)$, $col_C(x)$and $val_C(x)$ is corresponding to a $t-Diag$ matrix. This $piop$ includes:

The first, see $piop$ to prove $t-SLT$of the matrix $A$ in the following steps:

$1)$ The Prover interpolates polynomial $h$ such that $seq_{\mathbb{K}}(h)=\omega^t,\omega^{t+1},..,\omega^{n-1},0,..,0$. Here $t=2$ and $n=5$, therefore $seq_{\mathbb{K}}(h)=\omega^2,\omega^3,\omega^4,0,..,0$. This means that $\{h(k):\hspace{1mm}k\in\mathbb{K}=\{1,43,39,48,73,62,132,65,80\}\}=\{\omega^2,\omega^3,\omega^4,0,..,0\}=\{42,125,135,0,0,0,0,0,0\}$. Therefore $h(1)=42$, $h(43)=125$ , $h(39)=135$, $h(48)=h(73)=h(62)=h(132)=h(65)=h(80)=0$. So $h(x)=42L_1(x)+125L_2(x)+135L_3(x)$where $L_1(x)=\frac{(x-43)(x-39)(x-48)(x-73)(x-62)(x-132)(x-65)(x-80)}{(-42)(-38)(-47)(-72)(-61)(-131)(-64)(-79)}=161x^8+161x^7+161x^6+161x^5+161x^4+161x^3+161x^2+161x+161$,

$L_2(x)=45x^8+125x^7+126x^6+169x^5+27x^4+75x^3+148x^2+29x+161$,

$L_3(x)=125x^8+169x^7+75x^6+29x^5+45x^4+126x^3+27x^2+148x+161$,

Therefore $h(x)=121x^8+133x^7+57x^6+127x^5+103x^4+24x^3+128x^2+140x+114$. The Prover $\bold{\pink{sends}}$ $h$ to the Verifier.

$2)$ The Prover and the Verifier do $\red{Geometric\hspace{1mm}Sequence\hspace{1mm}Test}$ on $h$ (to verify correct construction of polynomial $h$). In $Geometric\hspace{1mm} Sequence\hspace{1mm} Test$ want to prove that $Seq_{\mathbb{K}}(h)=a_1,a_1r,..,a_1r^{c_1-1},a_2, a_2r,..., a_2r^{c_2-1},...,a_v,a_vr,...,a_vr^{c_v-1}$.

$\red{Start\hspace{1mm} of\hspace{1mm} Geometric\hspace{1mm} Sequence\hspace{1mm} Test }$

Since $h(\gamma^0)=\omega^2$, $h(\gamma^1)=\omega^3$ ,$h(\gamma^2)=\omega^4$ and $h(\gamma^3)=...=h(\gamma^8)=0$, then Geometric Sequence Test with $a_1=\omega^2$, $a_2=0$, $r=\omega$, $c_1=n-t=3$ and $c_2=m-(n-t)=9-3=6$ run. Let $p_i=\sum_{j<i}c_j$ for $i\in \{1,2,..,v\}$. Here $v$ is the number of $c_i$ that are non-zero. Therefore $v=2$ $p_1=0$ and $p_2=c_1=3$.

$3)$ The Verifier checks $h(\gamma^{p_i})=a_i$ for $i\in \{1,2,...,v\}$. Here checks $h(\gamma^{p_1})=h(\gamma^0)=a_1=\omega^2$ and $h(\gamma^{p_2})=h(\gamma^3)=a_2=0$. There the Verifier $\bold{\green{checks}}$ $h(1)=42$ and $h(48)=0$.

$4)$ The Prover and the Verifier run $\red{Zero\hspace{1mm}Over\hspace{1mm}\mathbb{K}}$ to check that for all $k\in\mathbb{K}$, have $(h(\gamma k)-rh(k))\prod_{i=1}^{v}(k-\gamma^{p_i+c_i-1})=0$. Here, $Zero\hspace{1mm}Over\hspace{1mm}\mathbb{K}$ run to check that for all $k\in\mathbb{K}=\{1,\gamma,\gamma^2,..,\gamma^8\}$, have $(h(\gamma k)-\omega h(k))(k-\gamma^2)(k-\omega^8)=0$. $\blue{Note}$: It is clear that if the construction of $h$ is correct, it applies this equality, because if $k=1$, $h(\gamma k)=h(\gamma)=\omega h(1)$ then $h(\gamma k)-\omega h(k)=0$. If $k=\gamma$, $h(\gamma k)=h(\gamma^2)=\omega h(\gamma)$, then $h(\gamma k)-\omega h(k)=0$. If $k=\gamma^2$, then $k-\gamma^2=0$. If $k=\omega^3,...,\omega^7$, then $h(\gamma k)=\omega h(k)=0$ and if $k=\gamma^8$, then $k-\gamma^8=0$.

$\red{Start\hspace{1mm}of\hspace{1mm} Zero\hspace{1mm} Over\hspace{1mm} \mathbb{K}}$

In $Zero\hspace{1mm}Over\hspace{1mm}\mathbb{K}$, want to prove that for all $k\in\mathbb{K}$, $F(k)=0$ where $F(x)=G(x,f_{j_1}(\alpha_1x),f_{j_2}(\alpha_2x),...,f_{j_{t}}(\alpha_{t}x))$. Here $F(x)=(h(\gamma x)-\omega h(x))(x-\gamma^2)(x-\gamma^8)$, therefore since $t=2$, $F(x)=G(x,f_{j_1}(\alpha_1x),f_{j_2}(\alpha_2x))=(h(\gamma x)-\omega h(x))(x-\gamma^2)(x-\gamma^8)$, so $h_1=f_{j_1}=h$, $h_2=f_{j_2}=h$, $\alpha_1=\gamma$ and $\alpha_2=1$.

$5)$ The Prover selects polynomials $r_i\in \mathbb{F}^{<2}[x]$, $i\in \{1,2,..,t\}$. Then computes masks $m_i(x)=r_i(\alpha_i^{-1}x)Z_{\mathbb{K}}(\alpha_i^{-1}x)$ and computes $h'_i(x)=h_i(x)+m_i(x)$ for $i\in\{1,2,..,t\}$.

Here, the Prover selects $r_1,r_2$. For example, let $r_1(x)=2+x$ and $r_2(x)=2x$. Therefore $m_1(x)=r_1(\alpha_1^{-1}x)Z_{\mathbb{K}}(\alpha_1^{-1}x)$ where $\alpha_1=\gamma=48$ and $Z_{\mathbb{K}}(x)=\prod_{x\in\mathbb{K}}(x-k)=(x-1)(x-43)(x-39)(x-48)(x-73)(x-62)(x-132)(x-65) (x-80)=x^9+180$. Therefore $m_1(x)=r_1(80x)Z_{\mathbb{K}}(80x)=80x^{10}+2x^9+101x+179$ $m_2(x)=r_2(\alpha_2^{-1}x)Z_{\mathbb{K}}(\alpha_2^{-1}x)=r_2(x)Z_{\mathbb{K}}(x)=2x(x^9+180)=2x^{10}+179x$. Then computes $h'_1(x)=h_1(x)+m_1(x)=h(x)+m_1(x)=80x^{10}+2x^9+121x^8+133x^7+57x^6+127x^5+103x^4+$ $24x^3+128x^2+60x+112$ and $h'_2(x)=h_2(x)+m_2(x)=h(x)+m_2(x)=2x^{10}+121x^8+133x^7+$ $57x^6+127x^5+103x^4+24x^3+128x^2+138x+114$.

$6)$ The Prover computes $F'(x)=G(x,h'_1(\alpha_1x),h'_2(\alpha_2x),...,h'_t(\alpha_tx))$ and $q_1(x)=\frac{F'(x)}{Z_{\mathbb{K}}(x)}$ then the Prover sends $\{m_i\}_i$, $\{r_i\}_i$ and $q_1$. Here $F'(x)=G(x,h'_1(43x),h'_2(x))=(h'_1(43x)-\omega h'_2(x))(x-\gamma^2)(x-\gamma^8)=64x^{12}+169x^{11}+168x^{10}$ $+51x^9+117x^3+12x^2+13x+130$ and then $q_1(x)=\frac{F'(x)}{Z_{\mathbb{K}}(x)}=64x^3+169x^2+168x+51$.

The Prover $\bold{\pink{sends}}$ $m_1(x)=80x^{10}+2x^9+101x+179$ , $m_2(x)=2x^{10}+179x$, $r_1(x)=2+x$ , $r_2(x)=2x$ and $q_1(x)=64x^3+169x^2+168x+51$ to the Verifier.

$7)$ The Verifier $\bold{\green{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 $\bold{\green{sends}}$ $c=171$ to the Prover.

$8)$ 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$.

$9)$ 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 $\bold{\green{queries}}$ $q_1(\beta_1)=86$ and $q_2(\beta_2)=146$. Also $\bold{\green{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 $\bold{\green{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)$.

$\red{End\hspace{1mm}of\hspace{1mm} Zero\hspace{1mm} Over\hspace{1mm} \mathbb{K}}$

$10)$ The Verifier $\bold{\green{outputs}}$ accept if all checks pass, otherwise reject. Here, outputs accept.

$\red{End\hspace{1mm}of\hspace{1mm} Geometric\hspace{1mm} Sequence\hspace{1mm} Test}$

$11)$ The Prover and the Verifier run $\red{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}:\hspace{1mm}k\in\mathbb{K}\}$and $h(\mathbb{K})=\{h(k)\hspace{1mm}:\hspace{1mm}k\in\mathbb{K}\}$.

$\red{Start\hspace{1mm}of\hspace{1mm} Subset\hspace{1mm} over\hspace{1mm} \mathbb{K}}$

.................

$\red{End\hspace{1mm}of\hspace{1mm} Subset\hspace{1mm} over\hspace{1mm} \mathbb{K}}$

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

$\red{Start\hspace{1mm}of\hspace{1mm}Discrete-log\hspace{1mm}Comparison}$

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$.

$13)$ 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 $\pink{sends}$ $s(x)$ to the Verifier.

$14)$ 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.

$4-1-5-3)$ 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$.

B- $PFR$ and$AHP$ proof generating and verifying

AHP

$1)$Let $z=(1,x,w)=(1,4,20,31,82)$. Also, let $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)$obtain the polynomial $z_A(x)$using indexing $z_A$ by elements of $\mathbb{H}$ that mean $z_A(x)$ is the polynomial that $z_A(1)=0$, $z_A(59)=0$, $z_A(42)=4$, $z_A(125)=1$ and $z_A(135)=31$.

Then obtain polynomial $\hat{z}_A(x)$ using the polynomial $z_A(x)$so 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$ and obtain $\hat{z}_A(x)$ so 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$.

Similarly, obtain 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)=0$, $\hat{z}_B(59)=0$, $\hat{z}_B(42)=5$, $\hat{z}_B(125)=31$, $\hat{z}_B(135)=26$ and also $b=2$ random locations $\hat{z}_B(150)=15$ and $\hat{z}_B(80)=170$. So $\hat{z}_B(x)=5L_3(x)+31L_4(x)+26L_5(x)+15L_6(x)+170L_7(x)=32x^6+178x^5+74x^4+101x^3+137x^2+81x+124$

Similarly, obtain polynomial $\hat{z}_C(x)$ so 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)=0$, $\hat{z}_C(59)=0$, $\hat{z}_C(42)=20$, $\hat{z}_C(125)=31$, $\hat{z}_C(135)=82$ and also $b=2$ random locations $\hat{z}_C(150)=1$ and $\hat{z}_C(80)=100$. So $\hat{z}_C(x)=20L_3(x)+31L_4(x)+82L_5(x)+L_6(x)+100L_7(x)=123x^6+50x^5+80x^4+96x^3+169x^2+157x+49$

Now, obtain polynomial $\hat{w}(x)\in \mathbb{F}^{|w|+b}[x]$that agree with $\bar{w}(x)$ on $\mathbb{H}[>|x|]$ where

$\bar{w}:\mathbb{H}[>|x|]=\{42,125,135\}\to \mathbb{F}$

$\bar{w}(h)=\frac{w(h)-\hat{x}(h)}{v_{\mathbb{H}[\leq |x|]}(h)}$

where $v_{\mathbb{H}[\leq |x|}(h)$is vanishing polynomial on $\mathbb{H}[\leq |x|]=\{1,59\}$, therefore $v_{\mathbb{H}[\leq |x|}(h)=(h-1)(h-59)$. Also $\hat{x}(h)$is the polynomial so that $\hat{x}(1)=1$ and $\hat{x}(59)=4$, therefore $\hat{x}(h)=128h+54$. Therefore

$\bar{w}(42)=\frac{w(42)-\hat{x}(42)}{(42-1)(42-59)}=\frac{20-0}{(41)(-17)}\equiv 108\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $\bar{w}(125)=\frac{w(125)-\hat{x}(125)}{(125-1)(125-59)}=\frac{31-126}{(124)(66)}\equiv 160\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$ and $\bar{w}(135)=\frac{w(135)-\hat{x}(135)}{(135-1)(135-59)}=\frac{82-139}{(134)(76)}\equiv 78\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$.

Now, obtain $\hat{w}(x)\in\mathbb{F}^{|w|+b=3+2}[x]$ so that $\hat{w}(42)=108$, $\hat{w}(125)=160$ , $\hat{w}(135)=78$ and also $b=2$ random locations $\hat{w}(150)=42$ and $\hat{w}(80)=180$. Therefore $\hat{w}(x)=108L_1(x)+160L_2(x)+78L_3(x)+42L_4(x)+180L_5(x)$ where $L_1(x)=\frac{(x-125)(x-135)(x-150)(x-80)}{(-83)(-93)(-108)(-38)}\equiv 152x^4+92x^3+73x^2+43x+112\hspace{1mm}(\textrm{mod}\hspace{1mm}181)$, $L_2(x)=156x^4+39x^3+84x^2+86x+171$, $L_3(x)=161x^4+157x^3+131x^2+159x+6$, $L_4(x)=60x^4+67x^3+118x^2+50x+20$ and $L_5(x)=14x^4+7x^3+137x^2+24x+54$. Therefore $\hat{w}(x)=149x^4+97x^3+161x^2+121x+166$.

$3)$ Find 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)=$ $92x^{12}+45x^{11}+164x^{10}+x^9+20x^8+61x^7+152x^6+49x^5+180x^4+161x^3+28x^2+165x+149$ and $v_{\mathbb{H}}(x)=\prod_{h\in\mathbb{H}}(x-h)=(x-1)(x-59)(x-42)(x-125)(x-135)=x^5+180$, obtain $h_0(x)=92x^7+45x^6+164x^5+x^4+20x^3+153x^2+16x+32$.

$4)$ Sample a fully random $s(x)\in\mathbb{F}^{2|\mathbb{H}|+b-1=11}[x]$. Consider $s(x)=5x^{10}+101x^8+17x^7+x^5+20x^4+3x+115$. Compute sum $\sigma_1=\sum_{k\in \mathbb{H}}s(k)=$ $s(1)+s(59)+s(42)+s(125)+s(135)=81+47+141+46+109\equiv 62\hspace{1mm}(\hspace{1mm}\textrm{mod}\hspace{1mm}181)$.

$5)$The Prover sends $\hat{z}_A(x)$, $\hat{z}_B(x)$, $\hat{z}_C(x)$, $\hat{w}(x)$, $h_0(x)$, $s(x)$and $\sigma_1$to the Verifier.

$6)$The Verifier chooses random numbers $\alpha$, $\eta_A$, $\eta_B$, $\eta_C$ of $\mathbb{F}$ and sends to the Prover. Let $\alpha=10$, $\eta_A=2$, $\eta_B=30$ and $\eta_C=100$.

$7)$ The Prover and the Verifier run $\bold{sum\hspace{1mm}check\hspace{1mm}protocol}$ for $s(x)+r(\alpha,x)\sum_{M}\eta_M\hat{z}_M(x)-(\sum_{M}\eta_Mr_M(\alpha,x))\hat{z}(x)$

$7-1)$ The Prover finds polynomials $g_1(x)$ and $h_1(x)$ so 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}|}$

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^{|\mathbb{H}|}-y^{|\mathbb{H}|}}{x-y}$. (Note that $r(x,y)$satisfies two useful algebraic properties. First, the univariate polynomials $(r(x,a))_{a\in \mathbb{H}}$ are linearly independent and $r(x,y)$ is their (unique) low-degree extension. Second, $r(x,y)$ vanishes on the square $\mathbb{H}\times \mathbb{H}$ except for on the diagonal, where it takes on the (non-zero) values $(r(a,a))_{a\in \mathbb{H}}$.) Therefore $r(x,y)=\frac{x^5-y^5}{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)=98x^6+172x^5+120x^4+12x^3+104x^2+131x+87$and $r(\alpha,x)=r(10,x)=\frac{10^5-x^5}{10-x}$, so the second term of the left is $r(\alpha,x)\sum_M\eta_M\hat{z}_M(x)=98x^{10}+66x^9+56x^8+29x^7+32x^6+153x^5+56x^4+136x^3+123x^2+42x+114$

Also, $\hat{z}(x)=\hat{w}(x)v_{\mathbb{H}[\leq |x|+1]}(x)+\hat{x}(x)=(149x^4+97x^3+161x^2+121x+166)(x-1)(x-59)+128x+54=149x^6+26x^5+55x^4+166x^3+52x^2+22x+74$ that agree with $z$ on $\mathbb{H}$ and $r_A(10,x)=\sum_{k\in \mathbb{H}}r(10,k)\hat{A}(k,x)$ where $\hat{A}(x,y)$ is a polynomial so that $\hat{A}(42,59)=1$, $\hat{A}(125,1)=1$, $\hat{A}(135,125)=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 25 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^5-\hat{row'_A}(k)^5}{x-\hat{row'_A}(k)}\frac{y^5-\hat{col'_A}(k)^5}{y-\hat{col'_A}(k)}\hat{val'_A}(k)$

where $row'_A:\mathbb{K}=\{1,43,39,48,73,62,132,65,80\}\to\mathbb{H}=\{1,59,42,125,135\}$ with $row'_A(k=\gamma^i)=\omega^{r_i}$ for $1\leq i\leq ||A||$ , $||A||$ is the number of nonzero entries in $A$, and $r_i$ is row number of $i^{th}$ nonzero entry and otherwise $row'_A(k)$ returns an arbitrary element in $\mathbb{H}$. So $row'_A(k)$ on $\mathbb{K}$ is a polynomial so that $row'_A(1)=42$ , $row'_A(43)=125$, $row'_A(39)=135$, $row'_A(k)$ returns arbitrary elements of $\mathbb{H}$, for example $row'_A(48)=1$, $row'_A(73)=135$, $row'_A(62)=125$, $row'_A(132)=59$, $row'_A(65)=42$ and $row'_A(80)=1$.

Also, $col'_A:\mathbb{K}=\{1,43,39,48,73,62,132,65,80\}\to\mathbb{H}=\{1,59,42,125,135\}$ with $col'_A(k=\gamma^i)=\omega^{c_i}$ for $1\leq i\leq ||A||$ and $c_i$ is column number of $i^{th}$ nonzero entry and otherwise $col'_A(k)$ returns an arbitrary element in $\mathbb{H}$. So $col'_A(k)$ on $\mathbb{K}$ is a polynomial so that $col'_A(1)=59$ , $col'_A(43)=1$, $col'_A(39)=125$, $col'_A(k)$ returns arbitrary elements of $\mathbb{H}$, for example $col'_A(48)=42$, $col'_A(73)=1$, $col'_A(62)=135$, $col'_A(132)=125$, $col'_A(65)=59$ and $col'_A(80)=42$.

And , $val'_A:\mathbb{K}=\{1,43,39,48,73,62,132,65,80\}\to\mathbb{H}=\{1,59,42,125,135\}$ with $val'_A(k=\gamma^i)=v_i$ for $1\leq i\leq ||A||$ where $v_i$ is value of $i^{th}$ nonzero entry and otherwise $val'_A(k)$ returns zero. So $val'_A(1)=1$, $val'_A(43)=1$, $val'_A(39)=1$, $val'_A(k)=0$ for $k\in \mathbb{K}-\{1,43,39\}$.

Now, $\hat{row'_A}$, $\hat{col'_A}$ and $\hat{val'_A}$ are extensions of $row'_A$, $col'_A$ and $val'_A$ so that are agree on $\mathbb{K}$. Therefore $\hat{A}(x,y)=$

References:

[1] Boneh, Dan, Wilson Nguyen, and Alex Ozdemir. "Efficient functional commitments: How to commit to a private function." Cryptology ePrint Archive (2021).‏

[2] de Castro, Leo, and Chris Peikert. "Functional commitments for all functions, with transparent setup and from SIS." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer Nature Switzerland, 2023.‏

[3] Gabizon, Ariel, and Zachary J. Williamson. "plookup: A simplified polynomial protocol for lookup tables." Cryptology ePrint Archive (2020).‏

[4] Wee, Hoeteck, and David J. Wu. "Lattice-based functional commitments: Fast verification and cryptanalysis." International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer Nature Singapore, 2023.‏