Skip to main content

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 PP and nP=QnP = Q, it is hard to find nn) is harder than DLP over numbers modulo prime pp.

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 G1G_1 and G2G_2, with generators GG and HH respectively, we can define a bilinear mapping e: G1G_1 x G2G_2 = GTG_T such that e(aG,bH)=e(G,H)abe(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 gag^{a} and gbg^{b}? Why can't she compute gabg^{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 x2βˆ’2027a+16152=0x^2 - 2027a + 16152 = 0 without revealing aa 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 gabg^{ab}. Even if the eavesdropper knows gag^a and gbg^b, it is hard to find aa or bb 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 GG and HH. You compute aGaG and aHaH, 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)a2βˆ’2027a+16152e(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 a2βˆ’2027a+16152a^2 - 2027a + 16152 is indeed equal to 0 (with high probability)!