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:-
Screenshot 2021-10-22 at 12.29.46 AMScreenshot 2021-10-22 at 12.30.24 AM
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:-
Screenshot 2021-10-22 at 12.32.00 AMwhereScreenshot 2021-10-22 at 12.29.21 AM
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:
Screenshot 2021-10-22 at 12.35.09 AM
Proof:-
Both a and b can be written as:-
Screenshot 2021-10-22 at 12.35.55 AM
Substituting these values of a and b in right side of the equation, we get:-
Screenshot 2021-10-22 at 12.36.28 AM
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:
Screenshot 2021-10-22 at 12.40.30 AM
Proof:-
Substituting the previous values of a and b in left side of the equation, we get:-
Screenshot 2021-10-22 at 12.41.13 AM
Substituting in right side of the equation, we get:-
Screenshot 2021-10-22 at 12.44.38 AM
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:
Screenshot 2021-10-22 at 12.49.19 AM
Proof:-
Expanding the left side of the equation, we get:-
Screenshot 2021-10-22 at 12.50.12 AM
Using the property 2 of modulo multiplication defined previously, we can write:-
Screenshot 2021-10-22 at 12.50.59 AM
Which is the same as the right side of the equation.

Property 2:
Screenshot 2021-10-22 at 12.53.03 AM
Proof:
Expanding the left side of the equation, we get:-
Screenshot 2021-10-22 at 12.53.51 AM
Using the property 2 of modulo multiplication defined previously, we can write
Screenshot 2021-10-22 at 12.54.29 AM
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

3 Likes

This is awesome! Thanks for sharing

1 Like