Around Christmas, a team in China published a scientific paper claiming a combination of techniques that allows you to break RSA-2048 with a quantum computer with just 372 qubits, which is smaller than systems that already exist. It’s an interesting paper that shows the use of a Quantum Approximate Optimization Algorithm (QAOA) algorithm to factor numbers. However, it doesn’t address whether you can factor faster with a quantum computer than with current classical approaches. This misses the point of why you’d want to employ the quantum computer in the first place.
Papers like this get published with increasing frequency, and every single one of them needs to be taken seriously to understand if there is something novel. There are several challenges to address to achieve cryptographic relevance of a quantum computer, and individual papers may slowly provide the different building blocks and techniques to enable a breakthrough. This breakthrough would affect data security, as today’s encryption schemes to transmit data also transmit the encryption key that can decrypt the data. Papers like this are a good reminder that today’s cryptography can fall apart in a moment.
Another interesting point about this paper is that the technique they claimed would apply not only to RSA-2048 but also to CRYSTALS-Kyber, which is the last remaining key exchange algorithm in the NIST post-quantum cryptography competition. So, it’s not unreasonable to worry that if RSA is broken with a new approach, PQC algorithms could also be broken. The PQC algorithms aren’t proven safe – we just don’t know of a way to break them yet. This means that any data transferred that has been intercepted and stored could be compromised, and all future traffic is at risk too – even if you had already migrated to PQC.
Personally, this is why I’m passionate about Qrypt’s technology, and why I joined Qrypt to begin with. Our Chief Cryptographer, Yevgeniy Dodis, has published protocols that eliminate the transmission of the encryption key. Traditionally, users are at the mercy of the encryption algorithm they use point to point; when this falls, they lose the encryption keys and all their data security. Qrypt’s technique is complementary and achieves much stronger privacy, making cracking communications harder, both technically and practically. While traditionally, the attacker can simply harvest ciphertext and then break it later, with our approach, the attacker has a very limited window of opportunity. If a particular ciphertext is not broken in a very short period of time, you get security forever. This makes Qrypt the only available technology that could protect against advancements like those described in the paper – when it turns out to be the real thing.
If you’re interested in knowing why we probably don’t need to worry about this paper, I should first say that a detailed review still needs to happen within the quantum community. I’m not a quantum scientist, but I have certainly read many papers and have spent a good deal of time being educated on the shortcomings of other quantum algorithms. In this case, the QAOA algorithm iterates between classical and quantum resources. The classical computer prepares a circuit for the quantum computer to run. The quantum computer then finds a solution and feeds it back to the classical computer, which prepares the next circuit. In theory, these iterations continue until you converge on a solution. In this paper, the authors showed the technique works for a small example, yet they didn’t address whether and why it would converge for a larger system – it could run forever and never converge. It’s also unclear how much classical resource is required for each iteration to do the state preparation – the need for too much classical computing could remove the benefit of using the quantum computer.
