Cryptographers have outsmarted today’s computers with clever encryptions. But the race is on to keep personal information safe in the future. As the recent recipient of the prestigious ICAR Fellowship explains, the next challenge is bamboozling the quantum computers of tomorrow.
When we design an algorithm for encryption, we’re not devising some kind of secret code. In fact, the whole algorithm is open – it’s published, and well-known. The only part which is not known is this relatively short 128-bit piece of information – a simple, secret key. And every time you’d like to communicate, you generate a random new key, which you distribute between you and the intended recipient.
If you both have the same key, you can quite securely communicate because even if somebody intercepts your cryptograms, the task of extracting the message is pretty horrendous. And it’s probably not doable using our existing computing power: it’s more or less equivalent to randomly selecting 128 bits in sequence. So that’s 2 to the power of 128 guesses. If you consider how long this number is, you will see that in many millions of years you may eventually break it, but not now.
Believe me, some of the problems are so difficult that no quantum computer is able to solve them quickly.
There aren’t many eureka moments in cryptography. Eureka is actually hard work. You design components of the algorithm, and you follow, more or less, the very well-known Shannon recipe for designing encryption algorithms. You just construct two basic modules and combine them. Obviously, the whole art, or skill, is that you’d like to get both a very fast algorithm and a very secure one. It’s easy to get very fast, but that’s often relatively insecure. And it’s also easy to get very secure, but very, very clumsy – very inefficient. Finding the middle ground is the challenge.
The next big challenge is designing cryptographic algorithms and protocols which are going to be resistant against quantum computers. At the moment there is an ongoing competition to create a post-quantum encryption algorithm and also digital signatures.
It has led to a substantial revolution, or evolution, of design. RSA [a public-key cryptosystem, named after inventors Rivest-Shamir-Adleman] is the classical design, which is based on mathematical problems which are intractable on classical computers – for instance, factorisation is an RSA encryption base. But this is actually easy on a quantum computer. So RSA is dead.
No, the new design must use mathematical problems that are difficult on quantum computers. And this means creating quite a few different variants of difficult problems in mathematical lattices, which is some sort of like, well … Believe me, some of the problems are so difficult that no quantum computer is able to solve them quickly.
Quantum computers might not come together for 10 or 20 years, but we have to be ahead of them. There’s been some substantial progress, but there isn’t a working quantum computer yet. Some of the components are slowly appearing, and we already have something like the equivalent to a central processing unit (CPU) – the heart of any computer. But there are many stumbling blocks, like memory. We still don’t have that quantum memory that guarantees storage of qubits for a long time.
We actually already know how quantum computers are going to work – we just don’t know whether or not we can make them operate yet. But I’m lucky enough not to have to bother about the intrinsic problems related to quantum because we already know some of the mathematical problems that are intractable, and difficult for quantum. So I’m concentrating on those mathematical models.
We actually already know how quantum computers are going to work – we just don’t know whether or not we can make them operate yet.
I’ve always loved mathematics. When I was a student in Bydgoszcz, Poland in the early 1970s, I was studying electrical engineering, but then started a second degree in mathematics, and began work on cryptography. It was perceived by a lot of people as the future, and I discovered there were a lot of interesting problems in terms of encryption and authentication. And so I was able to publish a few papers in some quite highly ranked journals.
One of my papers was actually accepted to a conference, Eurocrypt 85 – and I was able to attend in Austria, where I met my now very close friend and collaborator, Jennifer Seberry. We had a lengthy discussion about things and in 1986 I moved to Sydney.
We were actually the first serious group working in cryptography in Australia. My colleagues and I designed the first encryption algorithm for commercial use here. Telecom (as Telstra was known then) had a very big lab at the time working in security and cryptography. We designed LOKI in 1990.
Then, in 1997, NIST (National Institute of Standards and Technology) in the US announced a competition for an Advanced Encryption Standard (AES). This was an invitation to create a common secure language that everybody around the world could communicate with. The obvious restriction was that when you win, you could not claim any monetary profits, as this would be a free license.
The authors would actually give away the crypto as a service to the community, so everybody could use the algorithm.
We sent LOKI97 as a candidate, which was another one of the results of our collaboration – its design involved quite a number of steps at the heart of its encryption algorithm, which is highly nonlinear. It has a lot of cryptographic properties, which makes the whole algorithm strong. And it also has a linear layer, which doesn’t provide any extra confidentiality but it distributes changes very quickly because this algorithm is executed in a few rounds.
This is an invitation to create the common secure language that everybody around the world would communicate with. The obvious restriction was that when you win, you cannot claim any monetary profits, as this is a free licence
Our algorithm didn’t win, but it was analysed by colleagues from around the world, and in general, the feedback was quite positive. We didn’t get to be the founder – the international standard out now is the Rijndael, used by banking and government institutions for non-military applications – it’s actually quite strong in terms of resistance against attacks. Until quantum computers come along.
I’m not really a quantum physicist, so I don’t need to worry about whether or not this will be finally constructed. But even if the fully-grown quantum computer is not built in 10 or 20 years, some of the parts will be constructed. Our work is still of value – it doesn’t matter whether or not they will be able to come up with the working quantum computer.
Originally published by Cosmos as Open algorithms and secret keys: will existing encryption solutions solace quantum?
Professor Josef Pieprzyk
Professor Josef Pieprzyk has been one of the key drivers of Australia's, and arguably the world's, cryptography and cyber security research. He was recently awarded an ICAR (International Association for Cryptologic Research) Fellowship, the highest recognition a cryptographer can receive from the international research community. A Senior Principal Research Scientist at CSIRO’s Data61, he is currently working on a variety of data security (cryptography) projects, including quantum computing cryptography, and the security of IoT devices that collect and store data.
