1- Setup Phase

The first phase in our system is the setup phase. This phase should be run by a trusted party.

The setup phase is crucial for generating the necessary cryptographic parameters. During this phase, a trusted party generates public parameters, $pp$. We have defined 18 setting classes for our proving system.

Fields utilized in ZKP:

• (Goldilock- $\phi$): $p=\phi^2-\phi+1$ where $\phi^2 = \phi-1 \hspace{1mm} mod \hspace{1mm} p$

• (Sophie Germain- $\phi$): a prime number where both p and (2p+1) are prime. $\phi^2 = \phi-1 \hspace{1mm} mod \hspace{1mm} p$

Condition for the field utilized in function-hiding ZKP system:

• $m | (p-1)$ and $n | (p-1)$

Class	Number of gates, ng	Number of inputs, ni	n=ni+ng+1	m=2*ng	Field size, prime number p	Condition for function-hiding system ZKP	Generator, g
1	2	32	35	4	(Goldilock-1261) = $(1261)^2-1261+1 = 1,588,861$	4 | (1,588,861 -1 ) 35 | (1,588,861 -1 )	17
2	4	32	37	8	(Goldilock-1296) = $(1296)^2-1296+1 = 1,678,321$	8 | (1,678,321-1 ) 37 | (1,678,321-1 )	11
3	8	32	41	16	(Goldilock-2256) = $(2256)^2-2256+1 = 5,087,281$	16 | (5,087,281 -1 ) 41 | (5,087,281 -1 )	17
4	16	32	49	32	(Goldilock-1569) = $(1569)^2-1569+1 = 2,460,193$	32 | (2,460,193 -1 ) 49 | (2,460,193 -1 )	5
5	32	32	65	64	(Goldilock-2496) = $(2496)^2-2496+1 = 6,227,521$	64 | (6,227,521 -1 ) 65 | (6,227,521 -1 )	7
6	64	32	97	128	(Goldilock-3201) = $(3201)^2-3201+1 = 10,243,201$	128 | (10,243,201 -1 ) 97 | (10,243,201 -1 )	21
7	128	32	161	256	2,060,801 (Sophie Germain)	256 | (2,060,801 -1 ) 161 | (2,060,801 -1 )	3
8	256	32	289	512	14,056,961 (Sophie Germain)	512 | (14,056,961 -1 ) 289 | (14,056,961 -1 )	11
9	512	32	545	1,024	138,403,841 (Sophie Germain)	1,024 | (138,403,841 -1 ) 545 | (138,403,841 -1 )	15
10	1,024	32	1,057	2,048	270,592,001 (sophie Germain)	2,048 | (270,592,001 -1 ) 1,057 | (270,592,001 -1 )	15
11	2,048	32	2,081	4,096	272,760,833 (Sophie Germain)	4,096 | (272,760,833 -1 ) 2,081 | (272,760,833 -1 )	13
12	4,096	32	4,129	8,192	14,071,103,489 (Sophie Germain)	8,192 | (14,071,103,489 -1 ) 4,129 | (14,071,103,489 -1 )	3
13	8,192	32	8,225	16,384	673,792,001 (Sophie Germain)	16,384 | (673,792,001 -1 ) 8,225 | (673,792,001 -1 )	17
14	16,384	32	16,417	32,768	59,174,748,161 (Sophie Germain)	32,768 | (59,174,748,16 -1 ) 16,417 | (59,174,748,16 -1 )	3
15	32,768	32	32,801	65,536	236,461,096,961 (Sophie Germain)	65,536 | (236,461,096,961 -1 ) 32,801 | (236,461,096,961 -1 )	3
16	65,536	32	65,569	131,072	42,971,299,841 (Sophie Germain)	131,072 | (42,971,299,841 -1 ) 65,569 | (42,971,299,841 -1 )	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,ProofGeneration, ProofVerification)$ that contains two major phases, proof of function relation (PFR) phase and algebraic holographic proof (AHP) phase.

Major Phase 1 - A proof of function relation (PFR)

A proof of function relation, $PFR$, shows that a committed relation is a function.

Major Phase 2 - An algebraic holographic proof (AHP)

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

Both PFR and AHP will be compiled to a standard interactive protocol using a univariate polynomial commitment, $PC$, scheme. A $PC$ is a commitment scheme for $\mathbb{F}^{\leq d}[X]$ 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.Setup,PC.Commit,PC.Eval,PC.Check)$.

In the following section, we will review the setup phase of our system. 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 the set

$d=$ { $d_{AHP}(N,i,j)$ } $_{i=0,1,...,k_AHP, j=1,2,..,s_AHP(i)}^{}$

$\bigcup$ { $d_f(N,i,j)$ } $_{i=1,2,...,k_f, j=1,2,..,s_f(i)}^{}$

where $N$ is the maximum supported index size. Also, considering $d_{AHP}:\mathbb{N}^3\to\mathbb{N}$, $d_{AHP}(N,i,j)$ is the degree bound for $j^{th}$ polynomial in round $i$ of $AHP$. $k_{AHP}$ is the number of rounds in $AHP$. Moreover, considering $s_{AHP}:\mathbb{N}\to\mathbb{N}$, $s_{AHP}(i)$ is the number of polynomials that the Prover sends to the Verifier in round $i$ of $AHP$. Considering $d_f:\mathbb{N}^3\to\mathbb{N}$, $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$. $k_f$ is the number of rounds in $PFR$. Considering $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$.

Note that $s_{AHP}(0)=s_{f}(0)$ and for all $i\in$ { $1,2,...,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$ { $1,2,...,s_{AHP}(0)=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=0,1,...,k_AHP, j=1,2,...,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 $m=2n_g$ is maximum of number of non-zero entries of matrices $A$, $B$ and $C$ corresponding with arithmetic circuit of function $f$ with $n_g$ gates. Also, $\mathbb{H}$ and $\mathbb{K}$ are multiplicative subgroups of field $\mathbb{F}$ with order $m$ and $n$, where $n=n_g+n_i+1$ and $n_i$ is the the size of input $x$. Note that all the computations are in filed $\mathbb{F}$ with order prime number $p$. $b$ is a random number in { $1,2,..,|\mathbb{F}|-|\mathbb{H}|$ }. Also, $w$ are the intermediate values (witness) which are created when executing a program. $|w|=n_g-n_r$ where $n_r$ is the number of components in input $x$ which are changed during the program execution.

For example, if polynomial commitment scheme $KZG$ is used in our scheme, $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 $p > 2^\lambda > d$. Also, $d$ is maximum degree of polynomials that wants to be committed.

The above mentioned system is programmed in C++ and Rust. The code is available at: https://github.com/FidesInnova/zkiot

The output of this code are $ck$ and $vk$ keys stored in a json file and formatted as below.

1-2- Setup.json File Format

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

• class: Represents the configuration's classification. It indicates the number of gates in the ZKP circuit, defining the complexity or size of the cryptographic proof structure.

• ck:(Commitment Key) The Commitment Key is used by the prover to create commitments to the witness (private inputs).

• vk(Verification Key): Used by the verifier to validate the proof against the public inputs and commitments. It allows the verifier to efficiently check the proof without accessing the underlying secret data.

References

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

[2] Marlin Paper: 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] Function-hiding with SIS Paper: 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] Lookup table Paper: Gabizon, Ariel, and Zachary J. Williamson. "plookup: A simplified polynomial protocol for lookup tables." Cryptology ePrint Archive (2020).‏

[5] Lattice-based Function-hiding Paper: 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.

[6] KZG Polynomial Commitment: A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications. In International conference on the theory and application of cryptology and information security, pages 177–194. Springer, 2010.