DATA encryption is one of the most widely used methods to keep our confidential digital data safe. Without encryption private messages, bank records, and confidential digital information would be open for scrutinising by any person, making individuals and organisations very vulnerable.
Data encryption or the bundling of data into impenetrable files for safe transmission via the internet is an absolute and indispensable necessity in our time of proliferating cybercrime.
Currently, no hacker can easily or successfully decrypt private data since it takes considerable computing resources and time. But there is a major threat emerging to current encryption algorithms and our private data due to the growth in powerful quantum computers all over the world.
Quantum computers are computers based on quantum physics, using subatomic quantum bits (qubits) instead of the conventional binary bits (ones and zeros) of present day computers. Qubits follow quantum physics rules and can exist in “superposition” (having multiple values at the same time) that makes quantum computers exponentially faster than traditional computers since it can perform multiple calculations at once.
Most current data encryption systems are based on the difficulty of “prime factorisation” where a number is given and the smallest prime numbers that multiply together to give that number must be found. If large numbers are used, calculating all the various possibilities with traditional computers take very long.
However, in 1995 Peter Schor developed a very efficient prime factorisation algorithm that could find prime factors for extremely large numbers in a short time. Fortunately, Shor’s algorithm could only run on quantum computers. It would therefore be relatively easy to break current cryptography with quantum computers in the future.
All over the world many of the big tech companies and university labs have either built or acquired quantum computers. As the proliferation and power of these computers increase (100+ qubits in November 2021), the threat of breaking the current encryption of our data becomes bigger.
But it will take a few more years, since a study from 2019 calculated that a quantum computer of 20 million qubits will take about eight hours to break current encryption.
This threat from quantum computers is the reason why scientists and cryptographers are searching for new forms of cyber protection and a new quantum-computer-proof encryption system.
If this is not done in time, no private data will be safe if hackers get access to quantum computer technology.
Since 2017, the National Institute of Standards and Technology (NIST) in the US has been running a worldwide competition to find a new cryptographic algorithm. Over the years 69 algorithms have been narrowed down to seven finalists with the winners to be announced this year.
Five of these algorithms are lattice-based, using “noise” (eg adding random numbers) to turn the encrypted data into something complicated and patternless, thus preventing quantum computers from decrypting it.
However, many scientists are not convinced that lattices are the best way forward since Daniel Bernstein from the University of Illinois in Chicago developed a method to break through encryption lattices.
A group of scientists, with Professor Jintai Ding from Tsinghua University and Dieter Schmidt, Professor Emeritus from the University of Cincinnati as the lead mathematicians, developed the Rainbow cryptosystem since 2004 – a firm non-lattice-based favourite among many.
The security of Rainbow is based on the fact that solving a random multivariate quadratic equation (any relationship where the difference in the differences is a constant) is an NP-hard problem (a class of problems which are at least as hard as the hardest problems in non-deterministic polynomial-time [NP] problems). The signatures of Rainbow is therefore known to be much shorter than that of other post-quantum signature schemes.
Unfortunately or perhaps fortunately, Ward Beullens of IBM Research in Zurich, Switzerland, cracked the signature Rainbow encryption algorithm and published his provocative article “Breaking Rainbow takes a weekend on a laptop” in February 2022. He was able to extract Rainbow’s secret key from a public key in just 53 hours on a standard laptop, thus exposing a flaw that could enable attackers to wrongfully “prove” they are someone else, thus rendering Rainbow unsuitable for message verification.
Cryptography to a large extent relies on computational complexity arguments. As computers became more powerful, cryptographers had to increase the size of the keys. However, the longer the keys are, the more impractical the algorithms become. Rainbow can thus increase the key lengths to enhance the security, but it would make the algorithm far less attractive and more difficult to integrate into existing systems.
One of the most promising post-quantum signature methods of encryption that was supposed to protect data from hacking by quantum computers, has just been broken. If we cannot develop a secure encryption system that can withstand the power and special properties of quantum computers, we will experience serious problems with secure communication on the internet, such as logging into a bank site to execute transactions.
If such a promising candidate such as Rainbow can be broken so severely, it questions if we know enough about these technologies to standardise them yet. Perhaps it is time to extend our seeking of a cryptographic solution beyond complexity-based thinking, and consider the fundamental laws of physics and quantum technologies to generate cryptographic keys.
Professor Louis C H Fourie is an extraordinary professor at the University of the Western Cape
BUSINESS REPORT