What encryption methods are there?
There are basically two encryption methods: symmetric and asymmetric. Symmetric encryption uses the same key to encrypt and decrypt, which means that the sender and the recipient must have the same key. This system has the disadvantage that the shared key must be distributed via a secure channel. To overcome this disadvantage, asymmetric encryption was developed in the 1970s. This uses a key pair consisting of a public key for encrypting and a private key for decrypting. The public key is freely distributed, while the private key remains secret. This enables secure communication without the need to exchange a shared secret key in advance. The asymmetric method created the basis for today's exchange of information over the Internet, such as online banking, etc. For post-quantum cryptography, only asymmetric cryptography is actually relevant.
How does asymmetric encryption work?
The asymmetric encryption method is based on difficult mathematical problems: in other words, problems that a computer cannot solve quickly, such as factorizing large numbers. Even as humans, we can break down the number 91 into the two prime factors 13 and 7. For a 600-digit number, however, a computer would need millions of years because there is no fast algorithm for this. The security of encryption is based on this one-way function: multiplication is easy, but factorization, i.e. breaking down a number into its multipliers, is very difficult. Factorizing a large number into prime numbers, which is known as the RSA method, is only one of the possible methods.
Why do quantum computers pose a threat to these encryption methods?
In the 1990s, Peter Shor developed an algorithm enabling a quantum computer to calculate the factorization in just a few hours. Back then, quantum computers were just theory; today, they actually exist. And they are becoming more and more powerful.
So is the encryption in use today still secure?
Yes and no. As things stand today, the RSA method, which has been in use for 50 years, is secure. But with the increase in computing power, quantum computers will in future be able to decode information that is currently protected by these methods.
When will this happen?
There are various estimates, but no one can say for sure. The National Institute of Standards and Technology (NIST) in the USA, for example, assumes that by 2030, there will be cryptographically relevant quantum computers that pose a threat to cryptography. Estimates vary on how many quantum bits, or qubits for short, are needed for a quantum computer to be able to apply Shor’s algorithm or other algorithms that can crack the encryption. Initially, the assumption was that billions of qubits would be needed, but a lot has happened in recent years. Today, the figure is thought to be around 10,000 qubits. Last fall, IBM achieved 1,100 qubits. This number will increase over the next few years, and at some point Q-Day will arrive. Today, we also have the problem that quantum computers and qubits are very errorprone. But again, a lot of progress is being made here to correct or reduce errors more quickly.
What new methods that can withstand a quantum computer are already available as a replacement?
In 2022, NIST selected four quantum-safe algorithms as part of a six-year competition: two CRYSTALS algorithms, CRYSTALSKyber and CRYSTALS-Dilithium, as well as FALCON and SPHINCS+. NIST will publish its new standards this summer. These will be the new standards to secure the digital world for the coming decades. Anyone could take part in the competition, and cryptographers around the world tried to crack the submitted encryption algorithms. Naturally, many were eliminated, and in the end, NIST selected these four algorithms because they are the most secure and also the most practicable. Europe is taking the lead in this area, by the way. All four selected methods were primarily developed by institutes in Europe, and three of the four algorithms were largely developed by us at the IBM research laboratory in Rüschlikon.
In which areas are the algorithms used?
CRYSTALS-Kyber is an algorithm for securely exchanging keys via a public channel. It replaces well-known methods such as the Diffie-Hellman method and, unlike these, is secure against quantum computers. The other three algorithms are methods for digital signatures, to prove the authenticity of certificates, documents, software updates, etc.
When and for whom will the new NIST standard apply?
“Standard” means agreeing on how to encrypt and communicate. The US government is not just doing this for itself, but for the entire ecosystem, including the financial industry and others. It has set out a roadmap defining when and in which applications the new algorithms must be integrated. The NIST standards apply to many areas in the USA, but also have a global impact. Authorities in Europe also cite NIST. Standardization sends out a signal: the encryption of a solution is generally certified. Software manufacturers that supply the US government and the US market must have these certifications. Buyers do not want to implement 20 different algorithms. The private sector will therefore also follow suit, as cryptography is used everywhere and everyone is affected.
Do IBM and the other developers have a patent on their algorithms?
No. One of the requirements of the competition was that the submitted methods must not be patented. All the submitted algorithms are publicly available as open source and must be free of intellectual property rights. It is important that the algorithms are transparent for all to see and can be checked.
When will the new algorithms replace the current encryption methods?
This process has already started. At IBM, we implemented the algorithms in our mainframes in 2022, before the NIST announcement. Various cloud providers offer the algorithms and they are already integrated in the Google Chrome browser. Apple also announced in its iMessage security update in February that it is now using CRYSTALSKyber. The US government, for example, has drawn up a roadmap setting out when the new encryption standards must be implemented in which applications. What is important now is that companies and service providers can prepare for this transition. We don’t want a repeat of the Y2K problem. Back then, the transition took place relatively late and it became very expensive. Now we have a little more time, but it will depend on whether we tackle it in time and whether it is planned cleverly.
What difficulties do you see in switching to the new methods? Will it involve a lot of time and expense?
Until now, no one has really given much thought to the cryptographies used. They existed and were used. Nobody has ever recorded which methods are used in today’s very complex IT environment and where, as there was never any plan to replace the cryptography. You first need to understand how the relevant data streams are encrypted. IBM supports organizations with the transition: How can you prepare? What should you prioritize? How do you organize and orchestrate the whole thing? And how can you make the switch efficiently over a certain period of time without it costing a lot of money and causing a lot of headaches? The transition is very complex because there are many dependencies in today’s IT landscape. A company obtains most of its software, or at least components of it, from various providers or directly from the cloud. This means that the transition has many dependencies, as the systems must continue to be compatible with each other. For example, a bank must ensure that the transition not only takes place in the backend of its online banking system, but that all its customers, i.e. the browsers they use, are also able to make the change. In today’s initiatives, where workloads are moved to clouds or containers in clusters, the quantum-safe issue should be integrated from the outset. Making this change retrospectively is much more complex and expensive. This is where the concept of crypto-agility comes in, where cryptography does not have to be deeply embedded in the code, but is externalized in the form of Cryptography as a Service. This means that cryptography can be managed and used more easily and effectively. Germany’s Federal Office for Information Security (BSI) recently published a recommendation on crypto-agility that serves as a guide for companies.
second part of the interview
The algorithms submitted by IBM as part of the NIST competition are now the new standard. What other areas of cryptography are you researching?
Good question. You could say the research was essentially completed when the algorithms were submitted in 2017. However, we have been very actively involved in this process right up to standardization and have also been working on other developments. Among other things, NIST has launched a new competition to find new, even more compact digital signatures. Our cryptographers are also busy converting protocols to the new procedures. We are also researching ways to securely implement the new algorithms in code. This poses many challenges, such as vulnerable side channels and performance. When a server receives thousands of requests per second, every millisecond counts, so economies of scale also play a role. This makes IBM Research in Rüschlikon unique in global industrial security research. It’s the only place where specialist knowledge and practical implementation can be found at this level.
Are we ready for Q-Day?
I would say no, not yet. But I don’t want to be needlessly alarmist. It’s about being prepared and creating a wider awareness. We still have time, but one day we will see the arrival of powerful quantum computers. Although there is one scenario that we already have to deal with today: Harvest now, decrypt later. Encrypted data can be collected today to be decrypted in the future using quantum computers. Organizations therefore need to think about which data is particularly worth protecting and take measures at an early stage to minimize risks. Many areas of our digital world and our society are based on trust and the certainty that data will be kept secret and that the other party can be authenticated, i.e. recognized as genuine.
Are you worried about Q-Day?
I’m more concerned that many organizations will react very late due to a lack of awareness. I remember the year 2000 problem (Y2K). At that time, many organizations saw a real surge. In the case of post-quantum security, even though there is no clear date, the relationships are much more complex. And there is a lot at stake.
Do you want clear guidelines from the federal government?
I would leave it open as to whether there should be concrete specifications for standards or algorithms. What’s important is to develop guidelines that organizations can use as a basis. In Switzerland, the Federal Office for Cyber Security (BACS) and Armasuisse are already involved in the field of post-quantum cryptography, and the topic was also discussed by politicians last summer.
A positive question to finish off with. What are the advantages of quantum computing?
There are many areas of application in which quantum computers can be helpful. For example, in simulations, optimization problems, or in materials science. Quantum computers can model relationships that are not possible with conventional computers. Quantum computing is a pivotal technology for the 21st century.