Understanding Homomorphic Encryption
ZK-SNARKS rely on a certain encryption function called Homomorphic encryption. I believe it’s important to understand the mathematical properties of this particular operator to truly understand ZK-SNARKS and hence I decided to prepare this document. Let us dive deeper.
Definition:-
Where g^x is exponentiation and mod m is the modulo operator.
The Module Operator
Let us understand the (mod m) operator deeper first. If y = x mod m, this means that y is the remainder when x is divided by m. Hence, one could write:-
where q is the quotient when x is divided by m
Let us look at some interesting properties of the mod m operator
Property 1:
Proof:-
Both a and b can be written as:-
Substituting these values of a and b in right side of the equation, we get:-
Substituting the values of a and b in left side of the equation, we get:-
As we can see, both the equations evaluate to the same value.
Property 2:
Proof:-
Substituting the previous values of a and b in left side of the equation, we get:-
Substituting in right side of the equation, we get:-
As we can see, both the equations evaluate to the same value.
The E(x) Operator
Now that we are comfortable with the modulo operator, let us turn our attention back to the E(x) encryption function we defined earlier. E(x) is called an encryption operation since it’s not easy to find the value of x given the value of E(x). Hence, E(x) is a one-way function. The cool thing about E(x) is that it allows us to perform basic arithmetic operations on x, even when only E(x) is known, but x is not known.
Let’s dive deeper into these interesting properties of the E(x) operator:-
Property 1:
Proof:-
Expanding the left side of the equation, we get:-
Using the property 2 of modulo multiplication defined previously, we can write:-
Which is the same as the right side of the equation.
Property 2:
Proof:
Expanding the left side of the equation, we get:-
Using the property 2 of modulo multiplication defined previously, we can write:-
Which is the same as the right side of the equation
This was a basic intro to some of the maths used in ZK-SNARKS. In the next article, I will attempt to create a basic zero-knowledge scheme using the Homomorphic encryption defined here.
References:
Here is an awesome article series by Makesym on ZK technology — Why and How zk-SNARK Works 2: Proving Knowledge of a Polynomial | by Maksym | Medium
