A riddle

An old riddle asks: “What is something you never want, but once you have, you never want to lose?” The standard answer is “a bald head.” For a cryptographer, however, an equally good answer is “a hard problem.”

To explain: it would be terrific if all computational problems were easy. However, once we find a candidate hard problem—such as integer factorization—and we start building cryptosystems on top of it, we want that problem to “stay hard” for a long time. So a hard problem is something that we never really want to have, but once we have, we certainly never want to lose.

This post is about the discrete-log problem, which is one hard problem that we certainly don’t want to lose. In this post, we discuss preprocessing attacks on the discrete-log problem, explain their power and limits, and we mention a few new results along the way.

The discrete-log problem

The discrete-log problem is arguably the foundational problem in modern cryptography. It is the problem on which we build the key-exchange protocols, the digital-signature schemes, and the public-key encryption systems that secure our network communications and our e-commerce transactions.

Formally, we define the discrete-log problem relative to a finite cyclic group of prime order . The discrete log problem in is:

Given: ,  for an sampled uniformly at random from

Find: 

Since a discrete-log instance takes bits to write down, a polynomial-time discrete-log algorithm runs in time .

The hardness of the discrete-log problem depends crucially on the choice of the group . In some groups, such as the additive group of integers modulo , the discrete-log problem is solvable in polynomial time. In some groups, such as the multiplicative group of integers modulo , the best known discrete-log algorithms—“index calculus” algorithms—require sub-exponential time (something like time). In yet other groups, such as the elliptic-curve groups that your laptop uses to talk to your mail server, the best known discrete-log algorithms require exponential time .

How hard is it really?

One difference between bald heads and hard problems is that it’s not too hard to determine when you have a bald head (I can tell you from personal experience…) but it’s not so easy to know when you have a hard problem. In particular, why should we believe that the discrete-log problem is truly hard in any of the aforementioned groups? Is it possible that there is a much better discrete-log algorithm than these lurking just around the corner? Could some enterprising grad student find a polynomial-time algorithm that solves the discrete-log problem in every group?

In 1997, Shoup showed that the answer to the last question, at least, is a resounding “no:” the best discrete-log algorithm that works in every group must run in strictly exponential time .

Shoup proved this statement formally by defining a notion of “generic” discrete-log algorithms: these are algorithms that are agnostic to the structure of the group and, as such, they solve discrete log in every group. We don’t really want to get into the full formalism here but, roughly speaking, a generic algorithm just treats the group elements as arbitrary bitstrings and needs only black-box (oracle) access to the group operation in .

A number of generic discrete-log algorithms, including Shanks’ “Baby Step Giant Step” algorithm and Pollard’s “Rho” algorithm, run in time and show that Shoup’s lower bound is tight.

Shoup’s lower bound on generic discrete-log is especially interesting because the best algorithms for hard instances of the elliptic-curve discrete-log problem (ECDLP) are the generic ones. Thus, improving on the known ECDLP algorithms will require coming up with new non-generic discrete-log algorithms.

When using elliptic-curve cryptosystems in practice, implementers typically choose with the expectation that the best attacks will run in time roughly . Shoup’s lower bound lends some credibility to this strategy, since we know that the best generic attacks will take roughly this much time.

The discrete log monoculture

One funny feature of the Internet’s cryptographic ecosystem is that there are only a handful of groups in use out there. There are good reasons for this: using a standard set of groups reduces implementation complexity, ensures interoperability between different pieces of software, and enables the research community to focus its cryptanalytic effort on a few important groups.

However, having everyone on the Internet use one of a small set of standard groups entails some risks. In particular, if an adversary knows which group a victim will use, the attacker can mount a preprocessing attack against the discrete-log problem in that group. (In fact, Stanford’s own Martin Hellman introduced this sort of preprocessing attack in a 1980 paper.)

In a discrete-log preprocessing attack, an attacker does a huge amount of -specific precomputation in a preprocessing phase, after which she outputs a short “advice string” about the group . Later on, the adversary can use this short advice string in an online phase to quickly compute discrete logs in . If the advice string can be of length , then you can essentially store the answer to every discrete-log problem instance in the advice string. If the string has size , then it is less clear how advice can be useful to you.

A pair of recent independent results—one due to Mihalcik in 2010 and one due to Bernstein and Lange in 2013—show that even bits of advice can actually help quite a bit. More generally, these authors show a surprisingly powerful preprocessing attack on the discrete-log problem.

Recall that, in a group of order , the best generic discrete-log attacks run in time . Mihalcik and Bernstein and Lange show that there is a discrete-log algorithm with preprocessing that:

• operates in every finite cyclic group ,
• uses bits of -specific advice, and
• runs in online time much less than .

There are two reasons why this attack is still far from posing a practical threat to today’s discrete-log-based cryptosystems:

1. If (as it is in practice), then the -time attack still runs online time in well over . (The constant inside the big- is modest.)
2. More important, the preprocessing phase of the attack runs in time , which is more than for a 256-bit group. This is far far far beyond the reach of even the most sinister government with the most powerful computers and the most clever programmers.

Still, we might worry: Could better preprocessing attacks of this kind exist?

A worrisome feature of such preprocessing attacks is that they evade Shoup’s lower bound: if the preprocessing algorithm runs in time , then Shoup’s lower bound says nothing about how long the online phase must take.

The prospect of discrete-log preprocessing attacks raises the question: are we in danger of losing one of our favorite hard problems to preprocessing attacks?

The limits of preprocessing attacks

It turns out that, at least as far as generic preprocessing attacks are concerned, things don’t get much worse than the attack above. In our recent work, we show that any generic algorithm with preprocessing that uses an advice string of length bits and runs in online time solves the discrete-logarithm problem with probability at most (where the probability here is taken over the random discrete-log instance as well as any randomness used by the algorithm itself). In other words, one cannot reduce both the length of the advice and the online running time of the attack above while still being able to solve the discrete logarithm problem on a constant fraction of the inputs. Our lower bound extends naturally to the computational Diffie-Hellman problem, for which we also prove an equivalent lower bound, and the multi-instance discrete-log problem.

In terms of practicality, the limiting factor of the Mihalcik/Bernstein-Lange attack is almost certainly its prohibitively large preprocessing time. We also show that this part of their attack cannot be improved. To be specific, we show that any attack that runs in time requires a preprocessing phase that runs in time at least . For example, any generic attack that runs in online time must use close to preprocessing time to succeed with good probability—no matter how large of an advice string it uses.

Distinguishing attacks

An algorithm capable of computing discrete logs would certainly be devastating for many modern cryptosystems. But as is often the case in cryptography, even weaker algorithms—that reveal only partial information about the discrete log (e.g., its last bit)—could compromise the security of such systems. To obtain security guarantees for cryptographic constructions built on top of the discrete-log problem, we often need stronger assumptions than simply the hardness of computing discrete-logs. One of the most common such assumptions is the Decisional Diffie–Hellman assumption. Informally, the DDH problem in a group is the problem of distinguishing the following two probability distributions:

A random tuple:  ,  for sampled independently and uniformly at random from , and

A “DDH” tuple: ,  for sampled independently and uniformly at random from .

The DDH assumption in a group states that the DDH problem is computationally hard in that group. The DDH problem is no harder than the discrete-log problem, as one can always distinguish between the above two distributions by computing the discrete logs of each of the elements in the tuple. More interesting is that, in many groups in which discrete log is hard, the best known algorithm for solving DDH is just to compute a discrete log. In fact, for generic algorithms, Shoup showed in his 1997 paper that the two problems are equally hard.

However, as we’ve seen in the previous section, attacks with preprocessing don’t always follow the same rules as online-only attacks. We would therefore like to establish the hardness of the DDH problem against this class of attacks as well.

In our paper, we give a lower bound for the DDH problem against attacks with preprocessing. Specifically, we show that any algorithm that uses an advice string of length bits and runs in online time solves the DDH problem with probability at most . (A random guess is correct with probability .)

Our lower bound for DDH is not as strong as our lower bound for discrete log: the former bounds the advantage over a random guess by , whereas the latter bounds the success probability of solving discrete log by , which is substantially smaller (note the square-root difference). This opens up the possibility that in the presence of advice, the two problems might no longer be equally hard.

Although this gap remains an open question, we give some evidence in our work that might indicate that the two problems actually differ in their hardness when facing algorithms with preprocessing. Specifically, we show a distinguishing attack with preprocessing on a variant of the DDH problem that achieves advantage over a random guess (and thus beats the best possible discrete-log algorithm as implied by our lower bound). The variant in question is called the Square-DDH problem and it involves distinguishing tuples of the form from tuples of the form for random .

The distinguishing attack combines two ideas: one is a generic distinguishing attack on any pseudo-random generator described in the Bernstein-Lange paper (which in its turn builds on an earlier work by De, Trevisan, and Tulsiani), and the other is the idea of taking a walk on the elements of the group, and applying the distinguisher only to the set of points that lie at the end of long walks. The combined attack achieves the improved distinguishing advantage.

Open problems

What is left to do here? We leave you with a few open problems that are still nagging at us:

1. DDH. In the setting of generic attacks with preprocessing, are DDH and discrete log equally hard? Or is there a better attack on DDH?
2. Quantum preprocessing. Say that an attacker may use a quantum computer during the preprocessing phase, but must use a classical computer during the online phase. Does having a quantum computer reduce the preprocessing time at all? For example, is there an algorithm with quantum preprocessing time and classical online time ?
3. Non-generic attacks. Much of the interest in generic discrete-log algorithms stems from the fact that we don’t have any good non-generic algorithms for popular elliptic-curve groups. Does preprocessing change this state of affairs? Namely, are there non-generic preprocessing attacks on popular elliptic-curve groups (such as Curve25519 or NIST P-256) that outperform their generic counterparts?

Conclusion

We hope this post has been helpful in understanding the importance of considering attacks with preprocessing when thinking about cryptographic problems, and specifically when dealing with discrete-log-like problems. If you want to get more details, please take a look at our full paper or check out our upcoming talk at Eurocrypt 2018.