1- Setup Phase

The setup phase is crucial for generating the necessary cryptographic parameters. During this phase, a trusted party (or a multiparty computation to minimize trust) generates a common reference string

There are 18 classes in this method.

Class	n_g	n_i	n	m	p	g
1	2	32	35	4	1,588,861 (goldilock)	17
2	4	32	37	8	1,678,321 (goldilock)	11
3	8	32	41	16	5,087,281 (goldilock)	17
4	16	32	49	32	2,460,193 (goldilock)	5
5	32	32	65	64	6,227,521 (goldilock)	7
6	64	32	97	128	10,243,201 (goldilock)	21
7	128	32	161	256	2,060,801 (sophie germain)	3
8	256	32	289	512	14,056,961 (sophie germain)	11
9	512	32	545	1,024	138,403,841 (sophie germain)	15
10	1,024	32	1,057	2,048	270,592,001 (sophie germain)	15
11	2,048	32	2,081	4,096	272,760,833 (sophie germain)	13
12	4,096	32	4,129	8,192	14,071,103,489 (sophie germain)	3
13	8,192	32	8,225	16,384	673,792,001 (sophie germain)	17
14	16,384	32	16,417	32,768	59,174,748,161 (sophie germain)	3
15	32,768	32	32,801	65,536	236,461,096,961 (sophie germain)	3
16	65,536	32	65,569	131,072	42,971,299,841 (sophie germain)	3

Function-hiding functional commitment Scheme

Function-hiding functional commitment scheme enables the Prover to commit to a secret function $f$ and later without revealing any other information about $f$, proves that $y=f(x)$ for public $x$ and $y$. This scheme is a tuple $(Setup,\, Commitment,\hspace{1mm}Proof\hspace{1mm}Generation, Proof\hspace{1mm}Verification)$ that utilizes the following three protocols:

1- A univariate polynomial commitment scheme

A univariate polynomial commitment scheme is a commitment scheme for $\mathbb{F}^{\leq d}[X]$, the univariate polynomials with maximum degree $d\in\mathbb{N}$ and coefficients in the field $\mathbb{F}$. It supports an argument of knowledge for proving the correct evaluation of a committed polynomial at a given point. This scheme is a tuple $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 shows that a committed relation is a function.

3- An algebric holographic proof (AHP)

An algebric holographic proof is scheme where the prover without revealing any information about function $f$, proves that $y=f(x)$ for public $x$ and $y$.

In the following section, we will review the setup phase of the protocol. We also provide an example to clarify the method.

1-1- PFR and AHP Setup

$Setup(1^{\lambda},N)$: This function outputs $pp=PC.Setup(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)]}$. Also $N$ is the maximum supported index size, $k_f$ is the number of rounds in PFR, $s_f:\mathbb{N}\to\mathbb{N}$ where $s_f(i)$ is the number polynomials that the Prover sends to the Verifier in round $i$ of PFR, and $d_f:\mathbb{N}^3\to\mathbb{N}$ where $d_f(N,i,j)$ is the degree bound for $j^{th}$polynomial that the Prover sends to the Verifier in round $i$ of PFR , and $s_{AHP}:\mathbb{N}\to\mathbb{N}$ where $s_{AHP}(i)$ is the number polynomials that the Prover sends to the Verifier in round $i$ of AHP, and $d_{AHP}:\mathbb{N}^3\to\mathbb{N}$ where $d_{AHP}(N,i,j)$ is the degree bound for $j^{th}$ polynomial in round $i$ of AHP.

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)$. Also, there are $k_{AHP}=4$ rounds in $AHP$ where in

Round $0$: $s_{AHP}(0)=9$ $d_{AHP}(N,0,j)=m$ for $j\in[s_{AHP}(0)]=[9]=\{1,2,..,9\}$, Round 1: $s_{AHP}(1)=6$ $d_{AHP}(N,1,1)=|w|+b$, $d_{AHP}(N,1,2)=|\mathbb{H}|+b$, $d_{AHP}(N,1,3)=|\mathbb{H}|+b$, $d_{AHP}(N,1,4)=|\mathbb{H}|+b$, $d_{AHP}(N,1,5)=|\mathbb{H}|+2b-1$, $d_{AHP}(N,1,6)=2|\mathbb{H}|+b-1$, Round 2: $s_{AHP}(2)=2$ $d_{AHP}(N,2,1)=|\mathbb{H}|-1$, $d_{AHP}(N,2,2)=|\mathbb{H}|+b-1$, Round 3: $s_{AHP}(3)=2$ $d_{AHP}(N,3,1)=|\mathbb{H}|-1$, $d_{AHP}(N,3,2)=|\mathbb{H}|-1$, Round 4: $s_{AHP}(4)=2$ $d_{AHP}(N,4,1)=|\mathbb{K}|-1$ and $d_{AHP}(N,4,2)=6|\mathbb{K}|-6$, therefore$\{d_{AHP}(N,i,j)\}_{i\in[k_{AHP}]\bigcup\{0\},j\in[s_{AHP}(i)]}=\{m,m,m,m,m,m,m,m,m,|w|+b,|\mathbb{H}|+b,|\mathbb{H}|+b,|\mathbb{H}|+b,|\mathbb{H}|+2b-1,2|\mathbb{H}|+b-1,|\mathbb{H}|-1,|\mathbb{H}|+b-1,|\mathbb{H}|-1,|\mathbb{H}|-1,|\mathbb{K}|-1,6|\mathbb{K}|-6\}$ where $n=n_g+n_i+1$ and $m=2n_g$ is maximum of number of non-zero entries of matrices $A$, $B$ and $C$ corresponding with arithmetic circuit with $n_g$ gates and $n_i$ inputs. Also, $\mathbb{H}$ and $\mathbb{K}$ are multiplicative subgroups of field $\mathbb{F}$ with order $m$ and $n$, respectively. Also, $t=n_i+1$ and $b$ is a random number of $\{1,2,..,|\mathbb{F}|-|\mathbb{H}|\}$.

For example, if polynomial commitment scheme $KZG$ is used, $pp=KZG.Setup(1^{\lambda},d)=(ck,vk)=(\{g\tau^i\}_{i=0}^{d-1},g\tau)$ where $ck$ and $vk$ are commitment key and verifying key, respectively. Here $\tau$ is a secret element and must be discarded after the $Setup$. Also, $g$ is a generator of field $\mathbb{F}$ with large prime order $p$ such that $log(p) = Ω(λ)$ and $d$ is maximum degree of polynomials that wants to commit them.

1-2- Setup.json File Format

{
    "Class":  32-bit Integer,
    "ck": 64-bit Integer Array,
    "vk": 64-bit Integer
}

References

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

[2] Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., & Ward, N. (2020). Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I 39 (pp. 738-768). Springer International Publishing.‏‏

[3] 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.‏

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

[5] 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.