This article is the second part of the “Introduction to Zero-Knowledge Proofs” series. In the first part, we learned about the background, definitions, and related concepts proposed by zero-knowledge proofs. Below we will introduce the core mathematical tools in zero-knowledge proofs, including elliptic curves, homomorphic concealment, and polynomial protocol procedures. Due to the length limitation, we will cover it in two parts. This article focuses on elliptic curves and homomorphic hiding.
Core Math Tools
1. Elliptic Curve
Since the proposal of public-key cryptography by Diffie and Hellman in 1976, numerous implementations of public-key cryptography have been proposed, all of which are based on solving a mathematical problem. In 1985, Koblitz and Miller independently used elliptic curves over finite fields to design public-key cryptosystems, and since then, it has become a common method in public-key cryptography. Public-key cryptography systems are generally classified according to the mathematical problems on which they are based, and there are essentially three types:
1.1. Discrete logarithmic problems
If for an integer and ? a ? primordial root of a prime ? number (number theory: how to understand primitive roots – YouTube), a unique exponent can be found such that:
where 0 ≤ ? ≤ ?−1 holds, then the exponent ? is called ? the ? discrete logarithm ? of the base-based modulus.
The discrete logarithmic problem is that when a large prime number ? and one of its original roots are known, it is quite difficult ? to calculate the value ? of if given a .?
1.2. Discrete logarithmic problems on elliptic curves
An elliptic curve is a binary cubic equation.
It can be written in a variety of forms, but the common one is the short Weierstrass form:
The image is shaped like (b=1, a from 2 to -3).
The Koblitz curve family and the Pseudo-Random Curve fall into this category (secp256k1).
There are now two more commonly used forms:
Montgomery form
Edwards form
Take the short Weierstrass form as an example, define point addition:
Definition 2A = A + A
You can then define scalar multiplication:
Discrete logarithm problem on elliptic curves:
Given a point G(x,y) on an elliptic curve and a large number n, it is easy to calculate nG = P. However, given P and G, calculating n is more difficult, but not impossible.
If we define the elliptic curve over a finite field using modulo operation, then calculating n becomes a discrete logarithmic problem. However, given P and G, calculating n is more difficult, but not impossible.
We can understand that the modulo operation is similar to a compression algorithm, which reduces the computational factor while retaining the fundamental properties of the group, and transforms it into a finite loop of fields. This makes it impossible to reverse the reduction of the computational factor.
Taking secp256k1 as an example, the curve is expressed as:
The discrete images are:
The discrete logarithm problem described above is the foundation of elliptic curve encryption and signature algorithms.
In blockchain technology, elliptic curves are mainly used for digital signatures, and most blockchain systems use ECDSA algorithms for transaction verification and traceability. However, in zero-knowledge proofs, we primarily use the homomorphic properties of elliptic curves to enable homomorphic encryption.
2. Homomorphic Hiding
Encryption technology has been in existence for a long time. Classic encryption technology mainly involves hiding information, resulting in encrypted data that is unreadable and inoperable. However, in certain scenarios, we may want to perform specific operations on encrypted data, and retain these operations when restoring the data back to plaintext. In order to achieve this, we use algorithms that have homomorphic characteristics within asymmetric encryption algorithms.
Assuming that the encryption function is E(x), homomorphic encryption can be expressed by the following formula:
Subtraction can be converted to addition, and division can be converted to multiplication and the use of inverse elements within a finite field.
Full homomorphism refers to an encryption function that satisfies both additive homomorphism and multiplicative homomorphism, but such a function is not commercially available and is outside the scope of this article.
As a simple example, if we let the cryptographic function, ?(?)=??, then the cryptographic function satisfies the property of additive homomorphism because:
?(?+?)=?(?+?)=??+??=?(?)+?(?)
And if you let the encryption function
then the function satisfies the property of multiplicative homomorphism, because
And if you let the encryption function
then the function satisfies the property of multiplicative homomorphism, because
Commonly used additive homomorphic algorithms such as Palliar, commonly used multiplicative homomorphism algorithms such as ElGamal, RSA .
2.1. Blind verification of elliptic curves
Elliptic curves satisfy additive homomorphisms:
Therefore, we can construct an additive homomorphic encryption algorithm based on elliptic curves for polynomial blind verification:
Suppose Alice knows a polynomial P of the highest degree d, and Bob wants to verify that Alice knows the coefficients of this polynomial.
The simplest way is to set up the solution of one or more well-known polynomials, for example:
Suppose Alice claims that she knows a third-order polynomial with two roots, 1 and 2. That is, the polynomial can be written in the following form:
(x-1)(x-2) · …
In other words, (x–1) and (x–2) are two factories of the polynomial in the problem. Thus if Alice wants to prove that his polynomial does have these two roots without revealing the polynomial, then he needs to prove that his polynomial p(x) is the product of t(x ) = (x- 1)(x- 2) and some arbitrary polynomial h(x), i.e.:
p(x) = t(x) · h(x)
The natural way to calculate h(x) is to divide directly :
If Alice cannot find such an h(x) which means that p(x) does not contain the factor t(x), then the polynomial division will have a remainder. For example, we divide
We calculate the result h(x) = x with no remainder.
And if we take
we get the remainder 7x – 6 and cannot submit the correct result.
Using the above method, we can construct a polynomial consistency checking protocol:
Bob selects a random value s, calculates t = t(s), and sends s to Alice.
Alice calculates h(x) = p(x) / t(x) and evaluates p(s) and h(s), providing the results p and h to Bob.
Bob verifies that p = t ⋅ h, and if the polynomials are equal, it means that Alice knows all the coefficients.
However, the above method has some drawbacks:
Alice may not know what she claims about p(x), so she can calculate t = t(s) and then choose a random value h to calculate p = t ⋅ h. Because the equation holds, it also passes Bob’s checksum.
Since Alice knows that the random point x = s, she can construct an arbitrary polynomial that has something in common with t(s) ⋅ h(s) at s.
In the previous “statement”, Alice claimed that she knew a polynomial of a particular order, but the current protocol does not explicitly require the order. Thus, Alice can deceive Bob with a polynomial of a higher order that satisfies the factorial check.
The key to the above problem is the exposure of the s value, so next we use homomorphic encryption to solve the above problem
Bob can construct one from an elliptic curve ?(?)=?? and then take a random number s.
At this point, Alice knows that P does not know s, Bob knows that S does not know P, and Bob cannot tell directly Alice’s value on s, since this would not verify the polynomial coefficients, Bob calculates
, given to Alice.
Alice uses homomorphism and can calculate it
The result is then sent to Bob, and the same applies to the calculation of E(h(s)). Now that Bob has E(p(s)) and E(h(s)), he can decrypt p(s) with his private key and h(s).
However, how can Bob be sure that Alice is using the correct polynomial calculations? Alice can still forge proofs using other means instead of using the cryptographic values provided by Bob.
Just having a single s is definitely not enough. For verification, Bob must use another value as a reference.
So we bring us? to this concept
Thanks to the discrete logarithmic problem of elliptic curves, Alice cannot know, and since? Alice does not know ?, she has only one way to generate a new ?pair: multiply a and b by the same coefficient
?? 。
With the KCA (Knowledge-of-Coefficient Assumption) tool, Bob can construct a d-KCA (Knowledge-of-Coefficient Assumption of order d) based on s [3].
- Bob secretly chooses a random value ?and an s value
- Generate d ?pairs to send to Alice
Alice uses the homomorphic properties of elliptic curves and the known polynomial coefficients to generate new pairs ?
Bob verifies <?′,?′> that it is ?correct
If yes, accept the response.
After the above steps, Bob can eventually confirm that Alice knows the polynomial coefficients. The overall process is illustrated in the following figure:
In Chapter 2, we mentioned non-interactivity. However, as it is clear, the above blind verification process is interactive. Therefore, we will now use another set of mathematical tools to construct a non-interactive protocol for polynomial blind verification.
2.2. Bilinear pairing
To construct a non-interactive protocol, we need a secret parameter that is reusable, public, trusted, and cannot be abused.
In the blind verification protocol described above, we observe that the secret values used for verification are primarily s and α. If we want to construct a non-interactive proof, we need to make t(s) and α public parameters in the verification process, allowing us to achieve one-step public verification without any involvement of a single verifier entity.
The next concern is how to ensure the security of the secret value (t(s), α) after its construction.
Of course, it is encrypted using an elliptic curve, in the same way that Bob used for the power of s before sending the encrypted value to Alice. However, the elliptic curve homomorphic encryption we use only supports additive homomorphism and does not allow for the multiplication of two secret values. This makes it impossible to multiply the encrypted values of t(s) and h(s), as well as the encrypted value of α, which is crucial for verifying the product of the sums of p(s) and h(s).
It may seem that we have reached a dead end. Are we going to use a fully homomorphic algorithm? Fortunately, mathematicians have given us a tool – Bilinear Pairing.
Bilinear pairing was first proposed by the French mathematician André Weil in 1946 while he was in prison during World War II. At that time, there was no systematic cryptography (Shannon’s famous paper “Communication Theory of Secret Systems” was published three years later, and public-key cryptography did not develop until 30 years later). Today, bilinear pairing is mainly used in the fields of BLS aggregate signatures and zero-knowledge proofs.
Bilinear pairing can be intuitively understood as the ability to map two points P and Q on elliptic curve 1 to elliptic curve 2 through the “multiplication” operation (to be precise, it is a carefully constructed pair of superelliptic curves, with specific theoretical reference [4][5]). The point R.
At the same time, they have a relationship similar to the “multiplicative” associative law and commutative rate:
We call R the bilinear map of points P and Q, denoted as
?(?,?)
Let P=αG1, Q=βG1, and R=P· Q=(αβ)G2, where G1 is the base point in the elliptic curve E1 and G2 is the base point in the elliptic curve E2. Then the mapping relationship can be expressed as e(αG1, βG1) = αβ· e(G1, G1).
Bilinear pairing can be popularly interpreted as follows: After the “multiplication” operation of point P and point Q in E1, they are mapped to point R in E2. This is equivalent to performing the “multiplication” operation with G1, the reference point in E1, to “map” a point in E2. Point R is then obtained from the “scalar multiplication” of αβ times.
It is as if two elements in the finite universe can “generate” an element in the parallel universe through some kind of “operation”, and they have a “multiplicative” connection between them.
In this way, we can construct a weakened version of the homomorphic multiplication operation based on elliptic curve pairing. However, it is a weakened version because it only supports the multiplication of two encrypted values.
Textual References
[3] Groth J. Short pairing-based non-interactive zero-knowledge arguments[C]. International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010: 321-340.
[4] D. Boneh, B. Lynn, and H. Shacham, Short signatures from the Weil pairing,Asiacrypt 2001, LNCS 2248, pp.514-532, Springer-Verlag, 2001.
[5] S. D. Galbraith, K. Harrison, and D. Soldera, Implementing the Tate pairing,ANTS 2002, LNCS 2369, pp.324-337, Springer-Verlag, 2002.
