1- Setup Phase

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)=4$ $d_{AHP}(N,1,1)=|w|+b$, $d_{AHP}(N,1,2)=|\mathbb{H}|+b$, $d_{AHP}(N,1,3)=|\mathbb{H}|+2b-1$, $d_{AHP}(N,1,4)=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}|+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=\frac{n^2-n}{2}-\frac{t^2-t}{2}$ 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- Example

$Setup(1^{\lambda},N)$: This function outputs $pp=PC.Setup(1^{\lambda},d)$ where if $n_g=3$ , $n_i=1$ and $b=2$ then $d=\{d_{AHP}(N,i,j)\}_{i\in[k_{AHP}]\bigcup\{0\},j\in[s_{AHP}(i)]}=\{9,9,9,9,9,9,9,9,9,4,7,8,11,4,6,4,4,8,48\}$.

Run $KZG.\hspace{1mm}Setup(1^{\lambda},d)$ as following:

If the computation be done in $\mathbb{F}$ of order $p=181$, a generator of $\mathbb{F}$ is $g=2$.

$KZG.Setup(1^{\lambda},9)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^8,g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^8=(2,66,83,91,96,24,2,66,83)$ and $vk=66$.

$KZG.Setup(1^{\lambda},4)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^3,g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^3=(2,66,83,91)$ and $vk=66$. .

$KZG.Setup(1^{\lambda},7)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^6,g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^6=(2,66,83,91,96,24,2)$ and $vk=66$.

$KZG.Setup(1^{\lambda},8)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^7,g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^7=(2,66,83,91,96,24,2,66)$ and $vk=66$.

$KZG.Setup(1^{\lambda},11)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^{10},g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^{10}=(2,66,83,91,96,24,2,66,83,91,96)$ and $vk=66$.

$KZG.Setup(1^{\lambda},6)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^5,g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^5=(2,66,83,91,96,24)$ and $vk=66$.

$KZG.Setup(1^{\lambda},48)=(ck,vk)=(\{g^{\tau^i}\}_{i=0}^{47},g^{\tau})$ that for secret element $\tau=119$ and generator $g=2$ outputs $ck=\{g^{\tau^i}\}_{i=0}^{47}=(2,66,83,91,96,24,...,2,66,83,91,96,24)$ and $vk=66$.

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.