Announcements

• Homework 2 has been posted on Piazza. It is due on Friday 2/10 on Gradescope.
• Homework 3 will be posted later this week, and due on Friday 2/17.

Lecture 6: Cryptographic Building Blocks from Discrete Logarithms

Review from last lecture

At a high level, cryptographic systems attempt to provide (some or all of) the following three objectives.

• Confidentiality: keeping data or people's identities hidden from others.
• Integrity: preventing raw data or the data science results from being altered, or at least allowing for detection of tampering.
• Availability: ensuring that data science is censorship-resistant.

These three security objectives are sometimes referred to as the "CIA triad."

We have spent the past few lectures discussing how to record transactions within a blockchain.

As long as the majority of computational power is controlled by honest miners, then everybody's view of the blockchain is eventually consistent.

[Image source: Nakamoto whitepaper]

Last time, we designed some new cryptographic algorithms, and then used them to add features to Bitcoin.

A light client can be convinced that a transaction exists in the blockchain using a Merkle tree.

• The client only needs to store the root of the tree.
• A full node can store all transactions, and send a short proof that a single transaction is included within a block.

[Image source: Nakamoto whitepaper]

This is our first example of a proof system, which allows a prover who knows why a claim is true to convince a verifier of this fact. We will see more proof systems throughout this course.

Prover		Verifier
	$\longrightarrow$

We also discussed how to resolve a conundrum for light clients.

• For pseudonymity, they want to use each secret key only once.
• But it is easier if they only have to hold one key, rather than many of them.

We designed a pseudorandom generator, which allows the light client to make several random-looking keys in a deterministic fashion.

Given a single key $m$, the client can generate many new values $H(m, 0)$, $H(m, 1)$ and use all of these as keys.

In fact, it is possible to make a hierarchy of keys in this way.

[Image source: BIP-32 specification]

Finally, we can store the master key $m$ in a human-memorable way as a sequence of 24 words. Since each word is chosen from a list of 2048 options, the total number of choices is $2048^{24} > 2^{256}$ so the words can collectively encode a 256-bit key.

6.1 The Discrete Logarithm Assumption

Our starting point for today's lecture is to construct a new kind of digital signature that can make life easier for the nodes.

Last week, we saw the RSA digital signature scheme. It is named after its inventors: Rivest, Shamir, and Adleman. While RSA works fine, one concern is that its keys and signatures are about a few thousand bits long.

That may not sound big, and indeed a single signature is small. But they add up quickly.

Remember that each node stores a record of every single transaction, and so far there have been over 800 million transactions on Bitcoin.

The punchline here is: space on the blockchain is a valuable resource, so we should try to minimize usage of it. Let's discuss another signature scheme that can use less space.

Recall that digital signature schemes have a tricky property: from the public key it is impossible to create a digital signature but easy to verify if someone else has done so.

As a result, we must build signature schemes from math problems that we believe to have this property of "difficult to solve but easy to check."

One such problem is factoring, as we discussed last week. We want to find another problem that is hard(er) to break.

Here is another hard math problem: taking logarithms.

...Wait, this doesn't sound right. If I tell you that I have taken the number $5$ to some power $x$ and the result is $125$, can you compute $x$ such that $5^x = 125$?

Taking logarithms to find $x = \log_5(125)$ is easy over the real numbers $\mathbb{R}$.

But: it turns out though that for certain finite spaces, it is difficult to compute discrete logarithms.

Option 1: Modular arithmetic

Consider the following function: $f(x) = 5^x \bmod{7}$. Can you find a value $x$ such that $5^x = 3 \bmod{7}$?

This does not seem as simple to calculate. The good news is that calculating this function in the forward direction is easy: all we have to do is multiply. So, here is the truth table of the function $f$.

x	f(x)
1	5
2	4
3	6
4	2
5	3
6	1

Now can you solve the question from above? (It took a lot of work to do so!)

It turns out the act of exponentiation modulo a prime number is:

• Invertible. In fact it is a permutation, because each number between $1$ and $6$ occurs exactly once as a possible output.

• Computationally difficult to invert... at least if we choose a prime modulus that is large enough.

  (There is one additional caveat: we must take only the subgroup of quadratic residues, i.e., the even half of the truth table.)

Option 2: Elliptic curves

[Image source: Wikipedia]

Here is another, admittedly strange way to perform multiplication and exponentiation.

• Take a cubic equation $y^2 = x^3 + ax + b \bmod{p}$ -- this is called an elliptic curve.
• Consider the set of points on this degree 3 curve.
• We can "multiply points" using the rule that $P \cdot Q \cdot R = 1$. (Note that this has absolutely nothing to do with taking the exponent of the $(x, y)$ coordinates of any of the points.)

• We can "exponentiate a point" using a tangent line, so $P \cdot Q^2 = 1$.

[Image source: Wikipedia]

This is a very strange operation! Don't worry too much about the math details here. The most important thing to remember here is that it also leads to a hard math problem, where exponentiating is easy but the inverse is practically impossible.

Elliptic curve discrete logarithm assumption: Given two points $P$ and $Q$ such that $P^x = Q$, it is computationally infeasible for anyone to find the discrete logarithm $x$.

(Note: all of the exponentiations and logarithms in today's lecture are done modulo a prime number, but I'm going to stop writing that explicitly from now onward.)

In fact, this problem is really hard to solve, even harder than factoring (as far as we know). So, we can get away with smaller keys.

6.2 Diffie-Hellman Key Exchange

We have a new tool in our crypto toolbox. What can we do with this?

Here's one option: we can use the hardness of discrete logarithms as the basis for another type of public key cryptography.

Taking a slight detour from cryptocurrencies, let's go back to a question I raised in the first lecture. Suppose you want to send data back and forth to a public website, like kaggle.com, in such a way that nobody else can read or tamper with its contents.

We already know that digital signatures can provide evidence of tampering. But what about message confidentiality?

To solve this problem, you need symmetric key encryption. This is the digital equivalent to a combination safe -- it allows for two computers to exchange messages confidentially, as long as they have a shared secret that the two of them know but nobody else in the world does.

It is the basis for end-to-end encrypted secure messaging systems like Signal and WhatsApp.

In order to encrypt data, your computer and the kaggle.com server both need to have a secret key that nobody else in the world does.

You		kaggle.com
	$\quad \Longleftrightarrow \quad$

But how can they do that? If you could physically meet, then you could exchange secrets. But we want to enable secure communication over the Internet, which is a public network where most pairs of people have never met before.

In the digital world, they need a secure way to exchange secrets in plain view.

“The Internet is just the world passing notes in a classroom.”

– Jon Stewart

Amazingly, this can be done!

Based on the hardness of the discrete logarithm problem, here is an approach that you and the kaggle.com server can take.

• You can choose a secret $a$ that you keep to yourself, and send $A = g^a$ to the server. (Remember, nobody can take $A$ and reconstruct $a$... not the server, or anyone else!)
• The server can choose a secret exponent $b$ and send $B = g^b$ to you.

Now, there is a shared secret that both of you can compute: $s = g^{ab}$.

• You can take the public value $B$ and raise it to your secret exponent $a$ to compute $B^a = (g^b)^a = s$
• The server can do the opposite: $A^b = (g^a)^b = s$

Moreover, nobody else can compute this secret! Other people hear $A$ and $B$. But they don't know -- and cannot compute -- either secret exponent. So as far as we know, they have no way to compute $s$.

(Slight caveat: the last sentence does not actually follow from the one before it. Nevertheless, we do believe that it is a true statement too.)

This ingenious protocol was discovered in the late 1970s by Whitfield Diffie and Martin Hellman, and it is named Diffie-Hellman key exchange in their honor. It was based on concepts developed earlier by Ralph Merkle... the same person who invented Merkle trees.

6.3 A Zero-Knowledge Proof

Here is another application of the math of discrete logarithms: we can build an amazing new kind of proof.

A zero knowledge proof allows a prover to convince a verifier that a particular claim is true, but without revealing the evidence for this claim!

Prover		Verifier
	$\longrightarrow$

Let's see how this works in the case of discrete logarithms. Suppose that:

• The prover chooses a secret exponent $x$, and reveals $g^x$ to the world
• The prover now wants to show that she knows the discrete log of $g^x$... but without revealing $x$!

How can we do this?

The key idea is that the prover can show only discrete logarithms of values of her own choosing, and not $g^x$ specifically. Here's how the prover and verifier can interact.

1. Prover chooses a random exponent $k$ and sends $g^k$ to the verifier.
2. Verifier chooses one of two challenges: it requests either
   • The discrete log of $g^k$, or
   • The discrete log of $g^k \cdot g^x = g^{k+x}$.
3. Prover responds to the challenge by sending either $k$ or $k+x$, as appropriate.

The verifier accepts this proof only if $g$ raised to the power of the final message equals the challenge.

We will provide a formal definition of zero knowledge proofs in a future lecture. At a high level:

• Confidentiality holds because the prover only responded to one challenge. Either $k$ or $k+x$ on its own reveals nothing about $x$.
• Integrity holds due the fact that the prover knows how to respond to both requests. And if it knows both $k$ and $k+x$, then it follows that the prover must know $x$.

One downside of this protocol is that the prover can cheat with probability $\frac{1}{2}$.

For instance, even if I have no idea what $x$ is, I can run the first part of the protocol honestly and I will be able to respond to a challenge to produce $k$.

To fix this problem, the prover and verifier can repeat the protocol many times until the verifier is convinced that the prover isn't cheating.

A faster approach is to introduce more challenges that the verifier can ask.

1. Prover chooses a random exponent $k$ and sends $g^k$ to the verifier.
2. Verifier chooses a number $e$ at random, and challenges the verifier to find the discrete log of $g^k \cdot (g^x)^e = g^{k+xe}$.
3. Prover responds to the challenge by sending $k+xe$.

As before, the verifier accepts this proof only if $g$ raised to the power of the final message equals the challenge.

6.4 Constructing a Digital Signature Algorithm

Returning back to our goal: how can we form a digital signature algorithm based on the fact that discrete logarithms are hard?

Remember that a signature scheme needs a secret key and public key, such that it is easy to go from the secret to the public key, but hard to go in the other direction.

Based on the zero knowledge proof, here's an idea for KeyGen.

• Secret key: sample an exponent $x$ uniformly at random.
• Public key: choose a base $g$, and publish $y = g^{x}$ as the public key.

This satisfies our criteria.

• Starting from the secret key, we can calculate the public key through exponentiation, which is simple to do.
• But going in the other direction requires taking a discrete logarithm, which is believed to be hard.

There are a few digital signature schemes that can be designed using keys of this form.

One of them is a NIST standard called the digital signature algorithm, or DSA. If you use an elliptic curve group to build it, then we refer to the construction as ECDSA. (Note: this is the construction we used in Homework 1.)

Another scheme, which is slightly simpler, is called Schnorr signatures.

I reproduce the construction of Schnorr signatures below; it is adapted from the presentation on Wikipedia. Don't worry too much on the math details; the main ideas are the same as the zero knowledge proof we constructed earlier.

To sign a message $M$:

• Choose a random exponent $k$ from the allowed set.
• Let $r=g^{k}$.
• Let $e = H(r, M)$, where $H$ denotes a cryptographic hash function.
• Let $s = k − x e$.

The signature is the pair $\sigma = (s, e)$.

To verify the claimed signature $\sigma = (s, e)$ of a message $M$:

1. Let $r^* = g^{s}y^{e}$.
2. Let $e^* = H(r^*, M)$.

If $e^* = e$, then return true (i.e., that the signature is valid). Otherwise return false.

An observation: this signature scheme is randomized. If you request to sign the same message twice, you will likely get two different signatures back in response.

Nevertheless, all possible signatures will correctly be accepted by $\operatorname{Verify}$.

Why does this construction work?

Correctness: if all parties are honest, it is a straightforward math calculation to check that the $\operatorname{Sign}$ algorithm produces a signature that passes the $\operatorname{Verify}$ algorithm. Try writing it out to convince yourself of this fact!

Unforgeability: the Schnorr signature algorithm has cleverly interwoven two hard problems here -- the difficulty of solving discrete logarithms and the random oracle property of the cryptographic hash function $H$.

I will only give some intuition about the argument here. Put yourself in the shoes of Mallory. How would you break this construction?

• If you pick $s$ and $e$ first, then that determines the value of $r^*$ in step 1. But the cryptographic hash function "acts randomly" and it is extremely unlikely that it happens to return $e$ again.

• If you pick $r^*$ first, that determines the value of $e$ in step 2. Returning to step 1, you need to solve the equation $g^{s} = (r^*)/(y^e)$ for the only remaining unknown value: $s$. But that requires solving a discrete logarithm problem!

Impact to the Bitcoin blockchain

Remember that we started down this path in order to produce smaller signatures. How well did we do?

• Using elliptic curve groups, the discrete logarithm problem is hard if the secret key $x$ is be 256 bits, or 32 bytes, in length.
• The two values $s$ and $e$ in the signature are each of length 32 bytes as well. Hence, the overall size of a Schnorr signature is 64 bytes.

By comparison: ECDSA signatures are 72 bytes long, and RSA signatures are several hundred bytes in size.