[Discuss] Fwd: Quantum Crypto redux Re: Boston Linux Meeting ... Crypto News, plus ...

[bill.n1vux at gmail.com (Bill Ricker)]

Elliott is correct that ECC including Curve25519 as well as NIST P-* curves
are more affected  by QC (Shor's) than RSA ... in part because our
classical factoring technology had such a head start, has gotten so good,
that RSA keys have gotten huge, but discrete log remained hard, so ECC
remains small(er)-data, so a classically recommended-keysize problem fits
in fewer QuBits.

Having a 20x safety factor on announced QuBits today is fine for commercial
attack safety today, but for how much longer?
(The good news is AES and hashes only need to double in size to resist
Grover's algorithm in Quantum, they say. )

Partial retraction -- the D-Wave machines with ridiculous numbers of QuBits
are Quantum Annealers, not general purpose Quantum Computers. (It did seem
obvious there was something different about them, from the interleaved
series of records of different orders of magnitude. Now I know what!)
Annealers are good for some kinds of non-linear search problems, but the
two Quantum Computing algorithms known to theoretically plague
public-key/asymmetric and private-key/symmetric  cryptography, Shor's and
Grover's  respectively, are not among the Simulated Annealing algorithms.
So $15M for 2kQuBit D-Wave isn't yet scary for crypto even though
Curve25519  can be solved by < 1600 QuBits in theory, because the (open)
record for the general QC logic machine remains at 72 QuBits, a safety
factor of 20.

QuBits aren't QUITE on the Moore's Law 18-month doubling cycle yet; my
back-of-the-envelope shows going from 7 QuBits to 72 QuBits in 16 years is
doubling in 28 months.  Which is kinda close to Moore's law for RAM (24
months)...
How soon the engineering will allow a growth spurt is unclear.

So setting my ED25519 key expiration at 10 years was just about right, :-)
that's just exactly when it should be doable commercially :-).
A little shorter would have been more conservative!

(I do wonder if D-Wave could be used for Hill-Climbing attack on some
classic crypto problems e.g. Wheatstone/Playfair, but wouldn't be cost
effective there. :-)  )




-- 
Bill Ricker
bill.n1vux at gmail.com
https://www.linkedin.com/in/n1vux