- PsiQuantum publishes a resource tally for how big a quantum computer is needed to influence Elliptic Curve Cryptography, or ECC.
- PsiQuantum uses a fault-tolerant quantum computing architecture to achieve a 700 times reduction in computing resources to crack ECC keys.
- This is orders of magnitude less time to calculate than the billions of years it would take a conventional computer.
PERS CONFERENCE – PsiQuantum announced today in a new publication, a comprehensive resource tally for how large a quantum computer is needed to influence commonly used cryptographic systems – namely Elliptic Curve Cryptography (ECC) – given the new fault-tolerant quantum computing architecture the company introduced recently. This active volume architecture leverages remote connections within a quantum computer and results in a 700x reduction in computational resource requirements for cracking ECC keys relative to advanced quantum algorithms. It is also an order of magnitude less time to compute than the billions of years it would take a conventional computer to perform the equivalent task for a 256-bit ECC key.
Secure digital communications, which underpin our modern internet usage, rests on the success of public key cryptographic systems. This cryptographic system works by allowing users to provide a public key, with which anyone can securely encode messages to them. These messages can then only be decoded with the secret private key held by the user. The keys for encoding and decoding are constructed from mathematical operations that are easy to implement (for encoding), but difficult to reverse (for decoding). The difficulty of decoding hinges on the fact that reversing these mathematical operations is an impractical time-consuming task for conventional computers.
Two schemes that stand out are RSA and elliptic curve cryptography (ECC). In RSA, the mathematical operations used to provide public and private keys center on the ease of multiplying two prime numbers, rather than the difficulty of the inverse process – recovering these prime factors. The approach taken by ECC is a little more nebulous, but the concepts are similar. Public key encoding can be done using a mathematical operation known as elliptic curve point multiplication, and reversing this process to decode a message is difficult without the information contained in the private key.
RSA and ECC keys can be easily cracked using large-scale quantum computers. Algorithms have been devised for quantum computers that can, unlike conventional computers, efficiently reverse the mathematical operations at the heart of RSA and ECC. Several research papers have explored quantum algorithms for RSA and ECC key generation in the last few decades. Surprisingly, even though it involves more mathematically complex operations, cracking a 256-bit ECC key is easier than cracking a 2048-bit RSA key, thanks to the shorter key requiring fewer resource-intensive arithmetic operations.
In this paper, PsiQuantum discovers an architecture-independent improvement to the existing ECC quantum algorithm that reduces the number of gates needed to crack ECC keys by up to 80%. The team also undertook a resource estimate to implement the ECC quantum algorithm using the newly launched PsiQuantum active volume architecture technique (Read more) which leads to a reduction in the number of quantum operations required to crack an ECC key by up to 700x.
The active volume compilation technique is especially applicable to photonic architectures, such as PsiQuantum. This is because the technique relies on being able to have remote connections within a quantum computer and currently only photonic architectures have this feature. Unlike matter-based qubits such as ion traps or superconducting qubits, photons have the ability to connect easily non-locally using conventional optical fibers, such as those widely used in the telecommunications industry.
So are all our secrets at risk of being stolen? Not yet. Despite this breakthrough, cracking a 256-bit ECC key still requires a quantum computer that has millions of physical qubits. Although photonic quantum computers could reduce the required system size, this would still require much larger machines than what we currently have. However, researchers are actively preparing for that possibility with the development of post-quantum cryptographic schemes such as lattice cryptography, and recommendations to use longer RSA or ECC keys in the meantime. This approach is supposedly secure against quantum algorithms, and moreover other emerging technologies may actually offer encryption schemes that are provably secure against quantum algorithms.
Prof. Terry Rudolph, Chief Architect and Co-Founder of PsiQuantum, said: “These results illustrate a characteristic property of the quantum computing field, namely that although much progress has been made through slow and painful incremental development, it is also not surprising. to see a big leap forward by an order of magnitude or more. Because of these uncertainties, as well as the potentially high impact of the technology, companies and organizations developing quantum computers bear a serious responsibility to ensure that quantum computing is used in a responsible and transparent manner. This is why we chose to publish our method in the public domain.”
VADM (Ret.) Robert D. Sharp, former Director of the National Geospatial-Intelligence Agency, said: “I am applauded and comforted by PsiQuantum’s relentless commitment to ensuring that we maintain our competitive edge in strategic technologies such as quantum computing; one with such broad applications and – arguably – some of the most profound national security implications the US and our allies will face this century. As well as being impressed with what the company does, I appreciate how seriously and strategically they take it – learning quickly and iteratively, and approaching technology as a committed and transparent partner to the US and allied governments as they reach important milestones.”