On 14/12/2024 18:54, coderman wrote:
On Thursday, December 12th, 2024 at 11:20 PM, Peter Fairbrother <peter@tsto.co.uk> 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