Lecture 4: Crypto from the Discrete Logarithm Assumption

We also began our exploration into digital signatures, which allow the recipient Bob of a message to check that the sender is who they claim to be (entity authentication) and that the data hasn’t been tampered in transit (data authentication).

Alice		Mallory		Bob
	\(\longrightarrow\)		\(\longrightarrow\)

Formally, a digital signature contains three algorithms:

• KeyGen: takes no input, produces a secret key \(sk\) and a public key \(pk\)
• Sign\((sk, M)\): produces a signature \(\sigma\)
• Verify\((pk, M, \sigma)\): returns true or false

All three algorithms should be efficiently computable. Moreover, the digital signature must satisfy two requirements: correctness (Alice’s honest signatures should pass the verification check) and unforgeability (formalized with the EU-CMA game).

A digital signature scheme needs to be based on a math problem that is difficult to solve but easy to verify. Unfortunately, we do not know for certain whether any such problems exist! As a result, in cryptography we make conjectures about the difficulty of time-tested math problems, such as factoring.

If factoring large integers is computationally infeasible, then the RSA digital signature scheme is unforgeable (i.e., no adversary Mallory can win the EU-CMA game).

RSA is used in practice today, but not always. Let’s look at the digital certificate for the website bu.edu as an example.

• Note that RSA keys and signatures are small, but not that small: they are 2048 bits (or 256 bytes) long. This is because factoring is a hard problem, but it’s not a really hard problem, so we have to choose very large numbers for it to be infeasible by modern computers.

• As a result: RSA is fast, but not that fast. Signing and verification take around 1 millisecond on a modern laptop or phone, give or take.

These costs may not sound significant, and indeed a single signature is small and quick to compute on your phone or laptop. But:

• If you run a web server and calculate RSA for every client that visits your website, then the computational costs add up quickly.
• As we will see next week when we discuss Bitcoin, there are more than 1 billion transactions made on the Bitcoin blockchain so far, and each one includes a digital signature. As a result, using a large signature can waste many gigabytes of storage space.

Instead, the most common standard is called the digital signature algorithm, or DSA. We will discuss it today.

…Wait, hang on, this doesn’t sound right. Let’s check whether this is actually a hard math problem.

Question. If I tell you that I have taken the number \(5\) to some power \(x\) and the result is \(125\), can you determine the power \(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 if you ask this question together with modular arithmetic, then it is believed to be practically infeasible to compute discrete logarithms. For instance, consider the following function: \(f(x) = 5^x \bmod{7}\).

Question. Can you find an integer \(x\) such that \(5^x \bmod{7} = 2\)?

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\). (Remember that this took a decent amount of computational effort to build.)

With this table, now can you solve the question from above?

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

• Invertible. In fact it is a permutation over the inputs from \(1\) to \(6\), because each number between \(1\) and \(6\) occurs exactly once as a possible output. (And the function cycles after that, so we’ll ignore any larger inputs.) And this idea generalizes to larger primes besides \(p = 7\). The function is a permutation over the integers from \(1\) to \(p-1\).

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

  (There is one additional caveat: for some technical reasons that I will skip, we must take only the subgroup of quadratic residues, i.e., only half of the truth table for even values of \(x\).)

There is another way to make “exponentiation” easy but “logarithms” hard. It uses another kind of math object called an elliptic curve, which is just a cubic equation \(y^2 = x^3 + ax + b \bmod{p}\).

Rather than multiplying numbers, we’re going to make a new kind of arithmetic where we can “multiply” points in space. I’ll skip the math details since they are strange, but the punchline is the same: it is another 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). As a result:

• The act of computing a digital signature is faster: closer to microseconds (\(10^{-6}\) seconds) than milliseconds (\(10^{-3}\) seconds).
• We can get away with smaller keys and signatures: they can be 256 bits/32 bytes in size (just like SHA-256) rather than 2048 bits/256 bytes in size.

Taking a slight detour from digital signatures, let’s go back to a question I raised in the first lecture. Suppose Alice wants 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 the contents that Alice sends or receives from the server.

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

To solve this problem, Alice needs symmetric key encryption. (We will build it in Unit 3 of this course.)

• 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, Alice’s computer and the kaggle.com server both need to have a secret key that nobody else in the world does.

Alice		kaggle.com
	\(\quad \Longleftrightarrow \quad\)

But how can they do that? If Alice and the web server could physically meet, then they could exchange secrets. But we want to enable secure communication over the Internet, which is a public network where most pairs of people (and companies) 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! 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.

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

• Alice can choose a secret \(a\) that she keeps to herself, and send \(A = g^a\) to the server. (Remember, nobody can take \(A\) and reconstruct \(a\)… not the server, or anyone else!)
• The kaggle.com server can choose a secret exponent \(b\) and send \(B = g^b\) to Alice.

Now, there is a shared secret that both of them can compute: \(s = g^{ab}\).

• Alice can take the public value \(B\) and raise it to her 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\).