> "Shor's algorithm is the attack that was developed in the absence of a quantum computer,” Frincke said. “It's hard to predict what people will actually do with one."
Once QC actually manifests we may find new properties and new approaches to attacking existing algorithms, and being 'quantum hard' before that point is impractical.
I'm not a cryptographer by any means, so I have no idea if this is actually the case. Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms.
> Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms.
We don't have any theoretical proof that we can even encrypt against classical computation. It's still technically an open problem if P=PSPACE (as well as P=NP). All encryption (quantum or not) would be broken if we could effectively solve PSPACE-hard problems.
So really, nobody can truly say any encryption can hold up anywhere. But we still usually have a good idea of the truth of things simply based on empirical evidence - we don't think anybody is proving P=NP, much less P=PSPACE. We don't think people are going to crack our best classical encryption without brute force.
There's not as much empirical evidence that our current quantum encryption will hold up, which is the point of the assertion "it's hard to predict what people will actually do [with shor]"
I feel like 1) that is the key quote, 2) it's true, 3) it's also setting the bar too high for current efforts.
The first go at a post-quantum public-key crypto standard may in effect be (a public-key analog of) the DES that'll need be replaced with an AES someday. But provided we can get something that isn't a step backwards in classical security (so, well-studied problem) and doesn't fall to Shor's algorithm or any other thing we can find in a few years, that's way ahead of where we are now.
We may be feeling around in the dark because we don't know much about quantum computing, but we may also have to do that if we want reasonable security when the first big quantum computers show up.
> "Shor's algorithm is the attack that was developed in the absence of a quantum computer,” Frincke said. “It's hard to predict what people will actually do with one."
Once QC actually manifests we may find new properties and new approaches to attacking existing algorithms, and being 'quantum hard' before that point is impractical.
I'm not a cryptographer by any means, so I have no idea if this is actually the case. Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms.