Lattice-Based Cryptography: Zero Knowledge

Published on: Feb 12, 2022

Feb 12, 2022

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:

1. Sigma’ Protocol:

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 belongs to L.

Exact and Approximate ZKPoK:

Our sigma’ protocol will be a one-way function where we have small preimages s belonging to R in m dimensions for an image t that belongs to with a random matrix A belongs to random matrix of R with dimensions of mxn with modulus q. We represent the sigma’ protocol with the following relation.

Where C bar 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 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 11B cB and 11B cB 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 D in dimension of m and modulus of R and sigma. It is clear that an 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 is not equal to 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 the 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 nonaccepting 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 of discrete gaussian of power m. 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 by 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 belongs to R of modulus q and dimensions of m x n. We thus want this function to be hard enough for as well as for 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 B c on the norm of the challenges which would grow linearly with the 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]/(X^d)+1 where d is power in terms of two let us consider a challenge space C ={c belongs to R, ||c||1 = k, ||c|| infinite = 1}.

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 desired result without any repetition.

2. Application to the Opening :

Proof of Opening: We suppose the commitment t is defined as below

which we discussed in our previous publication. One can prove knowledge of an opening simply by using the sigma protocol that we have discussed above. To prove the knowledge of pre-image t1. Consider the following binary relation

The soundness extractor

will extract the tuple

belongs to R’. By the definition of the opening of commitment, we can say r- and c- 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 B COM Similarly we can prove knowledge of an opening to a specific message m by proving knowledge of pre-image

for the matrix A i.e from the proof

we can extract

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

is valid for ZKPoK knowledge extractor in R’

OR-Proofs:

Given sigma’ protocol for two relations 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 (t b,s b ) belongs to R b. The prover first computes a transcript using the simulator of the relation which remains unwitnessed. then he uses the c-c 1-b as a challenge whose witness is known, where c 1-b is used by the simulator and c is the challenge sent by the verifier. This protocol assumes that the challenges form a group as the verifier should not be able to differentiate whether the prover computed c 0=c-c 1 or c 1=c-c 0 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 Rᵐˣⁿᵩ, t 1,….t l belongs to Rᵩⁿ, s belongs to Rᵐᵩ , i belongs to [l] such that t i:= As and ||s|| is less than and equal to B let B𝒸 is greater than equal to the following

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 B cB and 11 B cB is greater than equal to ||sc i|| the rejection step will accept with probability overwhelming close to ⅓ and the vector z i output will be statistically close to Dᵐ sigma

for i is not equal to j the vector z j comes exactly by Dᵐ sigma

In our previous publication we have discussed j belongs to [l] , ||z j|| 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 (w 1,…..w l,c,z 1,…z l,c 1,…,c l) and(w’ 1,…..w’ l,c’,z’ 1,…z’ l,c’ 1,…c’ l) with c is not equal to c’. Since c is not equal to c’ therefore we can say that i belongs to [ l] such that c i is not equal to c’ i Let

and

by correctness we have

where c-ᵢ belongs to challenge space norm of z-ᵢ 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 Dᵐsigma

for all j belongs to [l]. Since C is a group for ⊕ the vector (c 1,….,c l) is sampled uniformly over C^l conditioned on ⊕ c j=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 are proving that message will belong to the subring Sq of Rq by using the Chinese remainder theorem. For instance let us suppose that X d+1 split into (X^d)+1=f g mod q then we would assume that Sq = f Rq= {fx:x belongs to 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 above relation is called of R² where gamma a 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 (Z 2)(Z d/2)and therefore it is generated by two elements, these elements are

and

From this, we know that the only element in R is fixed by both the relations mentioned above and these are the constant polynomial. To obtain a larger subring we can consider the elements that are fixed by the subgroup of gamma for any power of two k

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 automorphism of Rq but it is possible that we have an element for instance u that belongs to Rq and it is present in both the elements mentioned above 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 Rˡᵩ that is invariant under the set of automorphism.

As a special case we show that m belongs to Zˡᵩ 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 B-Aut. Let S be a set of automorphisms of size |S|. Let variance is and equal to B𝒸B-Aut(|S|+1)^(1/2). If B com 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 R auto 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 (w 1,w 1,j,w 2,j,,c,z,z j) and (w 1,w 1,j,w 2,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 on

to the above equation we have

or equivalently

we multiply our third equation by

and take the difference to get

Using verification we have that

and

which implies

Since c- has an inverse in Rq we can state that m- belongs to Rˡᵩ such that

by substituting this value in above equation we have

We can say that we have extracted the following equation

Where we have modulus z- greater than eqaul to B’-aut 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.

Reference:

You can read about lattice based cryptography here.

Written by

Researcher. Providing solutions to the ZK problem through the language of maths.

Similar Articles

January 9, 2021
Uniswap V2 Protocol: Let’s Dive In
Author: Zainab Hasan
January 28, 2021
Flash Ecosystem: An In-depth Explanation
Author: Zainab Hasan
March 15, 2021
Chainlink: An Encyclopedic Study
Author: Zainab Hasan
1 2 3 13

Get notified on our latest Web3 researches and catch Xord at a glance.

    By checking this box , I agree to receive email communication from Xord.
    © 2022 | All Rights Reserved
    arrow-leftarrow-right linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram