This is a series of articles. Part 1, PDF version.
We start with a problem of proving the knowledge of a polynomial and make our way to a generic approach. We will discover many other properties of polynomials along the way.
The discussion so far has focused on a weak notion of a proof, where parties have to trust each other because there are no measures yet to enforce the rules of the protocol. For example, the prover is not required to know a polynomial, and he can use any other means available to him to come up with a correct result. Moreover, if the amplitude of the verifier’s polynomial evaluations is not large, let us say 10, the prover can guess a number, and there is a non-negligible probability that it will be accepted. We have to address such weakness of the protocol, but first what does it means to know a polynomial? A polynomial can be expressed in the form (where n is the degree of the polynomial):
If one stated that he or she knows a polynomial of degree 1 (i.e., c₁x¹ + c₀=0), that means that what one really knows is the coefficients c₀, c₁. Moreover, coefficients can have any value, including 0.
Let us say that the prover claims to know a degree 3 polynomial, such that x = 1 and x = 2 are two of all possible solutions. One of such valid polynomials is x³ – 3x² + 2x = 0. For x = 1: 1 – 3 + 2 = 0. For x = 2: 8 – 12 + 4 = 0.
Let us first look more closely at the anatomy of the solution.
Factorization
The Fundamental Theorem of Algebra states that any polynomial can be factored into linear polynomials (i.e., a degree 1 polynomials representing a line), as long it is solvable. Consequently, we can represent any valid polynomial as a product of its factors:
Also, if any of these factors is zero then the whole equation is zero, henceforth all the a-s are the only solutions. In fact, our example can be factored into the following polynomial:
And the solutions are (values of x): 0, 1, 2, you can check this easily on either form of the polynomial, but the factorized form has all the solutions (also called roots) on the surface.
Getting back to the prover’s claim that he knows a polynomial of degree 3 with the roots 1 and 2, this means that his polynomial has the form:
In other words (x – 1) and (x – 2) are the cofactors of the polynomial in question. Hence if the prover wants to prove that indeed his polynomial has those roots without disclosing the polynomial itself, he needs to prove that his polynomial p(x) is the multiplication of those cofactors t(x) = (x- 1)(x- 2), called target polynomial, and some arbitrary polynomial h(x) (equals to x – 0 in our example), i.e.:
In other words, there exists some polynomial h(x) which makes t(x) equal to p(x), therefore p(x) contains t(x), consequently p(x) has all roots of t(x), the very thing to be proven.
A natural way to find h(x) is through the division
If the prover cannot find such h(x) that means that p(x) does not have the necessary cofactors t(x), in which case the polynomials division will have a remainder. In our example if we divide p(x) = x³ – 3x² + 2x by the t(x) = (x – 1)(x – 2) = x² – 3x + 2:
Note: the denominator is to the left, the result is to the top right, and the remainder is to the bottom (polynomial division explanation with examples is available at [Pik14]).
We have got the result h(x) = x without remainder.
Note: for simplicity, onwards we will use polynomial’s letter variable to denote its evaluation, e.g., p = p(r)
Using our polynomial identity check protocol we can compare polynomials p(x) and t(x) ⋅ h(x):
- Verifier samples a random value r, calculates t = t(r) (i.e., evaluates) and gives r to the prover
- Prover calculates h(x) =p(x) / t(x) and evaluates p(r) and h(r); the resulting values p, h are provided to the verifier
- Verifier then checks that p = t ⋅ h, if so those polynomials are equal, meaning that p(x) has t(x) as a cofactor.
To put this into practice, let us execute this protocol for our example:
- Verifier samples a random value 23, calculates t = t(23) = (23 – 1)(23 – 2) = 462 and gives 23 to the prover
- Prover calculates h(x) =p(x) / t(x) = x, evaluates p = p(23) = 10626 and h = h(23) = 23 and provides p, h to the verifier
- Verifier then checks that p = t ⋅ h: 10626 = 462 ⋅ 23, which is true, and therefore the statement is proven
On the contrary, if the prover uses a different p′(x) which does not have the necessary cofactors, for example p′(x) = 2x³ – 3x² + 2x, then:
Note: although the author’s chief objective is simplicity, including the set of math symbols in use, it would be detrimental for further sections to omit the ubiquitous symbol prime: ′ . Its essential purpose is to signify some transformation or derivation of the original variable or function, e.g., if we want to multiply v by 2 and assign it to a separate variable, we could use prime: v′ = 2 ⋅ v.
We will get 2x + 3 with the remainder 7x – 6, i.e.: p(x) = t(x)×(2x + 3) + 7x – 6. This means that the prover will have to divide the remainder by the t(x) in order to evaluate:
Therefore because of the random selection of x by the verifier, there is a low (but still non-negligible) probability that the evaluation of the remainder 7x – 6 will be evenly divisible by the evaluation of t(x), henceforth if verifier will additionally check that p and h must be integers, such proofs will be rejected. However, the check requires the polynomial coefficients to be integers too, creating a significant limitation to the protocol.
That is the reason to introduce cryptographic primitives which make such division impossible, even if the raw evaluations happen to be divisible.
Remark 3.1 Now we can check a polynomial for specific properties without learning the polynomial itself, so this already gives us some form of zero-knowledge and succinctness. Nonetheless, there are multiple issues with this construction:
- Prover may not know the claimed polynomial p(x) at all. He can calculate evaluation t = t(r), select a random number h and set p = t⋅h, which will be accepted by the verifier as valid, since equation holds.
- Because prover knows the random point x = r, he can construct any polynomial which has one shared point at r with t(r) ⋅ h(r).
- In the original statement, prover claims to know a polynomial of a particular degree, in the current protocol there is no enforcement of degree. Hence prover can cheat by using a polynomial of higher degree which also satisfies the cofactors check.
We will address all of the issues in the following sections.
Obscure Evaluation
Two first issues of remark 3.1 are possible because values are presented at raw, prover knows r and t(r). It would be ideal if those values would be given as a black box, so one cannot temper with the protocol, but still able to compute operations on those obscure values. Something similar to the hash function, such that when computed it is hard to go back to the original input.
Homomorphic Encryption
That is exactly what homomorphic encryption is designed for. Namely, it allows to encrypt a value and be able to apply arithmetic operations on such encryption. There are multiple ways to achieve homomorphic properties of encryption, and we will briefly introduce a simple one.
The general idea is that we choose a base (there are certain properties that base number needs to have) natural number g (say 5) and to encrypt a value we exponentiate g to the power of that value. For example, if we want to encrypt the number 3:
Where 125 is the encryption of 3. If we want to multiply this encrypted number by 2, we raise it to the exponent of 2:
We were able to multiply an unknown value by 2 and keep it encrypted. We can also add two encrypted values through multiplication, for example, 3 + 2:
Similarly, we can subtract encrypted numbers through division, for example, 5 – 3:
However, since the base 5 is public, it is quite easy to go back to the secret number, dividing encrypted by 5 until the result is 1. The number of steps is the secret number.
Modular Arithmetic
That is where the modular arithmetic comes into play. The idea of modular arithmetic is following: instead of having an infinite set of numbers we declare that we select only first n natural numbers, i.e., 0, 1, …, n – 1, to work with, and if any given integer falls out of this range, we “wrap” it around. For example, let us choose six first numbers. To illustrate this, consider a circle with six ticks of equal units; this is our range (usually referred to as finite field).
Now let us see where the number eight will land. As an analogy, we can think of it as a rope, the length of which is eight units:
If we attach the rope to the beginning of the circle
and start wrapping the rope around it, after one rotation we still have a portion of the rope left:
Therefore if we continue the process, the rope will end right at the tick #2.
It is the result of the modulo operation. No matter how long the rope is it will always stop at one of the circle’s ticks. Therefore the modulo operation will keep it in certain bounds (in this case from 0 to 5). The 15-units rope will stop at 3, i.e., 6 + 6 + 3 (two full circles with 3-units leftover). The negative numbers work the same way, and the only difference is that we wrap it in the opposite direction, for –8 the result will be 4.
Moreover, we can perform arithmetic operations, and the result will always be in the scope of n numbers. We will use the notation “mod n” for now on to denote the range of numbers. For example:
Furthermore, the most important property is that the order of operations does not matter, e.g., we can perform all operations first and then apply modulo or apply modulo after every operation. For example (2 × 4 – 1) × 3 = 3 (mod 6) is equivalent to:
So why on earth is that helpful? It turns out that if we use modulo arithmetic, having a result of operation it is non-trivial to go back to the original numbers because many different combinations will have the same result:
Without the modular arithmetic, the size of the result gives a clue to its solution. This piece of information is hidden otherwise, while common arithmetic properties are preserved.
Strong Homomorphic Encryption
If we go back to the homomorphic encryption and use modular arithmetic, for example with modulo 7, we will get:
And different exponents will have the same result:
This is where it gets hard to find the exponent. In fact, if modulo is sufficiently large, it becomes infeasible to do so, and a good portion of the modern-day cryptography is based on the “hardness” of this problem.
All the homomorphic properties of the scheme are preserved in the modular realm:
Note: modular division is a bit more complicated and out of the scope.
Let us explicitly state the encryption function:
where v is the value we want to encrypt.
Remark 3.2 There are limitations to this homomorphic encryption scheme while we can multiply an encrypted value by an unencrypted value, we cannot multiply (and divide) two encrypted values, as well as we cannot exponentiate an encrypted value. While unfortunate from the first impression, these properties will turn out to be the cornerstone of zk-SNARK. The limitations are addressed in section “Multiplication of Encrypted Values”.
Encrypted Polynomial
Armed with such tools, we can now evaluate a polynomial with an encrypted random value of x and modify the zero-knowledge protocol accordingly.
Let us see how we can evaluate a polynomial p(x) = x³ – 3x² + 2x. As we have established previously to know a polynomial is to know its coefficients, in this case those are: 1, –3, 2. Because homomorphic encryption does not allows to exponentiate an encrypted value, we’ve must been given encrypted values of powers of x from 1 to 3: E(x), E(x²), E(x³), so that we can evaluate the encrypted polynomial as follows:
As the result of such operations, we have an encrypted evaluation of our polynomial at some unknown to us x. This is quite a powerful mechanism, and because of the homomorphic property, the encrypted evaluations of the same polynomials are always the same in encrypted space.
We can now update the previous version of the protocol, for a polynomial of degree d:
Note: because the prover does not know anything about s, it makes it hard to come up with non-legitimate but still matching evaluations.
While in such protocol the prover’s agility is limited he still can use any other means to forge a proof without actually using the provided encryptions of powers of s, for example, if the prover claims to have a satisfactory polynomial using only 2 powers s³ and s¹, that is not possible to verify in the current protocol.
Restricting a Polynomial
The knowledge of a polynomial is the knowledge of its coefficients c₀,c₁,…,cᵢ and the way we “assign” those coefficients in the protocol is through exponentiation of the corresponding encrypted powers of the secret value s. We do already restrict a prover in the selection of encrypted powers of s, but such restriction is not enforced, e.g., one could use any possible means to find some arbitrary values zₚ and zₕ which satisfy equation
and provide them to the verifier instead of gᵖ and gʰ . That is why verifier needs the proof that only encryptions of powers of s were used and nothing else.
Let us consider an elementary example of a degree 1 polynomial with one variable and one coefficient f(x) = c⋅x and correspondingly the encryption of the s is provided E(s) = gˢ . What we are looking for is to make sure that only encryption of s, i.e., gˢ , was homomorphically “multiplied” by some arbitrary coefficient c and nothing else. So the result must always be of the form (for some arbitrary c):
A way to do this is to require to perform the same operation on another shifted encrypted value alongside with the original one, acting as an arithmetic analog of “checksum”, ensuring that the result is exponentiation of the original value.
This is achieved through the Knowledge-of-Exponent Assumption (or KEA), introduced in [Dam91], more precisely (note the difference between a and α (alpha)):
a) Alice has a value a, that she wants Bob to exponentiate to any power (where a is a generator of a finite field group used), the single requirement is that only this a can be exponentiated and nothing else, to ensure this she:
b) because Bob cannot extract α from the tuple (a,a′) other then through a brute-force which is infeasible, it is conjectured that the only way Bob can produce a valid response is through the procedure:
c) having the response and α, Alice checks the equality:
Conclusions:
- Bob has applied the same exponent (i.e., c) to both values of the tuple
- Bob could only use the original Alice’s tuple to maintain the α relationship
- Bob knows the applied exponent c, because the only way to produce valid (b,b′) is to use the same exponent
- Alice has not learned c for the same reason Bob cannot learn α *.
* Although the c is encrypted its range of possible values might not be sufficient to preserve zero-knowledge property which will be addressed in the section “Zero Knowledge”.
Ultimately such protocol provides a proof to Alice that Bob indeed exponentiated a by some value known to him, and he could not do any other operation, e.g., multiplication, addition, since this would erase the α-shift relationship.
In the homomorphic encryption context, exponentiation is the multiplication of the encrypted value. We can apply the same construction in the case with the simple one-coefficient polynomial f(x) = c ⋅ x:
- Verifier chooses random s,α and provides evaluation for x = s for power 1 and its “shift”:
- Prover applies the coefficient c:
- Verifier checks:
Such construction restricts the prover to use only the encrypted s provided, therefore prover could have assigned coefficient c only to the polynomial provided by the verifier. We can now scale such one-term polynomial (monomial) approach to a multi-term polynomial because the coefficient assignment of each term is calculated separately and then homomorphically “added” together (this approach was introduced by Jens Groth in [Gro10]). So if the prover is given encrypted exponentiations of s alongside with their shifted values he can evaluate original and shifted polynomial, where the same check must hold. In particular, for a degree d polynomial:
For our previous example polynomial p(x) = x³ – 3x² + 2x this would be:
Now we can be sure that the prover did not use anything else other than the provided by verifier polynomial, since there is no other way to preserve the α-shift. Also if a verifier would want to ensure exclusion of some power(s) of s in a prover’s polynomial, e.g., j, he will not provide the encryption and its shift:
Compared to what we have started with, we now have a robust protocol. However there is still a significant drawback to the zero-knowledge property, regardless of encryption: while theoretically polynomial coefficients cᵢ can have a vast range of values, in reality, it might be quite limited (6 in the previous example), which means that the verifier could brute-force limited range of coefficients combinations until the result is equal to the prover’s answer. For instance if we consider the range of 100 values for each coefficient, the degree 2 polynomial would total to 1 million of distinct combinations, which considering brute-force would require less than a million iterations. Moreover, the secure protocol should be secure even in cases where there is only one coefficient, and its value is 1.
Zero-Knowledge
Because verifier can extract knowledge about the unknown polynomial p(x) only from the data sent by the prover, let us consider those provided values (the proof):
They participate in the following checks:
The question is how do we alter the proof such that the checks still hold, but no knowledge can be extracted? One answer can be derived from the previous section: we can “shift” those values by some random number δ (delta), e.g.,(gᵖ )ᵟ . Now, in order to extract the knowledge, one first needs to find δ which is considered infeasible. Moreover, such randomization is statistically indistinguishable from random.
To maintain relationships let us examine the verifier’s checks. One of the prover’s values is on each side of the equations. Therefore if we “shift” each of them with the same δ the equations must remain balanced.
Concretely, prover samples a random δ and exponentiates his proof values with it
and provides to the verifier for verification:
After consolidation we can observe that the check still holds:
Note: how easily the zero-knowledge is woven into the construction, this is often referred to as “free” zero-knowledge.
References
[Pik14] — Scott Pike. Dividing by a Polynomial. 2014. url: http://www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/long_division/long_division.html(visited on 2018–05–01)
[Dam91] — Ivan Damgård. “Towards practical public key systems secure against chosen ciphertext attacks”. In: Annual International Cryptology Conference. Springer. 1991, pp. 445–456.
[Gro10] — Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2010, pp. 321–340.
