On 14/12/2024 18:54, coderman wrote:
On Thursday, December 12th, 2024 at 11:20 PM, Peter Fairbrother
<[email protected]> wrote:
... 10k-qubit entangled arrays with daylong lifetimes are
centuries away, not decades. And QEC sucks.
you're wrong Peter, you just don't know it yet...
And why is that?
There are two algorithms we might be concerned with. Let's take Grover's
first.
Grover's finds matches on a search. To be cryptographically useful
against ciphers the search space will usually only have one correct
match. However it isn't any good (=slower than classical overall, even
if it uses fewer queries) for random or pseudo-random searches, you need
a fast phase oracle - which for cryptographic attacks often doesn't exist.
Oooh it looks scary, a quadratic speedup - but only in special
circumstances, which do not really occur in cryptography. And it is only
a lessening of the number of search operations, while each search takes
longer than a classical search, and how much longer depends on how big
the search space is - typically ending up slower than classical overall.
Look at it from an information perspective. If the search space is
random, there are 2^n words of information in the search space. These
have to be available somehow, else the algorithm, quantum or not, cannot
find the answer (it won't be in there).
The exception is where a fast phase oracle can be used - a phase oracle
finds the difference between states, but it cannot exist for a random
search. It is part of a single Grover quantum search operation, repeated
on each qubit for each operation.
For ciphers and hash functions, such oracles can be constructed, but eg
for AES-128 the best known attack I know of uses 2^77 gates, an
implausible number, and an uncorrected error-free DW of 2^85.
Not. Going. To. Happen.
To do a Grover's search you would need an entangled register of n bits
for a search space of size 2^n, so maybe this register might be possible
for a 128-bit or 256-bit space, though it hasn't been done yet. The
oracle, in practice - with 2^77 quantum gates - nope, not this century.
However all this is moot as, as I have said before, keylengths and hash
sizes have increased to the point that (even if the time taken by the
phase oracle can be ignored) it would take too long,
lifetime-of-the-universe-long, to implement Grover's against any cipher
or hash.
Turning to Shor's algorithm(s), these are some classical math on twin
large primes (RSA) or modular exponentiation (DH) plus a cycle length
finding quantum algorithm common to both. They look for hidden subgroups
in Z*p groups caused by and the size of factors of p-1, so if you use
safe primes (p=2q+1. p and q prime) the only subgroups are of size 2 and
q, and for a big prime q and thus the cycle length is also big. The
bigger the cycle, the harder it is to find using Shor's.
So don't use speedup-optimisations where p-1 has a 128 or 256-bit
factor, use safe primes (or use primes where p-1 has a factor least 2/3
n bits long).
And magically Shor will be slower than classical or not work at all,
even assuming "they" have a working quantum computer.
Some people say that QEC will make Shor possible despite this, but I
don't know of any suitable QEC method which will work on more than
single unentangled qubits. The quantum threshold theorem threshold has
probably been passed, but that doesn't make QEC practical for Shor's.
Of course in practice it doesn't actually work anyway. To factor a 2kbit
RSA number Shor needs about a 10k qubit entangled register with a long
error-free lifetime; which is much further away than commercial fusion
power, if ever.
Peter Fairbrother
