Example 2

Assume the following sample code: $add\hspace{2mm} R_1, R_1, 5$ => Gate 1 $mul\hspace{2mm} R_2, R_2, R_{10}$ => Gate 2 $add\hspace{2mm} R_2,R_2,10$ => Gate 3 $mul\hspace{2mm} R_1,R_1,R_{19}$ => Gate 4

The constraints are as follows considering $p= 1678321$:

$R_1^{(2)}=R_1^{(1)}+5$ $R_2^{(2)}=R_2^{(1)}\times R_{10}^{(1)}$ $R_2^{(3)}=R_2^{(2)}+10$ $R_1^{(3)}=R_1^{(2)}\times R_{19}^{(1)}$

We continue with $n_g=4$ and $n_i=32$.

The Prover calculates square matrices $A$, $B$ and $C$ of order $n_g+n_i+1=4+32+1=37$ based on above construction:

$A=\begin{bmatrix}0&0&0&...&0&0&0&0\\0&0&0&...&0&0&0&0\\.&.&.&...&.&.&.&.\\.&.&.&...&.&.&.&.\\.&.&.&...&.&.&.&.\\.&.&.&...&.&.&.&.\\1&0&0&...&0&0&0&0\\0&0&1&...&0&0&0&0\\1&0&0&...&0&0&0&0\\0&0&0&...&1&0&0&0\end{bmatrix}$, $B=\begin{bmatrix}0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&...&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&...&0&0&0&0\\.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&...&.&.&.&.\\.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&...&.&.&.&.\\.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&...&.&.&.&.\\.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.&...&.&.&.&.\\5&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&...&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&..&0&0&0&0\\10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&...&0&1&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&...&0&0&0&0\end{bmatrix}$ , $C=\begin{bmatrix}0&0&...&0&0&0&0\\0&0&...&0&0&0&0\\.&.&...&.&.&.&.\\.&.&...&.&.&.&.\\.&.&...&.&.&.&.\\.&.&...&.&.&.&.\\0&0&...&1&0&0&0\\0&0&...&0&1&0&0\\0&0&...&0&0&1&0\\0&0&...&0&0&0&1\end{bmatrix}$

At we see, the matrices $A$ and $B$ are $33-SLT$ and matrix $C$ is $33-Diag$. Also $Az\hspace{1mm}o\hspace{1mm}Bz=Cz$.

We consider multiplicative subgroup $\mathbb{H}$ of order $n=n_g+n_i+1=37$ with generator $\omega=11^{\frac{p-1}{37}}\equiv 1101389 (\textrm{mod}\hspace{1mm}p)$. Therefore, $\mathbb{H}=\{1,\omega,\omega^2,\omega^3,\omega^4,...,\omega^{36}\}=\{1, 1101389, 876941, 1253722, 373750, 668759, 747302, 1444226, 727349, 1364683, 1298322,$$1224122, 644775, 127745, 1610054, 257937, 1257144, 1496263, 722913, 1195510, 1536124,$ $1669124, 870923, 784349, 1262357, 1500979, 469942, 1466322, 1364193, 358753, 1173208,$ $586481, 1605555, 1190739, 1632256, 159545, 899305\}$

Note that based on construction for matrices $A$, $B$ and $C$, we can conclude that the most number nonzero entries in $A$ and $C$ is $n_g$ and in $B$ is $2n_g$, therefore we can consider $m=2n_g$. Therefore, consider multiplicative subgroup $\mathbb{K}$ of order $m=2n_g=8$ with generator $\gamma=11^{\frac{p-1}{8}}\equiv 216 (\textrm{mod}\hspace{1mm}p)$. Therefore, $\mathbb{K}=\{1,\gamma,\gamma^2,...,\gamma^{7}\}=\{1,216, 46656, 7770, 1678320, 1678105, 1631665, 1670551 \}$.

AHP Commitment

$Commit(ck,m_f=(A,B,C),s\in R)$:

1 - The Prover Selects $s=(s_1,...,s_{s_{AHP}(0)})$ of random space $R$. 2- The Prover calculates $\overrightarrow{O}_{AHP}=Enc(m_f=(A,B,C))$ as encoded index as following:

The polynomial $AHProw_A:\mathbb{K}\to\mathbb{H}$ with $AHProw_A(k=\gamma^i)=\omega^{r_i}$ for $1\leq i\leq ||A||$ , and otherwise $AHProw_A(k)$ returns an arbitrary element in $\mathbb{H}$. So $AHProw_A(k)$ on $\mathbb{K}$ is a polynomial so that $AHProw_A(1)=\omega^{33}$ , $AHProw_A(\gamma)=\omega^{34}$, $AHProw_A(\gamma^2)=\omega^{35}$ , $AHProw_A(\gamma^3)=\omega^{36}$ and otherwise $AHProw_A(k)$ returns arbitrary elements of $\mathbb{H}$, for example $AHProw_A(\gamma^i)=\omega^i$ for $4\leq i\leq 7$. Therefore,

$AHProw_A(x)=\sum_{i=1}^{8}y_iL_i(x)=739930x^7 + 100821x^6 + 664621x^5 + 147929x^4 + 1066695x^3 + 902750x^2 + 454730x + 469905$

Also, $AHPcol_A:\mathbb{K}\to\mathbb{H}$ with $AHPcol_A(k=\gamma^i)=\omega^{c_i}$ for $1\leq i\leq ||A||$ and otherwise $AHPcol_A(k)$ returns an arbitrary element in $\mathbb{H}$. So, $AHPcol_A(k)$ on $\mathbb{K}$ is a polynomial so that $AHPcol_A(1)=1$ , $AHPcol_A(\gamma)=\omega^2$, $AHPcol_A(\gamma^2)=1$ , $AHPcol_A(\gamma^3)=\omega^{33}$ and otherwise $AHPcol_A(k)$ returns arbitrary elements of $\mathbb{H}$, for example $AHPcol_A(\gamma^i)=\omega^i$ for $4\leq i\leq 7$. Therefore, $AHPcol_A(x)=\sum_{i=1}^{8}y_iL_i(x)=344425x^7 + 1483132x^6 + 490249x^5 + 246919x^4 + 662128x^3 + 101801x^2 + 833805x + 872505$

and , $AHPval_A:\mathbb{K}\to\mathbb{H}$ with $AHPval_A(k=\gamma^i)=\frac{v_i}{u_{\mathbb{H}}(AHProw_A(k),AHProw_A(k))u_{\mathbb{H}}(AHPcol_A(k),AHPcol_A(k))}$ for $1\leq i\leq ||A||=4$ where $v_i$ is value of $i^{th}$ nonzero entry and otherwise $AHPval_A(k)$ returns zero. Note that based on definition of $u_{\mathbb{H}}(x,y)$, for each $x \in \mathbb{H}$, $u_{\mathbb{H}}(x,x)=|\mathbb{H}|x^{|\mathbb{H}|-1}=37x^{36}$. So $AHPval_A(1)=\frac{1}{(37AHProw^{36}_A(1))(37AHPcol^{36}_A(1))}=\frac{1}{37\times (\omega^{33})^{36}\times37\times1}$, $AHPval_A(\gamma)=\frac{2}{(37AHProw^{36}_A(\gamma))(37AHPcol^{36}_A(\gamma))}=\frac{2}{37\times (\omega^{34})^{36}\times37\times(\omega^2)^{36}}$ , $AHPval_A(\gamma^2)=\frac{1}{(37AHProw^{36}_A(\gamma^2))(37AHPcol^{36}_A(\gamma^2))}=\frac{1}{37\times (\omega^{35})^{36}\times37\times1}$, $AHPval_A(\gamma^3)=\frac{7}{(37AHProw^{36}_A(\gamma^3))(37AHPcol^{36}_A(\gamma^3))}=\frac{7}{37\times (\omega^{36})^{36}\times37\times(\omega^{33})^{36}}$ , and $AHPval_A(k)=0$ for $k\in \mathbb{K}-\{1,\gamma,\gamma^2,\gamma^3\}$. Therefore $AHPval_A(x)=\sum_{i=1}^{8}y_iL_i(x)=1349736x^7 + 870027x^6 + 189189x^5 + 1024786x^4 + 201373x^3 + 194896x^2 + 1568354x + 1218943$

Now, $\hat{AHProw_A}$, $\hat{AHPcol_A}$ and $\hat{AHPval_A}$ are extensions of $AHProw_A$, $AHPcol_A$ and $AHPval_A$ so that are agree on $\mathbb{K}$.

Similarly, $AHProw_B:\mathbb{K}\to\mathbb{H}$ so that $AHProw_B(1)=\omega^{33}$, $AHProw_B(\gamma)=\omega^{33}$, $AHProw_B(\gamma^2)=\omega^{34}$ , $AHProw_B(\gamma^3)=\omega^{35}$, $AHProw_B(\gamma^4)=\omega^{35}$, $AHProw_B(\gamma^5)=\omega^{36}$ and for the rest values of $\mathbb{K}$, $AHProw_B(k)$ returns arbitrary elements of $\mathbb{H}$, for example $AHProw_B(\gamma^i)=\omega^i$ for $6\leq i\leq 7$. Therefore $AHProw_B(x)=\sum_{i=1}^{8}y_iL_i(x)=745068x^7 + 1550888x^6 + 311204x^5 + 1053454x^4 + 781197x^3 + 709275x^2 + 356449x + 718167$

Also, $AHPcol_B:\mathbb{K}\to\mathbb{H}$ so that $AHPcol_B(1)=1$ , $AHPcol_B(\gamma)=\omega$, $AHPcol_B(\gamma^2)=\omega^{10}$, $AHPcol_B(\gamma^3)=1$ , $AHPcol_B(\gamma^4)=\omega^{34}$, $AHPcol_B(\gamma^5)=1$ and for the rest values of $\mathbb{K}$ , $AHPcol_B(k)$ returns arbitrary elements of $\mathbb{H}$, for example, $AHPcol_B(\gamma^i)=\omega^i$ for $6\leq i\leq 7$. Therefore $AHPcol_B(x)=\sum_{i=1}^{8}y_iL_i(x)=757883x^7 + 1334841x^6 + 941775x^5 + 1041045x^4 + 898965x^3 + 1498879x^2 + 781052x + 1137166$

and , $AHPval_B:\mathbb{K}\to\mathbb{H}$ so that $AHPval_B(1)=\frac{5}{(37AHProw^{36}_B(1))(37AHPcol^{36}_B(1))}=\frac{5}{37\times (\omega^{33})^{36}\times37\times1}=$, $AHPval_B(\gamma)=\frac{1}{(37AHProw^{36}_B(\gamma))(37AHPcol^{36}_B(\gamma))}=\frac{1}{37\times (\omega^{33})^{36}\times37\times(\omega)^{36}}$ , $AHPval_B(\gamma^2)=\frac{1}{(37AHProw^{36}_B(\gamma^2))(37AHPcol^{36}_B(\gamma^2))}=\frac{1}{37\times (\omega^{34})^{36}\times37\times1}$ , $AHPval_B(\gamma^3)=\frac{10}{(37AHProw^{36}_A(\gamma^3))(37AHPcol^{36}_A(\gamma^3))}=\frac{10}{37\times (\omega^{35})^{36}\times37\times1}$, $AHPval_B(\gamma^4)=\frac{1}{(37AHProw^{36}_A(\gamma^4))(37AHPcol^{36}_A(\gamma^4))}=\frac{1}{37\times (\omega^{35})^{36}\times37\times(\omega^{34})^{36}}$ , $AHPval_B(\gamma^5)=\frac{1}{(37AHProw^{36}_A(\gamma^5))(37AHPcol^{36}_A(\gamma^5))}=\frac{1}{37\times (\omega^{36})^{36}\times37\times1}$ , and $AHPval_B(k)=0$ for $k\in \mathbb{K}-\{1,\gamma,\gamma^2,\gamma^3,\gamma^4,\gamma^5\}$. Therefore $AHPval_B(x)=\sum_{i=1}^{8}y_iL_i(x)=1592245x^7 + 169676x^6 + 1573426x^5 + 1612428x^4 + 256156x^3 + 1249861x^2 + 995621x + 462292$

Now, $\hat{AHProw_B}$, $\hat{AHPcol_B}$ and $\hat{AHPval_B}$ are extensions of $AHProw_B$, $AHPcol_B$ and $AHPval_B$ so that are agree on $\mathbb{K}$.

Similarly, $AHProw_C:\mathbb{K}\to\mathbb{H}$ so that $AHProw_C(1)=\omega^{33}$, $AHProw_C(\gamma)=\omega^{34}$, $AHProw_C(\gamma^2)=\omega^{35}$, $AHProw_C(\gamma^3)=\omega^{36}$ and for the rest values of $\mathbb{K}$, $AHProw_C(k)$ returns arbitrary elements of $\mathbb{H}$, for example $AHProw_C(\gamma^i)=\omega^{i}$ for $4\leq i\leq 7$. Therefore $AHProw_C(x)=\sum_{i=1}^{8}y_iL_i(x)=739930x^7 + 100821x^6 + 664621x^5 + 147929x^4 + 1066695x^3 + 902750x^2 + 454730x + 469905$

Also, $AHPcol_C:\mathbb{K}\to\mathbb{H}$ so that $AHPcol_C(1)=\omega^{33}$ , $AHPcol_C(\gamma)=\omega^{34}$, $AHPcol_C(\gamma^2)=\omega^{35}$, $AHPcol_C(\gamma^3)=\omega^{36}$ and for the rest values of $\mathbb{K}$ , $AHPcol_C(k)$ returns arbitrary elements of $\mathbb{H}$, for example $AHPcol_C(\gamma^i)=\omega^i$ for $4\leq i\leq 7$. Therefore $AHPcol_C(x)=\sum_{i=1}^{8}y_iL_i(x)=739930x^7 + 100821x^6 + 664621x^5 + 147929x^4 + 1066695x^3 + 902750x^2 + 454730x + 469905$

and , $AHPval_C:\mathbb{K}\to\mathbb{H}$ so that $AHPval_C(1)=\frac{1}{(37AHProw^{36}_C(1))(37AHPcol^{36}_C(1))}=\frac{1}{37\times (\omega^{33})^{36}\times37\times(\omega^{33})^{36}}$, $AHPval_C(\gamma)=\frac{1}{(37AHProw^{36}_C(\gamma))(37AHPcol^{36}_C(\gamma))}=\frac{1}{37\times (\omega^{34})^{36}\times37\times(\omega^{34})^{36}}$ , $AHPval_C(\gamma^2)=\frac{1}{(37AHProw^{36}_C(\gamma^2))(37AHPcol^{36}_C(\gamma^2))}=\frac{1}{37\times (\omega^{35})^{36}\times37\times(\omega^{35})^{36}}$ ,$AHPval_C(\gamma^3)=\frac{1}{(37AHProw^{36}_C(\gamma^3))(37AHPcol^{36}_C(\gamma^3))}=\frac{1}{37\times (\omega^{36})^{36}\times37\times(\omega^{36})^{36}}$ and $AHPval_C(k)=0$ for $k\in \mathbb{K}-\{1,\gamma,\gamma^2,\gamma^3\}$. Therefore $AHPval_C(x)=\sum_{i=1}^{8}y_iL_i(x)=435354x^7 + 1188860x^6 + 1158417x^5 + 525698x^4 + 1126753x^3 + 467855x^2 + 544916x + 1083027$

Now, $\hat{AHProw_C}$, $\hat{AHPcol_C}$ and $\hat{AHPval_C}$ are extensions of $AHProw_C$, $AHPcol_C$ and $AHPval_C$ so that are agree on $\mathbb{K}$.

Therefore,

$\overrightarrow{O}_{AHP}=469905, 454730, 902750, 1066695, 147929, 664621, 100821, 739930,872505 ,$ $833805, 101801, 662128,246919, 490249, 1483132, 344425,1218943,1568354, 194896$ $201373, 1024786, 189189,870027, 1349736,718167,356449, 709275, 781197,1053454,$ $311204,1550888,745068, 1137166, 781052, 1498879, 898965, 1041045, 941775, 1334841,$ $757883,462292, 995621, 1249861,256156, 1612428, 1573426, 169676,1592245,469905,$ $454730,902750, 1066695,147929,664621,100821,739930,469905,454730, 902750,$ $1066695, 147929,664621,100821, 739930, 1083027, 544916,467855,1126753,525698,$ $1158417,1188860,435354)$

3- The Prover calculates commitment by using of $KZG$ commitment scheme as following:

$Com_{T}=\sum_{i=0}^{deg_T}a_ig\tau^i=\sum_{i=0}^{deg_T}a_ick(i)$ where $a_i$ is coefficient of $x^i$ in polynomial $T(x)$.

4- The Prover sends $AHP\hspace{1mm}Com^0=\sum_{i=0}^{deg_{\hat{row'}_A}}\hat{row'}_{A_i}\hspace{1.1mm}ck(i)=$

and similarly

$AHP\hspace{1mm}Com^1=$, $AHP\hspace{1mm}Com^2=$, $AHP\hspace{1mm}Com^3=$, $AHP\hspace{1mm}Com^4=$, $AHP\hspace{1mm}Com^5=$, $AHP\hspace{1mm}Com^6=$, $AHP\hspace{1mm}Com^7=$ and $AHP\hspace{1mm}Com^8=$.

2-3- PFR and AHP Commitment.json File Format

{
    "commitment_id": String,
    "iot_developer_name": String,
    "iot_device_name": String,
    "device_hardware_version": String,
    "firmware_version": String,
    "class": 32-bit Integer,
    "m": 
    "n": 
    "p":
    "g":   
        
    // PFR Commitment   
    "PFRrow_A": 
    "PFRcol_A": 
    "PFRval_A": 
    "PFRrow_B": 
    "PFRcol_B": 
    "PFRval_B":
    "PFRrow_C": 
    "PFRcol_C": 
    "PFRval_C": 
    
    "PFR Com0": 
    "PFR Com1":
    "PFR Com2": 
    "PFR Com3":
    "PFR Com4": 
    "PFR Com5":
    "PFR Com6":
    "PFR Com7":
    "PFR Com8":

    // AHP Commitment
    "AHProw_A":
    "AHPcol_A": 
    "AHPval_A": 
    "AHProw_B": 
    "AHPcol_B": 
    "AHPval_B": 
    "AHProwC_": 
    "AHPcol_C": 
    "AHPval_C": 
    
    "AHP Com0": 
    "AHP Com1": 
    "AHP Com2": 
    "AHP Com3": 
    "AHP Com4": 
    "AHP Com5": 
    "AHP Com6": 
    "AHP Com7": 
    "AHP Com8":  
    
    "curve": String,
    "polynomial_commitment": String
}