> As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm
Isn't that also huge news, depending on the definition of "often"?
Isn't that also huge news, depending on the definition of "often"?
Also, while new, this result isn't really surprising. That Grover's algorithm can be applied to get a quadratic improvement over existing classical search algorithms has been known for a long time.
I wonder if a quantum computing revolution would cause a resurgence of research into symmetric encryption algorithms?
Because doesn't Shor's algorithm basically destroy asymmetric encryption (i.e., integer-factorization schemes like RSA are solvable in polynomial time), while symmetric encryption is only weakened? Namely, I think I remember reading that a quantum computer can search through a space of size 2^n in time 2^(n/2) for AES & friends.
I believe you're thinking of Grover's algorithm, which as you remember offers the ability to search for a value in a function domain in O(sqrt(N)). This is trivially countered just by doubling the key length, a 128-bit key probably couldn't be considered secure (average 2^64 evaluations) but a 256-bit would still average 2^128 and 512-bit 2^256. I vaguely recall there was some speculation that applied de Broglie–Bohm theory, if it was accurate, could allow a mild improvement but even then it only changed it to cube-root, which again could be countered with slightly larger keys (in practice 512-bit would still be plenty even then).
At least for now there don't appear to be any major algorithmic implications for symmetrical encryption from a theoretical future scalable general purpose quantum computer. Granted, there may be some practical historical ones, and in a few cases they could be of significance. If agencies have archived data of interest encrypted with 128-bit in the past, they may gain the ability to gain access to it within the next decade or two. A lot of it might be well past its proverbial sell-by date but not all if those using it were counting on it last much longer then they'd be alive.
EDIT: Also note that quantum cryptanalytic attacks may be able to break specific symmetric ciphers by exploiting some structure specific to the cipher. But you're correct that QCs don't generically break symmetric cryptography.
Then it constructs a 1 terabyte RSA parameter, so big neither algorithm can currently attack it using a computer (quantum or otherwise) of practical size, as all known quantum attacks (including the new presented) would still need over a 2¹⁰⁰ workfactor; the 2³¹ factors they would need to find are each 4096 bits long themselves, if I'm reading it right?
Needless to say, that is a trifle on the heavy side and definitely isn't your first practical choice (those would be lattice-, code- or hash-based primitives), but it is possible, and that's impressive (to me) by itself! Nice work.