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 utilizes the following three protocols:
A univariate polynomial commitment scheme is a commitment scheme for F≤d[X], the univariate polynomials with maximum degree d∈N and coefficients in the field 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).
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.
Setup(1λ,N): This function outputs pp=PC.Setup(1λ,d) where λ is security parameter and d={dAHP(N,i,j)}i∈[kAHP]⋃{0},j∈[sAHP(i)]⋃{df(N,i,j)}i∈[kf],j∈[sf(i)]. Also N is the maximum supported index size, kf is the number of rounds in PFR, sf:N→N where sf(i) is the number polynomials that the Prover sends to the Verifier in round i of PFR, and df:N3→N where df(N,i,j) is the degree bound for jthpolynomial that the Prover sends to the Verifier in round i of PFR , and sAHP:N→N where sAHP(i) is the number polynomials that the Prover sends to the Verifier in round i of AHP, and dAHP:N3→N where dAHP(N,i,j) is the degree bound for jth polynomial in round i of AHP.
Note that sAHP(0)=sf(0) and for all i∈[sAHP(0)], dAHP(N,0,i)=df(N,0,i).
Also, there are kAHP=4 rounds in AHP where in
Round 0: sAHP(0)=9
dAHP(N,0,j)=m for j∈[sAHP(0)]=[9]={1,2,..,9},
Round 1: sAHP(1)=4
dAHP(N,1,1)=∣w∣+b, dAHP(N,1,2)=∣H∣+b, dAHP(N,1,3)=∣H∣+2b−1, dAHP(N,1,4)=2∣H∣+b−1,
Round 2: sAHP(2)=2
dAHP(N,2,1)=∣H∣−1, dAHP(N,2,2)=∣H∣+b−1,
Round 3: sAHP(3)=2
dAHP(N,3,1)=∣H∣−1, dAHP(N,3,2)=∣H∣−1,
Round 4: sAHP(4)=2
dAHP(N,4,1)=∣K∣−1 and dAHP(N,4,2)=6∣K∣−6, therefore{dAHP(N,i,j)}i∈[kAHP]⋃{0},j∈[sAHP(i)]={m,m,m,m,m,m,m,m,m,∣w∣+b,∣H∣+b,∣H∣+2b−1,2∣H∣+b−1,∣H∣−1,∣H∣+b−1,∣H∣−1,∣H∣−1,∣K∣−1,6∣K∣−6}
where n=ng+ni+1 and m=2n2−n−2t2−t is maximum of number of non-zero entries of matrices A, B and C corresponding with arithmetic circuit with ng gates and ni inputs. Also, H and K are multiplicative subgroups of field F with order m and n, respectively. Also, t=ni+1 and b is a random number of {1,2,..,∣F∣−∣H∣}.
For example, if polynomial commitment scheme KZG is used, pp=KZG.Setup(1λ,d)=(ck,vk)=({gτi}i=0d−1,gτ) where ck and vk are commitment key and verifying key, respectively. Here τ is a secret element and must be discarded after the Setup. Also, g is a generator of field F with large prime order p such that log(p)=Ω(λ) and d is maximum degree of polynomials that wants to commit them.
Setup(1λ,N): This function outputs pp=PC.Setup(1λ,d) where if ng=3 , ni=1 and b=2 then d={dAHP(N,i,j)}i∈[kAHP]⋃{0},j∈[sAHP(i)]={9,9,9,9,9,9,9,9,9,4,7,8,11,4,6,4,4,8,48}.
Run KZG.Setup(1λ,d) as following:
If the computation be done in F of order p=181, a generator of F is g=2.
KZG.Setup(1λ,9)=(ck,vk)=({gτi}i=08,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=08=(2,66,83,91,96,24,2,66,83) and vk=66.
KZG.Setup(1λ,4)=(ck,vk)=({gτi}i=03,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=03=(2,66,83,91) and vk=66. .
KZG.Setup(1λ,7)=(ck,vk)=({gτi}i=06,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=06=(2,66,83,91,96,24,2) and vk=66.
KZG.Setup(1λ,8)=(ck,vk)=({gτi}i=07,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=07=(2,66,83,91,96,24,2,66) and vk=66.
KZG.Setup(1λ,11)=(ck,vk)=({gτi}i=010,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=010=(2,66,83,91,96,24,2,66,83,91,96) and vk=66.
KZG.Setup(1λ,6)=(ck,vk)=({gτi}i=05,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=05=(2,66,83,91,96,24) and vk=66.
KZG.Setup(1λ,48)=(ck,vk)=({gτi}i=047,gτ) that for secret element τ=119 and generator g=2 outputs ck={gτi}i=047=(2,66,83,91,96,24,...,2,66,83,91,96,24) and vk=66.