Understanding Zero-Knowledge Proofs: Part 2 — Math Basics for Cryptography
We started this series with a previous article giving a broad-overview of zero-knowledge proofs and their role in enabling verifiable computation with confidentiality. The rest of this series aims to elucidate how zero-knowledge proofs work. For folks new to cryptography, there is a bit of a math hurdle to understand how exactly various schemes work. This is an attempt to capture some of the basics, with pointers to learn more.
Fields, Groups, Elliptic Curves
Field: A field is just a set of numbers equipped with two binary operations (addition and multiplication) satisfying certain properties (namely, associativity, commutativity, distributivity, existence of identity and inverses, for both operations). Common examples of fields are the set of rational numbers (Q), real numbers (R), and finite fields with p elements (Fp).
Finite Fields: Typically in cryptography finite fields (also known as Galois fields) are used, with the number of elements being referred to as their order. The field Fp consists of the first p whole numbers: {0, 1, … (p-1)}. Basic operations like addition, subtraction, and multiplication can be defined defined as with whole numbers but with the modulo p operation so that the answer remains within the set. The division is defined a little differently to ensure the output remains in the field, as follows: x divided by y is expressed as (x * y^(p-2) ) %p.
(An interesting aside: Why do we multiply x by y^(p-2) for division? First note that straightforward division by an integer can result in a non-integer value: e.g., 1/2. Fermat’s little theorem states that y^p = y for any y in a prime field of order p. From this we can see y^(p-1)*y= y, which implies that y^(p-1)=1, which in turn shows that y^(p-2)*y = 1 which indicates that y^(p-2) is the inverse of y. )
Groups: A group is a set G equipped with a binary operation (addition or multiplication) that satisfies closure, associativity, having an identity element e, and an inverse element for each element. A group G is called a cyclic group if there exists an element g∈G (called a generator) such that every element in G can be written as g^n (i.e., g multiplied n times in case of a multiplicative group) or n⋅g (in case of an additive group) for some integer n. All cyclic groups are Abelian (i.e. the operation is commutative). The multiplicative group formed by any finite-field Fp is cyclic. The additive group formed by any finite field with a prime order is also cyclic. Lagrange’s theorem states that if G is a finite group and H is a subgroup of G, then the order (number of elements) of H divides the order of G. The theorem also shows that any group of prime order is cyclic and simple, since the subgroup generated by any non-identity element must be the whole group itself.
Elliptic Curves: Elliptic curve cryptography (ECC) uses the properties of elliptic curves defined over finite fields. An elliptic curve E over a finite field Fp consists of
i) all points satisfying the equation y² = x³+ax+b (mod p) where a and b are constants that satisfy the condition 4a³ + 27b² (mod p) != 0, and
ii) a “point at infinity” called O.
To clarify what this looks like, consider the elliptic curve y² = x³+3 mod(11). All the points other than the point at infinity are shown in the figure below (from here).
One popularly-used elliptic curve is BN254, defined as follows:
Elliptic Curves and Groups: There is a special geometrically-defined addition operator for Elliptic curves. It is illustrated for an Elliptic curve over the Reals in the following figure.
A similar operation can also be defined for Elliptic curves over finite fields, as illustrated below.
The set of all points on an Elliptic curve over a finite field, let’s call it E{Fp}, with the above-mentioned addition operator, forms an additive group. Treating any base-point on the curve P as a generator, we get a cyclic additive group, with the property that all other elements in that group can be generated as integer multiples of the generator, i.e. in the form n⋅P.
Given an elliptic curve defined over a finite field Fq, it is possible to find a base point that generates a cyclic subgroup with the largest prime order r, where r is the largest prime factor of the order of E{Fq}. This cyclic additive subgroup is typically used for elliptic curve cryptography.
One benefit of using elliptic curves is that various operations such as addition, doubling, negation, and multiplying a point by a scalar can be done very fast.
Next article: Next, we will discuss Cryptography using Elliptic Curves.