For developers like myself, understanding cryptography is like dark magic. The problem lies with the fact that there’s no resource which balances the mathematics and technicalities of ideas in an easy-to-understandable manner. Facing this problem first hand, I decided to start this series to consolidate my learning, but also help various developers in their journey of understanding cryptography.
In the previous post, we started with the CI proof systems and their need in the blockchain ecosystem. We have also discovered the general steps of constructing a proof system and what is the need of using ZK-friendly hash functions.
The discussion so far has focused on symmetric cryptography and zk-friendly hash functions. We have also briefly understood the construction of a poseidon hash function with a low degree polynomial by introducing the non-linear random layers in its construction. Moving forward, we now will understand the cryptography behind asymmetric primitives and its underlying methods. In the end we will compare both primitive system on the basis of:
- Computational Efficiency
- Size of Proof
- Transparency
- Post quantum security
To keep things straightforward, I’ll begin by establishing the fundamental principles of asymmetric cryptography, encompassing concepts like groups, finite fields, and associated mathematical notions. In this article, our focus will primarily be on introducing the initial building block: the Elliptic curve DLP primitive. Subsequently, in the forthcoming series, we will delve into other primitives such as Bilinear mapping, Knowledge of exponentiation, and groups of unknown orders.
But first what do we mean when we say asymmetric cryptography?
What is Asymmetric Cryptography?
Most of the cryptographic systems today are existing on the foundations of asymmetric encryption also known as public key cryptography. These Encryption keys are generated in mathematically-related pairs — public and private keys. Asymmetric cryptographic schemes, such as Diffie-Hellman (DH), allow parties to establish a shared secret over an insecure communication channel without exposing their private keys. Typically, the prover needs to convince the verifier that a certain statement is true without revealing the underlying secret information. Asymmetric cryptography enables the prover to create cryptographic evidence (such as digital signatures or commitments) that can be verified without requiring the prover to disclose their secret inputs.
In Zero-Knowledge (ZK) protocols, certain key terminologies will frequently surface. So to ensure a solid foundation, we’ll begin by gaining a fundamental understanding of a few mathematical and computational concepts before delving into our core topic of asymmetric primitives. For example, the Diffie-Hellman key exchange protocol relies on the mathematical properties of groups to allow two parties to securely establish a shared secret key over an insecure communication channel.
Diffie-Hellman Key Exchange
Imagine that we have a communication protocol where Alice and Bob want to exchange some shared secret on the network. To do that, Alice first selects a private number say 15 and take its exponent 3¹⁵ mod 17≡ 6. Alice sends this value 6 publicly to the network.
The generator 3 and p (mod 17) are public to the network.
Similarly Bob selects his secret number say 13 and calculates 3¹³ mod 17≡ 12 and sends this value to the network too. Now the heart of the trick is Alice takes Bob’s public result and raises it to the power of her private number to obtain the shared secret which in this case is 10.
12¹⁵ mod 17≡ 10
Similarly Bob takes Alice’s public value and raises it to his secret value resulting in the same shared secret: 6¹³ mod 17≡ 10. You have observed that we have used prime modulus such as 17 to carry out the secret communication between Alice and Bob. This prime modulus builds us a ground for achieving the hardness(one way functionality) in our system.
For example, If we find a primitive root of 17, which in this case is 3 we could achieve the hardness in function. This value has an extraordinary property which states that when this is raised to different exponents, the solution is likely to be any value between 0 to 17. This is defined as “modular arithmetic” or clock arithmetic.
3⁴ mod 17≡ 81 mod 17≡ 13
Note: This primitive root is also known as generator point. You can find this primitive root by using the GCD method.
Discrete Log Problem
Now the reverse procedure is hard, say with the given value of 12, find the exponent.
For this we have to perform a trial and error method which may be easy for small prime numbers but a poly-time machine will have no possibility of breaking it with large prime modulus (i.e 289283939485959594949) unless we have quantum computers. This is called the “Discrete log problem”. The security of many cryptographic algorithms hinges on the hardness of the underlying mathematical problems. The discrete logarithm problem is considered “hard” in certain groups, meaning that there’s no efficient algorithm to solve it in general, making it a suitable foundation for secure cryptographic schemes. Digital signature algorithms, such as the Digital Signature Algorithm (DSA) and the Elliptic Curve Digital Signature Algorithm (ECDSA), leverage the discrete log problem.
Groups
In the above example of Diffie-Hellman, Alice and Bob must have agreed on a specific mathematical group, often a multiplicative group modulo a prime number. The parties agree on public parameters, including the group’s modulus (p) and generator(g).
The generator is an element in the group that can generate all other elements by repeated multiplication.
By selecting a suitable group and performing specific calculations within that group, the protocol ensures that both parties derive the same shared key without revealing it to eavesdroppers. Groups are algebraic structures that have well-defined operations and properties.
- Closure: for a and b in a group, the a.b will also be in the similar group.
- Associativity: for a, b, c in a group, (a.b).c= a.(b.c) is also in group.
- Identity: for all a in a group, a.I =a is also in a group.
- Inverse: Every a has an inverse b such that, a.b=I.
- Commutativity: Some groups have an additional property of a.b= b.a, they are often called abelian groups.
Note: The operation dot(.) is subjective here. In the above example(DHKE) the group we’re working with is the multiplicative group modulo 17, denoted as Zp*. The prime value 17 could be denoted as a finite field Fp.
Finite Fields
Finite Fields, also known as Galois Fields, are the basic fundamental for understanding any cryptography including Zk. A field can be defined as a set of numbers that we can add, subtract, multiply and divide together to get another value in the group. So, if we have a group of 0 to 17 we can constrain our values with a (mod p) operation. In our case it would be 17. This is particularly useful for cryptography as we can deal with a limited set of extremely large numbers.
Note: Groups can be finite or infinite. While finite fields have group structures, not all groups are finite fields. A finite field is a more specific mathematical structure that falls under the broader concept of groups.
The finite field follows the same properties as groups however, an additional property they follow is p^m(where p is a prime number and m is the power of base). For example, a finite field with 256 elements would be written as GF(2⁸). With this in mind, you must know that you can’t have a field with 12 or 15 elements as you can’t represent them in the base power method.
With our notation of GF(p^m):
- If m=1 then we get prime fields.
- If m>1 then we get extension fields. This is important as this is what we are going to use for our elliptic curves down the line.
Prime Field Arithmetic
We represent the prime field as GF(p) means we have a finite field with integers {0, 1, 2, . . . , 16}. If we put into action we would return a closure property.
This looks seemingly fine until we want to represent our field without starting with an index 0. Meaning F¹⁷={1, 2, 3, . . . .}. We need this because 0 doesn’t have any inverse. This introduces us to extension fields.
Extension Fields
Unlike finite fields, whose elements are integers, extension fields’ elements are polynomials. Extension field = GF(2^m) where m>1. These polynomials take the form of:
To understand this, let’s take an example of GF(2³) which will result in the equation form representing there would be total of 8 elements in the field:
Putting it all together,
By looks this might seem like little different from our integers, but even on extension field we can perform our arithmetic operations such as:
If we take our A =x²+1 and B= x²+x+1,we can reduce it to:
(1+1)x²+x+(1+1)
And we know that 1+1 mod 2=0 so putting 0 at the above equation we will get x only which exists in our set and hence we get a closure property. However, what if after performing some operation on a field, we get a value which is not in our field?
In the above example, we get the equation x⁴+x³+1. This does not exist in our field so what are we gonna do ?
In the case of GF(2³) Our irreducible polynomial is x³+x+1. If we divide x⁴+ x³+1 with our irreducible prime, we ultimately get x²+x which exists in our set — great!
This indicated that finite fields have specific algebraic structures that can’t be directly mapped to the properties of real numbers. For example, FFT algorithms can be adapted to finite fields to perform polynomial multiplication efficiently, which is a common operation in certain cryptographic algorithms and error-correcting codes.
Till now, we have cleared all the raw concepts regarding computational hardness and how it makes our system secure from malicious parties. Furthermore, we have also discussed how groups, modular arithmetic and finite fields play their role in our cryptic functions. Now it’s the time to go deeper in our main topic of cryptographic assumptions that we need for our ZKP systems.
To learn more about finite fields, check this link.
Asymmetric Primitives
With reference to our previous article, we now move towards the asymmetric primitives which are widely used in zero-knowledge proof systems. We will first start with Elliptic Curve DLP.
Now, I searched around the internet a-lot and found so many explanations regarding the topic but each explanation has a different style and a less focus on its critical points. So I am gonna explain the topic as simply as I could while keeping in mind the technicalities behind the topic such as security assumptions.
Elliptic Curve Cryptography
This is a cryptographic system that is based on elliptic curves over finite fields where a randomly selected private key is used to easily generate a public key but where the reverse direction is computationally difficult/impossible.
An Elliptic Curve equation could be defined as:
y²=x³+ax+b
For example let a= -3 and b=5, the graph will look like:
First let’s pick two random points with different x values on the curve. Then connect these points with a straight line say A to B, you will now see that the line will connect to another point in the middle. Once we find that third point and flip its y value to the other side of the x axis, let’s call it A+B.
Well, let’s do the trick again. This time from point A+B to another point on curve C.
Keep repeating the same tick again and again by adding a new point to get a new sum, as long as the new line is not vertical. We can repeat this method over multiple times.
However, another tangent line method would be a tedious choice. For example consider a point P over a curve. No you make a tangent drawn from that point. This will touch another point on the curve and if we reflect that point to the downward axes we can have our second point 2P. We keep repeating the steps till NP point.
Now here comes an interesting question, given the coordinates of a point NP, can we find out the number over which we’ve jumped from point P to NP? Like how many tangents have we drawn? I can tell you the number i selected but you won’t be able to guess or brute force unless the number I selected has been really small.
Heart of the Trick
You may be wondering what if the attacker did the same? If he knows our P and NP point he can add point P to itself over many times until he gets the NP. Then he has our secret number of iterations.
The elliptic curves have some phenomenal characteristics. The point on the curve follows group law. Yay!!! for this day we have covered the group’s topic. The idea is simple, which we have discussed earlier which means you can perform addition and multiplication operations while still remaining in the group. For example let’s understand this through the lens of associativity property.
Also note, here we can only apply add, sub and multiply. We haven’t talked about division which we will discuss later.
Associativity= (A+B)+C = A+(B+C)
We either perform the first equality method or the second we will reach the same point. Here I found a simple example from an article I followed for this series.
You can see from the above example that ab_c and a_bc are both identical with a minor floating point value difference due to rounding errors.
So we can say that P+ 3P= 4P which is the same as 2P+ 2P= 4P
See? Both ways lead to the same result. This is it, since we can double a point easily, and the order of adding it doesn’t matter. This means we don’t need to add the previous points to get a new point. We can simply keep doubling the point and pick the power of the point.
Elliptic Curve DLP
Now with the understanding we have built above, let’s try to perform computations over a big number, say 227P. Means I am gonna add P to itself 227 times ?? well NOO 😀
We represent the 227P as in its exponent form and add all the powers i.e:
2⁷P+2⁶P+2⁵P+2¹P+2⁰P
128P+64P+32P+2P+P=(128+64+32+2+1)P=227P
What we did here is called double and add which has significantly reduced our steps of computation hence fast proof generation time. The number 227 in this example is small, even the number is as big as the number of atoms in the universe, say 10⁸², which is around 2²⁷⁵, this method can still finish calculating it in 275 double-and-add steps. With this method we can now jump over gazillion times to achieve security and make it nearly impossible for the attacker to find out how many times we jump. This is what we define as the Elliptic Curve Discrete Logarithm Problem.
Need of Finite Fields Over Elliptic Curve
So far, we have been talking about Elliptic Curve Cryptography with real number calculations. Though performing calculations over real numbers is easy, that’s not how real world cryptography works.
In the real world, using real numbers causes many problems such as the one with floating point rounding error we saw above.
Finite fields save us in this regard. We perform complex calculations over a finite field of integer modulo p, where p is the prime number.
Go through this Tutorial or the correspondence articles for a better understanding. To explain elliptic curve on finite field of integers modulo p in math:
y²=x³+ax+b (mod p)
Where p= 19 and a= -3 and b=5, the curve will look like this:
y² mod(p)= x³+ax+b at point (y,x)=(11,7)
(7)²(mod 19) ≅ 49 (mod 19) ≅ 11 =(11³–3*11+5)(mod 19) ≅ 11
As both sides have the same remainder 11 divided by 19, so that’s indeed a point on the curve. While it doesn’t look like a curve, it does follow the same group law like the one on real numbers. Let’s see an example, set point A=(3,2) and B=(5,18), and calculate A+B with the same sum operation.
It is the most special thing about this curve on a finite field, when a line hits the boundaries, it can actually warp around to the other end, as the modular operation is circling around. The line will hit the third point somewhere, just like the curve on the real number does.
In the end, as the finite field only operates on integers, we won’t lose any precision. Hence, that why it’s more suitable for cryptographic purposes.
Final Thoughts
That’s all for Elliptic curves. Now you know all the basics or perhaps more about how ECC cryptography works. Finally in the next article I would quickly try to explain the concepts of bilinear mapping and other primitives in detail. Hopefully, you have built a basic intuition of cryptographic primitives till now. See y’all in the next one.
References
- Ochekliye Enigbe, 2022, Elliptic Curves and the Discrete Log Problem
- Practical cryptography for Developers (Gitbook)
- Fang-Pen Lin, 2019, Elliptic Curve Cryptography Explained
