PsiQuantum publishes paper projecting a 700x reduction in the computational resource requirements for breaking Elliptic Curve Cryptography using a fault tolerant quantum computer

PsiQuantum’s latest paper describes a more efficient method to break Elliptic Curve Cryptography (ECC) which is widely used for secure communications. This approach uses techniques especially applicable to photonic architectures, and reduces the number of gate operations required to break an ECC key by up to 80% as well as a 700x reduction in computation time relative to the state-of-the-art quantum algorithms.

PALO ALTO, Calif.–(BUSINESS WIRE)–PsiQuantum announced today in a new publication, a thorough resource count for how large a quantum computer is needed to impact a commonly used cryptosystem – namely Elliptic Curve Cryptography (ECC) – considering a novel fault-tolerant quantum computing architecture that the company recently introduced¹. This active volume architecture leverages long-range connections within the quantum computer and results in a 700x reduction in the computational resource requirements for breaking ECC keys relative to state-of-the-art quantum algorithms. This is also orders of magnitude less time to compute than the billions of years required by conventional computers to perform the equivalent task for a 256-bit ECC key.

Secure digital communications, which underpin our modern use of the internet, rests on the success of public-key cryptographic systems. These cryptographic systems work by allowing a user to provide a public key, with which anyone can securely encode messages to them. These messages can then only be decoded with a secret private key held by the user. These keys for encoding and decoding are built from mathematical operations which are easy to apply (for the encoding), but hard to reverse (for the decoding). The difficulty of the decoding relies on the fact that reversing these mathematical operations is an impractically time-consuming task for conventional computers.

Two prominent such schemes are RSA and elliptic curve cryptography (ECC). In RSA, the mathematical operation used to provide the public and private keys centers around the ease of multiplying two prime numbers, compared with the difficulty of the inverse process – recovering these prime factors. The approach taken by ECC is a little more obscure, but the concept is similar. Public key encoding can be performed using a mathematical operation known as elliptic curve point multiplication, and reversing this process to decode the messages is hard without information contained in a private key.

Both RSA and ECC keys could be easily broken using large-scale quantum computers. Algorithms have been discovered 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 the generation of RSA and ECC keys in the past decades. Surprisingly, although it involves more mathematically complex operations, breaking 256-bit ECC keys is easier than breaking 2048-bit RSA keys, thanks to the shorter keys needing fewer resource-intensive arithmetic operations.

In this paper, PsiQuantum uncovered architecture-independent improvements to existing ECC quantum algorithms that reduce the number of gates required for breaking ECC keys by up to 80%. The team also conducted a resource estimate for implementing ECC quantum algorithms using PsiQuantum’s newly unveiled active volume architecture technique (read more) which led to a reduction in the number of quantum operations needed to crack an ECC key by up to 700x.

The active volume compilation technique is especially applicable to photonic architectures, like that of PsiQuantum’s. This is because the technique relies on the ability to have long-range connections within the 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 be easily non-locally connected using conventional optical fiber, as widely used in the telecommunications industry.

So, are all our secrets at immediate risk of being stolen? Not yet. Despite these breakthroughs, cracking 256-bit ECC keys still requires quantum computers having millions of physical qubits. Even though photonic quantum computers can reduce the size of the required system, this still requires a machine much larger than what we have today. Nevertheless, researchers are actively preparing for that eventuality with the development of post-quantum cryptography schemes such as lattice cryptography, and the recommendation of using longer RSA or ECC keys in the meantime. These approaches are suspected to be secure against quantum algorithms, and moreover other developing technologies can actually offer encryption schemes that are provably secure against quantum algorithms.

Prof. Terry Rudolph, Chief Architect and Co-Founder at PsiQuantum, said:

“These results illustrate a characteristic property of the field of quantum computing, which is that while much progress is made through slow and painful incremental development, it is also not surprising to see huge leaps forward by an order of magnitude or more. Because of this unpredictability, as well as the high potential impact of the technology, companies and organizations which are developing quantum computers carry a serious responsibility to ensure that quantum computing is deployed in a responsible and appropriately transparent way. This is why we are choosing to publish our methods in the public domain.”

VADM (Ret.) Robert D. Sharp, former Director of the National Geospatial-Intelligence Agency, said:

“I applaud and am comforted by PsiQuantum’s relentless commitment to ensuring that we maintain our competitive edge in strategic technologies like quantum computing; one with such widespread applications and – arguably – some of the most profound national security implications the US and our allies will face this century. Beyond being impressed by what the company is doing, I appreciate how thoughtfully and strategically they’re doing it – learning rapidly and iteratively, and approaching the technology as a committed and transparent partner to the US and allied governments as they reach critical milestones.”

About PsiQuantum

Powered by breakthroughs in silicon photonics and fault-tolerant quantum architecture, PsiQuantum is building the first utility-scale quantum computer to solve some of the world’s most important challenges. PsiQuantum’s approach is based on single-photon qubits, which have significant advantages at the scale required to deliver a fault-tolerant, general-purpose quantum computer. With their photonic chips manufactured in a world-leading semiconductor fab, PsiQuantum is uniquely positioned to deliver quantum capabilities reaching the scale needed to drive advances in climate technologies, pharmaceuticals, healthcare, finance, energy, agriculture, transportation, communications, and beyond. To learn more, visit www.psiquantum.com.

Follow PsiQuantum: LinkedIn

Link to paper: https://arxiv.org/abs/2306.08585

© 2023 PsiQuantum. PsiQuantum and the PsiQuantum logo are registered or pending registration trademarks of PsiQuantum, Corp., in the United States and other countries.

¹ https://arxiv.org/abs/2306.08585

Contacts

media@psiquantum.com
Jacqueline Tame
Tel: +1 (512) 554-9718