Score:18

Crypto

Will IBM's Condor quantum processor run Shor's Algorithm to crack a 256-bit Elliptic Curve key?

Simon G.

11/10/23, 10:07 AM

Yesterday IBM announced that they have a 433 bit quantum computer, called Osprey. There is nothing in the press releases I can find that says whether it can or cannot run Shor's Algorithm.

They also say they are on track to release "Condor", an 1121 bit processor next year.

Shor's algorithm, as far as I know, requires twice the number of bits in the key, so a 256 bit key requires 512 qubits to crack. Hence Osprey cannot do this, but apparently Condor will be able to.

256-bit keys are widely used - for example Ed25519 as used by Bitcoin, and is a valid TLS algorithm.

Is it expected that Osprey will be able to run Shor's algorithm?

If it can, how can the loss of security best be mitigated?

5005

1 + 3

post-quantum-cryptography

quantum-cryptography

cryptocurrency

shors-algorithm

fgrieu

11/10/23, 11:00 AM

I have yet to find any claim that a physical quantum computer has run Shor's algorithm to factor an integer larger than 21. And then it's disputed if such claimed implementations of Shor's algorithms factor, or verify a known result. See [Largest integer factored by Shor's algorithm?](https://crypto.stackexchange.com/q/59795/555) for details and references. I don't make this comment an answer because I can't make an independent informed opinion, for I know too little on Quantum Computers and Shor's algorithm, and next to nothing on Osprey.

user4574

11/10/23, 10:22 PM

It wasn't using Shor's algorithm, but I believe Collin Williams demonstrated factoring numbers using N^2 QBITS on a D-Wave quantum computer. I believe he was able to factor numbers up to 16 bits using the machine he had at the time.

R.. GitHub STOP HELPING ICE

3/7/24, 2:08 AM

@user4574: That falls under "Stunts" in this answer: https://crypto.stackexchange.com/a/59796/7218

Score:25

Crypto

Daniel S

11/10/23, 11:01 AM

No. The issue here is the distinction between physical qubits and logical qubits. The back of the envelope estimate for Shor's algorithm for a 256-bit elliptic curve is 512 logical qubits, but a more accurate costing by Roeteller et al is 2330 logical qubits.

Logical qubits are idealised computational resources that would need a perfectly engineered physical qubit to achieve. The Osprey chip and its ilk have physical qubits that degrade over time and perform operations with a certain error rate. Instead several physical qubits of the Osprey sort would be need to emulate the behaviour of a logical qubit using quantum error correction. Estimates for the number of physical qubits required to break 256-bit ECC in one hour (and these physical qubits would still be to a high engineering specification, perhaps beyond that of Condor) is $317\times 10^6$ per work by Webber et al. Similarly, they quote $13\times 10^6$ physical qubits of this high quality to solve this problem inside a day.

+ 5

fgrieu

11/10/23, 11:18 AM

The second citation is: Mark Webber, Vincent Elfving, Sebastian Weidt and Winfried K. Hensinger: _The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime_, in AVS Quantum Science (2021), doi: [10.1116/5.0073075](https://doi.org/10.1116/5.0073075). It flies high over my head but I like the idea that we can make such estimates. I hope I'll someday be proven pessimistic for conjecturing human civilization will never get to [CRQC](https://crqc.grieu.fr).

Simon G.

11/10/23, 11:33 AM

For those who read this answer, the estimate of 317 million qubits is to break the 256-bit key within one hour assuming certain hardware properties. The same paper estimates 13 million required to break in 24 hours.

Daniel S

11/10/23, 1:54 PM

Thanks fgrieu, Simon G, I have incorporated both of your comments into the answer.

Daniel S

11/10/23, 6:45 PM

@DeanMacGregor I'm afraid those were the headline data points picked by the authors, though their methodology could produce others. The qubits to time relationship is certainly not (inverse) linear as the longer and more operations that a logical qubit has to exist for increases the number of physical qubits need to emulate it. The two data points therefore might represent the most achievable values, thought the authors would know better.

Daniel S

11/10/23, 7:03 PM

Further to the above, fig. 1 of the paper seems to suggest a hard-ish lower bound of around $8\times 10^6$ physical qubits of the chosen specification.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Will IBM's Condor quantum processor run Shor's Algorithm to crack a 256-bit Elliptic Curve key?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.