I’m not gonna dig up the links since I’m sure y’all’re already tired of talking about quantum computing. I am going to insist that, while I professionally disagree with Filippo about plenty of things, I do not see any mistakes in their analysis here. Please start thinking about post-quantum cryptographic tooling today.
I feel like the same “<1%” argument is used to justify a whole lot of things these days. Can you guarantee that there’s a <1% chance that someone will come out next year with a paper showing that LWE can be broken efficiently with a quantum algorithm? What about a classical algorithm? I feel like a better argument is needed than just “well you can’t be sure it won’t happen” because we aren’t sure about pretty much anything.
First, I personally don’t yet believe in the cryptographic security of LWE on lattices. I agree that it sure looks hard, but we don’t have a solid proof. But also, I don’t believe that we’ve found any provably one-way functions in the classical regime either. So I agree with you from different premises.
Unlucky 10,000: Shor’s algorithm speeds up any discrete logarithm. It actually speeds up the abelian HSP. This does give us a theoretical reason to expect that LWE on lattices won’t fall to Shor’s approach, as the underlying groups are non-abelian. It does make me sad for elliptic curves, though; they’re so elegant and the keys are so small.
Not sure what you think my “different premises” are? Also I obviously already know that Shor’s algorithm solves the discrete log problem. I don’t know why you phrased your comment assuming I’m an idiot.
I will say that, speaking as an idiot, I appreciated the information and the accessibility of many of these very technical conversations here is one of the elements of this community I appreciate. I would be very surprised if it had been meant as any kind of dig instead of explicitly clarifying a usually-unstated bit of context.
I think the main difference here is that breaking RSA now just requires scaling up existing approaches, while breaking LWE or anything like that would need a major conceptual breakthrough. The former possibility is much more likely, and in any case, cryptographers are the most paranoid people on the planet for a reason.
Unfortunately, one can never be sure about much in cryptography until P vs NP is solved (and then some).
(Of course, just because some people say that scaling up is enough doesn’t mean it’s actually true. For breaking RSA, we know have Shor’s algorithm, while the only evidence AI bros have from superintelligence coming from scaling is “trust me bro”.)
Yeah and I agree that in principle we should be trying to move to cryptosystems which aren’t known to be broken by quantum algorithms. I just don’t think the argument in the article is sound. There are costs, including actual security risks, inherent to switching. To name a couple:
- There will be implementation errors any time a new cryptosystem is implemented; this is practically inevitable especially if you are trying to rush the process through in 3 years.
- Quantum-unbroken systems are slower and require bigger keys than elliptic curve systems. Users will be inconvenienced by the resulting performance hit, which will both impede adoption of cryptography in general, and tempt implementors into using incorrect parameters.
You have to actually weigh the benefits of resistance to quantum computers (which may or may not actually appear) against these costs (which certainly will). Paranoia isn’t a threat model.
And to be clear cryptographers already know these things and if they still think we should all move to lattice cryptosystems despite the costs then that’s totally fine. I just wish they would write their blog posts to reflect that instead of talking about the 1% thing.
Very interesting, thanks for posting.