top of page

Encrypted Polynomial Evaluation

Updated: Jan 31

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

39 = x^3 - 4x^2 + 3x - 1

(The answer is x = 5 by the way).


The naive way to solve this is to give x = 5 to the verifier, then they will plug it into the formula. This obviously gives away the solution. If we multiply 5 by the generator of an elliptic curve group (G1), this will "encrypt" the value. Although the verifier, given a point representing and encrypted x might be able to compute x² as the point paired with itself, we cannot compute a higher power because the pairing can only be used once.


Instead, the prover computes the encrypted value of x, x², and x³ and gives those the verifier separately. That is, the prover is squaring and cubing on behalf of the verifier.


Here is the example polynomial from earlier done in python with an encrypted 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 τ 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. We are using the square brackets to emphasize the term is an elliptic curve point.


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.

Note that [result] is the same value as if we had evaluated the polynomial directly. That is, if

And we evaluate it directly on τ, then multiply the result by the generator, we will get the same point.

The important point here is that we can evaluate polynomials using elliptic curve points and get a valid output, but without knowing the point we evaluated the polynomial at.


Important implementation detail: polynomials over finite fields

Elliptic curves form a cyclic group, and thus they have a notion of the “maximum” value they can encode. Polynomials over integers however have an unbounded maximum.


To be precise, we can only evaluate polynomials modulo done the order of the elliptic curve group. That is, we need to do

where n is the order of the group.

Here’s how we can do this in Python

from py_ecc.bn128 import G1, multiply, add, curve_order, eq, Z1
from functools import reduce
import galois

print("initializing a large field, this may take a while...")
GF = galois.GF(curve_order)

def inner_product(ec_points, coeffs):
    return reduce(add, (multiply(point, int(coeff)) for point, coeff in zip(ec_points, coeffs)), Z1)

def generate_powers_of_tau(tau, degree):
    return [multiply(G1, int(tau ** i)) for i in range(degree + 1)]

# p = (x - 4) * (x + 2)
p = galois.Poly([1, -4], field=GF) * galois.Poly([1, 2], field=GF)

# evaluate at 8
tau = GF(8)

# evaluate then convert
powers_of_tau = generate_powers_of_tau(tau, p.degree)
evaluate_then_convert_to_ec = multiply(G1, int(p(tau)))

# evaluate via encrypted evaluation# coefficients need to be reversed to match the powers
evaluate_on_ec = inner_product(powers_of_tau, p.coeffs[::-1])

if eq(evaluate_then_convert_to_ec, evaluate_on_ec):
    print("elliptic curve points are equal")

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 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.


1,764 views0 comments

Commentaires


bottom of page