Understanding Zero-Knowledge Proofs: Part 3—Elliptic Curve Cryptography

We continue our journey to explore how zero-knowledge proofs work. After a broad overview of zero-knowledge proofs and how they enable verifiable computation with confidentiality in part 1, in part 2, we went over some basic mathematical background needed for cryptography, namely finite fields, cyclic groups, and elliptic curves. Now we turn to how elliptic curve cryptography (ECC) works, through some concrete examples applying it to encryption and key exchange for secret creation. We also present another key concept in ECC called bilinear pairings and their application to identity-based encryption and short signatures.

Elliptic Curve Cryptography: Hardness and Benefits

Hardness: The use of elliptic curves in cryptography is backed by the hardness of the elliptic curve discrete log problem (ECDLP). ECDLP is stated as follows: Given points S and T on an elliptic curve over a finite field E(F(q)), find an integer m such that T = mS. The smallest m that satisfies this relationship is conventionally referred to as the discrete logarithm of T with respect to S.

While a brute force approach takes O(q) steps to find the discrete log, for a general ECDLP the fastest known algorithm is Pollard’s ρ method, which can solve it in time that scales as O(sqrt(q)). If q is exponentially large, ECDLP is a challenging problem. Today, for q > 2¹⁶⁰ , ECDLP over E(F(q)) is considered computationally infeasible.

ECC requires Smaller Keys: The complexity of the Elliptic Curve Discrete Logarithm Problem (ECDLP) is exponential in the size of the key (i.e., the number of bits of the order of the elliptic curve group). In contrast, solving the discrete logarithm problem over a multiplicative group of a finite field (used in older cryptographic schemes like the original Diffie-Hellman Key Exchange and the Digital Signature Algorithm) or solving the prime factorization problem (used in the famous RSA algorithm) both have sub-exponential complexity. Consequently, elliptic curve cryptography (ECC) can achieve the same level of security with much smaller key sizes compared to cryptographic systems based on multiplicative groups. For instance an ECC scheme with a key size of 256 bits is comparable to 3072 bits in RSA.

Applications of Elliptic Curve Cryptography

To understand how ECC, works, let’s examine two classic cryptographic schemes: Elliptic Curve Diffie-Hellman (ECDH) key exchange and Elliptic Curve ElGamal Encryption.

Elliptic Curve Diffie-Hellman (ECDH) key exchange: Alice and Bob wish to create a shared secret by exchanging information over a channel that is open to a potential adversary. Alice has a private key a, and Bob has a private key b. Alice generates a public key A using a generator g: A = a⋅g. And likewise, Bob generates a public key B using the same generator g: B = b⋅g. They exchange these keys over the open channel. Then Alice creates the shared secret based on Bob’s public key and her private key by calculating S = a⋅B = ab⋅g, while Bob creates the shared secret based on Alice’s public key and his private key, respectively, by calculating S’ = b⋅A = ba⋅g. Because ab = ba (product of scalars from the underlying finite field is commutative), S=S’. Note that the public keys, A, B, as well as the shared secret resulting from this protocol are all points on the elliptic curve.

Elliptic Curve ElGamal Encryption: This is an asymmetric key encryption scheme. It works as follows when Alice wants to send a message to Bob. Let Bob’s public key be represented as B = b⋅g, for a generator g on the elliptic curve. First, at the encryption side, Alice represents her message M as a point on the Elliptic Curve. Alice also takes a random number k, and computes two terms as follows. C1 = k⋅g, C2 = M + k⋅B. The cypher-text (C1,C2) is sent over an open communication channel to Bob. Bob decrypts as follows: C2 — b⋅C1 = M+k⋅B— bk⋅g = M+kb⋅g — bk⋅g = M + kb⋅g — kb⋅g = M. This is a simplified description of how the scheme works, in particular not addressing how an arbitrary message could be represented as a point on the elliptic curve.

Other examples of elliptic curve cryptography schemes are Menezes-Vanstone Elliptic Curve Cryptosystem (MVECC), Elliptic Curve Integrated Encryption System (ECIES), and Elliptic Curve Digital Signature Algorithm (ECDSA).

Bilinear Pairings and their Applications

Another technique that is used in some elliptic curve cryptography schemes (including in zero-knowledge proof schemes that we are working up to) is referred to as a bilinear pairing.

A bilinear mapping is a mapping from points on two cyclic subgroups of elliptic curves (call them G1 and G2) to an element of a multiplicative cyclic group (call it GT). This mapping must satisfy three key properties:
(1) Bilinearity: For all P, Q in G1, and natural numbers a, b, e(a⋅P, b⋅Q) = e(P,Q)^(ab).
(2) Non-degeneracy: for any T in G2, e(S, T) = 1 if and only if S is the identity point in G1.
(3) Computability: There should be an efficient algorithm to compute e(P,Q) for any P in G1​ and Q in G2​.

Examples of bilinear pairings for elliptic curves are the Weil pairing and the Tate pairing. Bilinear pairings are used in identity based encryption, short signatures, and are also used in zero-knowledge proof schemes. Their use in cryptography is predicated on the complexity of solving a problem known as the Bilinear Diffie-Hellman Problem (BDHP). One reason they are useful is that, very roughly speaking, they offer a way to “transfer” the use of a private key from one point on one curve to another one on a different curve. In particular, consider that the bilinearily property implies e(a⋅P, Q) = e(P, a⋅Q), as they are both equal to e(P,Q)^a. If you think of a as a private key, and aP as a public key, and Q as another quantity such as a hashed ID or message, then the term on the left (a⋅P,Q) corresponds to having the public key aP as well as the quantity Q, while the second term corresponds to having just the known generator of the first curve P, and applying the private key directly on the quantity (a⋅Q). Consider two concrete use cases of bilinear pairings: a) identity based encryption, and b) the Boneh-Lynn-Shacham (BLS) signature scheme.

Identity-Based Encryption: the goal of identity-based encryption (IBE) is to use a user’s identity (like their email address) as their public key. Bilinear pairing-based IBE works as follows. Consider a master private key k. Using an elliptic curve with generator P, the corresponding master public key is k⋅P. Given an identity ID, it is hashed to a point on the curve I = H(ID). A corresponding private key for this ID is generated by the owner of the master key as i = k⋅I . Now, a sender trying to send an encrypted message to the user uses the master public key and their identity. The encryption process involves the master public key k⋅P and the hashed identity I , while the decryption process involves the generator P and the private key i. Specifically, the sender uses a secret S = e(k⋅P, r⋅I) based on a random scalar r, the master public key k⋅P, and the hashed-ID I, as well as the bilinear pairing function e(.,.) to encrypt the message, and also sends r⋅P to the receiver. The receiving user is able to use r⋅P and its own private key i = k⋅I to reconstruct a secret S’ = e(r⋅P, k⋅I). By the bilinear pairing property, we have that S = e(k⋅P, r⋅I) = e(P, k⋅I)^r = e(r⋅P, k⋅I) = S’. Thus, the secret is a shared one and can be used to decrypt the message.

Boneh-Lynn-Shacham (BLS) Digital Signature: the goal of BLS is to create short, efficient digital signatures. It works as follows. Consider a private key k . Using an elliptic curve with generator P, the corresponding public key is K = k⋅P. Given a message m, it is hashed to a point on the curve H= H(m). A corresponding signature for this message is generated by the owner of the private key as s = k⋅H. Now, a verifier trying to check the validity of the signature uses the public key K and the hash of the message H. The verification process involves the generator P and the public key K, while the signing process involves the private key s. Specifically, the verifier uses a bilinear pairing function to check if e(s, P) = e(H, K). By the bilinear property, we have that e(s, P) = e(k⋅H, P) = e(H, k⋅P) = e(H, K). This equality helps confirms that the signature s was indeed generated using the private key k corresponding to K. The BLS signature is short compared to traditional digital signature schemes because it is just a point on the elliptic curve. Another useful benefit of BLS is that it allows for aggregating signatures from many senders into one signature of the same length.

Next article: next, we will look at the topic of Polynomial Commitments.