Applied Crypto #1: Elliptic Curve Cryptography

Description

Yan Zhang talks about elliptic curve cryptography.

🔑 Many cryptographic protocols rely on the fact that it is ‘hard’ to find discrete log in groups, which is known as the Discrete Log Problem (DLP). Two protocols of these protocols are the Diffie-Hellman Key Exchange and the Elgamal Public Key Cryptosystem. The Diffie-Hellman protocol is a way for two parties to securely derive a shared secret even in the presence of an eavesdropper and the Elgamal Cryptosystem allows one party to securely second a message to another party.

To make this computation more efficient and secure, we want groups with certain desired properties. Enter elliptic curves! The magic of elliptic curves is that they give us groups with really favorable properties for ZK cryptography — namely groups with an efficient group operation, where discrete log is hard, and enable pairings (which we define later). Most importantly, Elliptic Curve DLP (given $P$ and $nP = Q$, it is hard to find $n$) is harder than DLP over numbers modulo prime $p$.

A group and an elliptic curve share the properties of associativity, identity, and invertibility (i.e. all elements have an inverse). This means that any cryptographic computation done in a group can also be done in an elliptic curve! Using ECDLP, we can implement Diffie-Hellman Key Exchange and Elgamal Public Key Cryptosystem elliptic curves. Why does this matter? Elliptic curve cryptography provides the same security guarantees as “normal” cryptography but requires fewer bits, making computation more efficient.

Another useful EC computation is an elliptic curve pairing: A bilinear pairing on two elliptic curve groups means that for groups $G_1$ and $G_2$, with generators $G$ and $H$ respectively, we can define a bilinear mapping e: $G_1$ x $G_2$ = $G_T$ such that $e(aG, bH) = e(G, H)^{ab}$. EC pairings are important because they allow us to perform unique operations over groups in ways we couldn’t normally do. Pairings underlie many core cryptographic primitives used in zero-knowledge cryptography, including BLS digital signatures, KZG polynomial commitments, and zkSNARKs.

Check-in Questions

(1) DLP: Why is the Diffie-Hellman Key Exchange secure even when an eavesdropper Eve can see $g^{a}$ and $g^{b}$? Why can't she compute $g^{ab}$ given this information?

(2) Pairings: What do pairings allow you to do that normal groups do not?

(3) EC Pairing Example: Let’s suppose you want to prove to me that you know some integer a that satisfies the equation $x^2 - 2027a + 16152 = 0$ without revealing $a$ to me. How would you do this using an elliptic curve pairing?

Check out zkPairing for a proof-of-concept implementation of zkSNARK circuits for elliptic curve pairings in Circom.

Sample Answers

(1) *DLP: The shared secret that the two parties derive in the Diffie-Hellman Key Exchange is $g^{ab}$. Even if the eavesdropper knows $g^a$ and $g^b$, it is hard to find $a$ or $b$ because of the Discrete Log Problem.

(2) Pairings: Pairings allow you to multiply two hidden numbers while “normal groups” only allow you to add. Wow, the magic of pairings!

(3) EC Pairing Example: First, choose two public generators $G$ and $H$. You compute $aG$ and $aH$, and send me the results. I cannot compute a due to ECDLP. I run the following computation with a series of pairings:

$e(aG, aH) * e(G, (-2027)*(aH)) * e(G, 16152 * H) = e(G, H)^{a^2 - 2027 a + 16152}$

If the result of this computation is 1, then we know that $a^2 - 2027a + 16152$ is indeed equal to 0 (with high probability)!