Encrypted Polynomial Evaluation

Encrypted Exponentiation

In our article about bilinear pairings, we explained how to do (partially) homomorphic encryption for multiplication. The next natural question is, can we do homomorphic encryption for exponents?

A quick look at our asymmetric bilinear pairing construction suggests that this isn’t practical. Given a G12 point, what other group would we construct a pairing with, and what would the output group be? If we use asymmetric pairings, this group could have a truly massive dimension, which is undesirable.

Therefore, we need a different strategy if we are going deal with exponents larger than 2.

Let’s say we want to prove we know x such that

(The answer is x = 5 by the way). What we do is encrypt the values of x, x², and x³ and give that to the verifier. Without the modulo aspect (to make this easy to follow), we get the following

Giving this to the verifier, the verifier will compute

Since the verifier knows g, they can raise g to the 39th power and see the equality holds, thus verifying the prover’s claim that they know x such that the polynomial evaluates to 39. Don’t forget this is all done modulo p, i.e. in a finite field!

By the way, the verifier can check that x₁, x₂, and x₃ are all consecutive powers of the same number because

for all xᵢ. (There is a subtle issue that the prover might supply sequential powers of x not starting at 1, but we'll get to this).

Because of group theory magic, this trick also works if we use the group of elliptic curves instead of the group of gⁿ mod p. Elliptic curves are more efficient than gⁿ mod p. The only change is scalar multiplication by the generator point instead of raising the generator integer to a power.

Here is the example polynomial from earlier done in python with an ecrypted evaluation using elliptic curves. Note that X, X2, and X3 are elliptic curve points the prover passes to the verifier.

from py_ecc.bn128 import G1, multiply, add, neg, eq

# Prover
x = 5

X3 = multiply(G1, 5**3)
X2 = multiply(G1, 5**2)
X = multiply(G1, 5)

# Verifier
left_hand_side = multiply(G1, 39)
right_hand_side = add(add(add(multiply(X3, 1),
                              multiply(neg(X2), 4)),
                              multiply(X, 3)),
                              multiply(neg(G1), 1))

assert eq(left_hand_side, right_hand_side), "lhs ≠ rhs"

Trusted Setup

Counterintuitively, we typically use the above construction in reverse.

The full motivation for this won’t be fully understood until we get to quadratic arithmetic programs, but you can see this algorithm requires the verifier to do work linearly proportional to the size of the polynomial. Our goal is not just zero knowledge, but succinct zero knowledge. So although we just showed you a cool trick, it is clearly a dead end for building ZK-SNARKS.

Instead, what we do is have a trusted third party generate a secret x value and encrypt it as

And the prover will plug this into their polynomial with coefficients cᵢ

where G is the generator of the elliptic curve group.

And output the result.

At first, this might seem not very useful since neither the prover nor the verifier knows the input and output value of the polynomial. The only difference is the verifier doesn’t know the polynomial of the prover. But this lack of knowledge about the input and the output turns out to be very important to zero knowledge. To jump ahead, the fact that the prover doesn’t know what point they are evaluating on and what the result is becomes a tool to prevent them from forging proofs, and the fact that the input and output is encrypted helps prevent the verifier from learning the polynomial.

Schwartz Zippel Lemma and the motivation for encrypted polynomial evaluation

The Schwartz-Zippel Lemma says that two unequal polynomials almost never overlap except at a number of points constrained by the degree. In a big prime finite field (i.e. a prime number with a couple hundred bits), the degree is going to be vanishingly small compared to the order of the field. So if we evaluate two different polynomials at a random point x and they evaluate to the same value, then we can be almost perfectly certain the two polynomials are the same even if we don’t know the polynomials.

As it is, we have enough tooling for a prover to prove to the verifier that they have four polynomials 𝓐(x), 𝓑(x), 𝓒(x), and 𝓓(x) such that 𝓐𝓑 = 𝓒𝓓, and the verifier can certify this fact without learning the polynomials.

The prover will execute the encrypted evaluation of all four polynomials to obtain scalars A, B, C, and D and give that to the verifier. The verifier can then carry out AB = CD to see the prover’s claim is true. The prover doesn’t know what point they are evaluating at so they can’t architect polynomials that intersect at the point the third party setup chose (assuming no collusion).

Okay, we have AB = CD, but how is that useful?

This starts to get interesting when the verifier can require the prover to use a known polynomial for D. This is not enough for the verifier to learn A, B, or C, but it puts known constraints on what polynomials the prover can use for A, B, and C.

For example, one important feature is that the verifier now knows AB has the same roots (and possible others) as D because when polynomials are multiplied by a non-zero polynomial, the roots of the product polynomial is the union of the roots of the constituent polynomials. Therefore, the roots of polynomial 𝓓 must be a subset of the roots of 𝓐𝓑.

Another subtle way to constrain the verifier is to only supply them encrypted powers of x up to a limited power. This constrains the degree of the polynomial 𝓐𝓑.

A unknown polynomial of with a known upper bound on the degree and a known set of roots is not unique, but nonetheless “says something” and can be used to encode information with some clever transformations. This should start to give you a foggy idea of how succinct zero knowledge proofs are possible.

Another teaser is that the setup ceremony “powers of tau” derives its name from creating a lot of powers of a hidden value so encrypted polynomials can be calculated from it, similar to what we described in this section.

The purpose of this article is only to introduce the concept of a trusted setup and encrypted polynomial evaluation, so we must stop here. But now that we know how to handle addition, multiplication, and exponentiation in an encrypted manner, we are ready to encode and encrypt arbitrary calculations, with the added bonus that we have a vague idea of how to make them succinct.

Learn more with RareSkills

This material is from our zero knowledge proof course.