For developers like me, 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-understand 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 Zero-Knowledge - 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 of 315 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 313 mod17= 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.
1215 mod17= 10
Similarly, Bob takes Alice's public value and raises it to his secret value resulting in the same shared secret: 613 mod17= 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 arithmetics” or clock arithmetics.
34 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.
3? mod17= 12
For this we have to perform a trial-and-error method which may be easy for small prime numbers but a polytime 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 F p.
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 crypto 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
pm (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 (28). 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 (pm):
- 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.
Picture credit: https://medium.loopring.io/learning-cryptography-finite-fields-ced3574a53fe
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 F17={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(2m) where m>1. These polynomials take the form of:
am-1Xm-1+. . . . +a1X1+a o
To understand this, let's take an example of GF (23) which will result in the equation form representing there would be total of 8 elements in the field: A(x)=a 2X2 + a 1X1 + a o
Putting it all together, GF ((23) = {0, 1, x, x2, x + 1, x2 + x, x2 + x, x2 + 1, x2 + x, x + 1}
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 = x2 + 1 and B+ x2 + x + 1 we can reduce it to:
(1 +1)x2 + x + (1 +1)
And we know that 1 + 1 mod2 = 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 x4 + x3 + 1. This does not exist in our field so what are we going to do?
In the case of GF (23) 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 arithmetics 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 alot 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 converse is computationally difficult/impossible.
An Elliptic Curve equation could be defined as:
y2 = x3 + 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.