Hard problems in cryptography
Hardness assumptions on mathematical problems lie at the heart of modern cryptography; they are often what ensure one cannot break an encryption scheme. This week we will see what hard problems are and how they can offer this underlying security. We have two of examples of hard problems to look at and one of these uses group theory, that we introduced last week.
What are ‘hard problems’?
Some mathematical problems are harder than others, but what if some problems can never be solved? Well, this is exactly what much of modern cryptography relies on. Often it is assumed that a problem is hard, and this assumption is used to prove that it is impossible to break an encryption scheme, for example.
More formally, a hardness assumption on a particular problem is the assumption that there is no efficient algorithm (that runs in what we call polynomial time) that can solve it.
It is often not known whether there is a method to solve these hard problems efficiently, just that there is not currently a method to do so. However, most of the hard problems used in modern cryptography have been widely studied and so we can have confidence that the assumption they are hard is valid.
How are they used?
How can we use a hard problem in showing an encryption scheme is secure? We use what is called a reduction argument which runs as follows: we show that if an adversary can break the encryption scheme then they can also break the hard problem, thus ‘reducing’ the security to the hard problem.
Why does this work?
Why do these reductions work? Well, think about it this way:
- We have made an assumption that a problem is hard and we have confidence that it is hard because these hard problems have been well studied.
- We then take an adversary, who we assume can break our encryption scheme, and we show that this adversary (which we may have to adapt slightly — this is fine as long as it is still efficient or runs in polynomial time) can break the hard problem.
- Although, now we have a contradiction as we assumed that no efficient adversary could solve the hard problem.
- Thus, due to this contradiction, we know the adversary cannot break our encryption scheme or in other words, breaking the encryption scheme is as hard as solving the hard problem, which is hard, so we can be happy that it is hard to break the encryption scheme.
Let’s take a look at a couple of examples…
Factoring:
Factoring numbers is a hard problem. While it may seem very simple for low numbers, it is considered a hard problem for large numbers. The problem can be formulated as follows:
Take n = p.q where p and q are large prime numbers. The challenge, given the number n, is to find p and q.
DDH:
The second hardness assumption we will consider here is the decisional Diffie-Helman assumption. This assumption is based on cyclic groups, we saw these last week. Remember, that for cyclic group G we have a generator g (this is just an element that can be used to make every other element in the group).
The DDH assumption says that it is hard to distinguish between the following two tuples:
1. (ga,gb, g(a.b)) where a and b are chosen at random;
2. (ga,gb, gc) where a, b and c are chosen at random.
It is this hardness assumption that is used in the ElGamal encryption scheme we will see next week.
Further reading:
- Look up what polynomial runtime is, why do you think we make this restriction when we consider hard problems and adversaries?
- Find out where the two hard assumptions we see here are used in modern cryptography.
This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.
Oxbridge Inspire delivers innovative STEM education and provides guidance and inspiration to young people wishing to pursue STEM subjects at University and beyond. To find out more about Oxbridge Inspire and the courses and activities we offer, visit our website.
