Introduction
In my previous research we discussed about Lattice-based cryptography and now we will use lattice cryptography to built our zero knowledge proof of knowledge in which we will introduce ‘-protocol. Then we will use Fiat Shamir with aborts to obtain two variants: one exact protocol and other approximation protocol. We then use the sigma’-protocol to prove knowledge of openings of commitment and linear relation on opening, we also construct a proof or dis-junction of statement. We present a proof that the opening of a message belongs to a subset of R that is fixed by the set of automorphisms. Lastly we present the exact proof with constant overhead of a lattice based one way function, this proof is efficient and requires the equation to be amortised.
Zero Knowledge Proof of Knowledge:
A zero knowledge proof of knowledge is commonly abbreviated as ZKPoK is an interactive protocol in which prover P has to convince the verifier V that the knowledge he has is correct without revealing any information about the statement. In order for ZKPoK to be efficient it needs to have the following three properties.
- Completeness: A prover with witness s where t belongs to the set L can convince the verifier.
- Soundness: A prover can not state that information if t does not belong to L.
- Zero Knowledge: The interaction should not reveal anything to the verifier except that t belongs to L.
Exact and Approximate ZKPoK:
- Sigma’ Protocol:
Our sigma’ protocol will be a one way function where we have small preimages s belongs to Rm for an image t that belongs to Rqn with a random matrix A belongs to random matrix of Rqmxn. We represent the sigma’ protocol with the following relation.
Where C– is the set of different elements C except for 0. If we suppose that R is equal to Z then our challenge set would be fixed to {0,1} and since C– does not includes 0 hence it is equal to C– =[1] which gives the protocol of sounding ½. If we suppose that R is a polynomial ring then the size of C increases and hence the the size of our C– and the soundness of the protocol will increase to 1/|C|. Where our protocol will look like below.
Let’s talk about the correctness of the Sigma’ protocol.
Correctness: we know that from the previous publication that sigma is greater than and equal to 11BcB and 11BcB is greater than and equal to 11||sc|| the rejection step will accept the probability that is close ⅓ and vector z output will be statistically be closed to DR,sigmam . It is clear that in honest protocol response is computed in such a way that the verification equation Az = tc + w holds.
Special Soundness:
Let w,c,z and w,c’,z’ be two accepting transcripts with c c’. Let z= z-z’ and c = c-c’ by correctness we have 
with 
and ||z|| is less and equal to 2B’.
Honest Verifier Zero Knowledge:
Here we prove that accepting transcripts do not leak any information. We make sure that our protocols are non interactive proof based on Fiat Shamir transform. In which case only accepting transcripts will matter since aborting the runs will result in nothing. Moreover the protocol can be made zero knowledge for non accepting transcripts by sending B(w) where we have B as a commitment instead of w and then we send the opening commitment in the flow. Therefore, we design the following PPT algorithm.
It is clear that z verifies with the overwhelming probability. We already showed in our proof of correctness that in the real protocol no aborts occurs the distribution of z is with in the
statistical distance DR,sigmam . Since the value of w is determined by A,z,t and c, the distribution (w,c,z) output by S is within distance 2-100 of the distribution of these variables in this protocol.
Our main concern will be the communication overhead which would depend on the soundness error. Which needs to be repeated 
times to achieve the desired soundness. Thus it will multiply the overhead with the same amount. Another important feature of lattice based zero knowledge will be the slack protocol which will be defined as ||z|| / ||s||. The slack of the proof will help us to set parameters, for example when proving the preimage for the one way function defined as A Rqnxm . We thus want this function to be hard enough for s as well as for z otherwise the knowledge would be easily extracted by the extractor. Hence a large slack will imply larger parameters and in turn larger overhead. Finally the computation complexity comes from one way function evaluation and Gaussian sampling.
ZKPoK over the integers: Let us consider a ring R= Z where our challenge space will be C= {0,1}. We could assume a bigger sample space for the better soundness error since the slack protocol depends on the bound error Bc on the norm of the challenges which would grow linearly with size of the challenge space which would result in the exact proof of knowledge with the soundness of ½ and slack of 11(2dm)1/2. The main problem that occurs here is constant soundness. Where ZKPoK is needed to be repeated lambda times to achieve the overwhelming soundness error which will result in large impractical proof.
ZKPoK over Polynomial Rings:
Now let us consider a ring in a larger dimension that one can obtain by a new tradeoff. Let us consider Z= [X]/Xd+1 where d is a power in terms of two let us consider a challenge space C =
Using such a challenge gives us approximate proof of knowledge.with a soundness error of 
and slack of 11k(2dm)1/2 the bound k is chosen so that protocol attains the overwhelming soundness. The above challenge set helps us to attain the desirable result without any repetition.
- Application to Commitment:
Proof of Opening: We suppose the commitment t is defined as below
The soundness extractor 
will extract the tuple 
belongs to R’. By the definition of opening of commitment we can say that 
are the valid opening for the message 
as long as ||r|| is less than equal to 2B’ and 2B’ is less than and equal to BCOM Similarly we can prove knowledge of an opening to a specific message m by proving knowledge of pre-image 
such that 
Proof of Linear Relation:
We now have to consider how to prove the messages of two commitments verify certain linear relations. So let us consider u,v belongs to R, t= Com(m;r) and t’=Com(m’;r’) and now we have to proof um+vm’=0 therefore we consider the following relation
Such a proof can be obtained by applying the proof one-way functions to a well chosen matrix B stated as below
Observe that if our commitment scheme is binding for randomness of norm less than B then
The protocol piOWF 
OR-Proofs:
Given sigma protocol for two relation R0 and R1 one can prove that he knows a witness for either t0 belongs to L(R0) or t1 belongs to L(R1) without revealing which is mandatory in zero knowledge. Let b belong to {0,1} be such that P knows sb with (tb,sb )Rb The prover first computes a transcript using the simulator of the relation which remains unwitnessed . then the he uses the c-c1-b as a challenge whose witness is known, where c1-b is used by the simulator and c is the challenge sent by the verifier. This protocol is assumes that the challenges form a group as the verifier should not be able to differentiate whether the prover computed c0=c-c1 or c1=c-c0 The challenge space used in lattice based ZKPoK typically does not have this property; to remedy this we will use C and apply an ad-hoc group law. That is stated below.
We now discuss how to obtain a computable group law over the challenge space.
Lemma: Let A belongs to Rqnxm, t1,….tl Rnq, s belongs to Rqm and i belongs to [l] such that ti := As and ||s|| is less than and equal to B let 
and B’ is greater and equal to (2m*d*sigma)1/2 The protocol 
is a sigma’ protocol for the above mentioned relations. With the success rate of ⅓ and the soundness of 1/|C|
Correctness: Using lemma we know that sigma is greater than equal to 11 BcB and 11 BcB is greater than equal to ||sci|| the rejection step will accept with probability overwhelming probability overwhelming close to ⅓ and the vector zi output will be statistically close to 
for i is not equal to j the vector zj comes exactly by In our previous publication we have discussed j belongs to [l] , ||zj|| is less than and equal to (2m*d*sigma)1/2 which is less than and equal to B’ with the overwhelming probability. It is clear that in our honest protocol the response is computed in such a way that the verification equation stands.
Special Soundness:
Consider two accepting transcripts (w1,…..wl,c,z1,…zl,c1,…,cl) and(w’1,…..w’l,c’,z’1,…z’l,c’1,…c’l) with cc’. Since cis not equal to c’ therefore we can say that i belongs to [l] such that ci is not equal to c’i Let 
and 
by correctness we have 
where 
belongs to challenge space norm of 
is less than equal to 2B’.
Honest Proof Verifier: We work on the transcripts that do not leak information. Let S(A,t1,….tl) be the following PPT algorithm.
It is clear that the transcript is satisfied with an overwhelming probability by the simulator. We have discussed before in the proof of correctness that in real protocol when no abort occur the distribution of zj is with in the statistical distance of 2-100 of for all j belongs to [l]. Since C is a group for 
the vector (c1,….,cl) is sampled uniformly over Cl conditioned on cj=c in both simulator and the real protocol. Since we have determined (w1,….wl) is completely determined by A,t1,….tl,z1,….zl, c1,….cl and c. the distribution of the transcript output by S is within the statistical distance of 2-100 of the distribution of the one in the actual protocol.
Subset Membership Proof:
Now let us consider a different approach to the concept of Zero knowledge since we have been working in rings we be proving that message will belong to the subring Sq of Rq by using the Chinese remainder theorem. For instance let us suppose that Xd+1 split into Xd+1=fg mod q then we would assume that Sq = f Rq= {fx:x Rq} and prove that t commits to m belongs to Sq using the linear relation which is discussed above in OR proof. We thus prove that the message m belongs to Rq is a subring Sq of Rq with invertible elements to do so we will use automorphism of R.
Galois Group Structure of Cyclotomic Rings.
Consider the following relation 0 is less than and equal to i which is less than and equal to 2d: 
The 
is the so called of R2. 
is group for composition
And the only subset of R that is fixed by sigma is Z (i.e. polynomial of 0)
As a group is isomorph to Z*2d is approximately equal to (Z2)(Zd/2)and therefore it is generated by two elements, these elements are 
and 
From this we know that the only element in of that is fixed by both 
and 
are the constant polynomial. To obtain a larger subring we can consider the elements that are fixed by the subgroup of for any power of two k<d we have
Therefore we can obtain a subring R of dimension k of any power that should be two less than d. Where R is not trivial for Rq the set will remain the automorphims of Rq but it is possible that we have an element for instance u that belongs to Rq and it is present in both and but it is not a constant. But we can resolve this issue if we have a well chosen modulus q that is stated as
We can now prove that a message is in a subring dimension of k by proving that it is fixed in both and . Furthermore, such subrings only consists of invertible elements and have a Zq-basis and has a power of efficiently computable polynomial where alpha belongs to Rq i.e
Proving Stability Under Automorphism:
We now discuss the stability of ZK under automorphism. Here we first discuss that the proof of knowledge open up a commitment to a message m that belongs to Rql that is invariant under the set of automorphism. 
As a special case we show that m belongs to Zlq by proving that it is invariant under two automorphism
Below is the proof that the opening of a commitment is invariant under the set of automorphism
Theorem: Now let us suppose that ||r|| is less than and equal to BAut. Let S be a set of automorphisms of size |S|. Let 
and 
If Bcom less than equal to 2B’Aut then the protocol pi auto(A,t,S;s,m) in above algorithm is a sigma’ protocol for relations Rauto and R’auto with a success property of of ⅓ and soundness of 1/|C|
The above argument for correctness and zero-knowledge are identical to the ones in Sigma’ Protocol. Let us suppose (w1,w1,j,w2,j,,c,z,zj) and (w1,w1,j,w2,j,,c’,z’,z’j)are the transcripts where j belongs to S. We will prove that there exist a message m such that 
is a valid opening of a column matrix t1 and t2 and for all j belongs to S, 
For a fixed j belongs to S, Let 
and 
by taking the difference of the verification of both the transcripts we get the following results:
If we apply automorphism 
to the above equation we have 
or equivalently 
we multiply our third equation by (c) and take the difference to get
Using verification we have that 
and 
which implies
Since
has an inverse in Rq we can state that 
such that 
by substituting this value in above equation we have 
We can say that we have extracted the following equation
Where we have and the same argument can be applied to the other elements when j belongs to S.
Conclusion:
Throughout this study, we have discussed Fiat Shamir with Aborts and techniques that can help us build zero knowledge and zero-knowledge proof on lattice-based cryptography, which helps create an efficient lattice-based privacy protocol.
References:
- Efficient lattice-based Zero Knowledge ( January 20, 2020) Rafael Del Pino.
https://tel.archives-ouvertes.fr/tel-02445482/document
You can read about lattice based cryptography here.
