Re: State of Post Quantum Cryptography?

On 10/05/2024 17:28 Peter Fairbrother <peter@tsto.co.uk> wrote:

On 10/05/2024 07:32, Jakob Bohm wrote:

On 2024-05-09 23:28, Peter Fairbrother wrote:

 

You would need about 1,000 reliable entangled error-free qubits
equivalent (REEFQe) to do any useful cryptanalysis of present day
public key algorithms, and we are nowhere near that. Not even 100
REEFQe, more like 20.

 

Would those numbers apply to things like EdDSA and ECDSA?

 
A thorny question.
 
The publicity for quantum computers is usually splashed about measured
solely in qubits (approximately, quantum storage bits, a bit like a
register in a cpu with only one register); but that's not immediately
relevant to the amount of computation they can do - they also need
quantum gates, qubits by themselves can't do any computing.
 
So even 1,000 "real" qubits is just a very rough ballpark figure which
doesn't actually mean very much.
 
 
In terms of comparing breaking RSA and breaking ECDSA, you would need
more qubits but less gates for RSA - but as you can, above some
minimums, pretty much swap needed qubits for needed gates, that doesn't
help much.
 
I believe the minimum number of "real" qubits needed is about 350 for
ECDSA and about 1,000 for RSA[1]; but at that level breaking ECDSA needs
a LOT more quantum gates.
 
Overall it's pretty hard to say which is easier to do, and would depend
on more than the number of qubits a computer has. Quantum gates are
noisy too, especially the ones which do entanglement.
 
 
 
[1] I could be wrong here, I'm a bit out-of-touch. And these are
_theoretical_ minimums, and even then estimates vary, a lot.
 
In practice, realistically the best I've seen uses about 6,000 real
qubits and 10^12 gates to break 2k RSA in months. You would also need a
depth of about 10^11 (depth is the longest chain of quantum gates used,
and they all have to work...)
 
 
We are closer to getting to Alpha Centaurus and taming fusion than doing
that.
 
 
Peter Fairbrother
 
 

<https://www.space.com/purest-silicon-could-lead-to-first-million-qubit-quantum-computing-chips>

They now believe they can build million-qubit processors using ultra-pure silicon.