4 ms·

Wait, so can quantum computers now crack public key cryptography, or not?

by zkhalique 12y ago

rnovak 12y ago
Looks like the algo attacked was already a quantum algorithm, not classical computing algorithm.
- rbanffy 12y ago
  No - it's classical, but it was, until now, considered resistant to quantum algorithms (as in a QC would not yield a significant improvement over a classical computer).
gliese1337 12y ago
Only if we can actually build general purpose quantum computers. The news here is that a new quantum algorithm has been developed to attack public key cryptography; other quantum algorithms that attack certain kinds of cryptography were already known. None of them matter practically until we have computers that can actually run them, which we don't, but the discovery of another new attack algorithm means that developing such computers would be a slightly bigger deal than we thought it was before.
- apendleton 12y ago
  This one is also noteworthy because the algorithm it attacks was developed specifically with resistance to quantum attacks in mind, unlike the breed of public-key crypto currently in use, which is widely known to be vulnerable to quantum attacks.
  - tptacek 12y ago
    That may be true of Soliloquy, but I'm not sure it's the case that lattice problems were originally researched as an antidote to QC. Lattice theory has applicability to cryptography in general, so it's natural that people explored its suitability as a crypto primitive. I don't think it's reasonable to draw the conclusion from this paper that "cryptographers set out to foil QC and in this case failed". One derivative scheme in a broad class of lattice crypto designs fell, that's all. Lattice crypto has very strong post-quantum crypto marketing, because of NTRU.
- tptacek 12y ago
  The news here is that a new quantum algorithm has been developed to attack one very specific form of public key cryptography.
gruntled 12y ago
If anyone can build a big enough quantum computer (enough qubits) and prevent it decohering (that is, keeping it quantum long enough) to run Shor's algorithm, standard public key crypto like RSA would be broken. That has been known in theory since the 90s. But if anyone ever builds such a quantum computer it isn't necessarily the end for public key crypto because there is a workaround that will work on classical computers, and that is to avoid trapdoor functions that can be broken by Shor's algorithm. So if a quantum computer comes along that can break, say, 256 bit RSA, we can save public key crypto by everyone switching to a different algorithm. That's the idea of post-quantum cryptography. And although RSA might be broken by a future quantum computer we can still have some sort of public key cryptography. From the looks of this blog post, though, one of the new post-quantum public key algorithms can be broken. At least it could be if anyone ever makes a big enough quantum computer. And there's still the possibility that someone will find a trapdoor function that will be quantum resistant, so it isn't the end for all public key crypto. tl;dr One more public key scheme might have fallen to a quantum algorithm. But the quantum hardware isn't there yet, so it's OK for now.
- SapphireSun 12y ago
  I talked to a dude who made an interesting point about quantum computers. Quantum computations rely on particles behaving in a "quantum manner" in order for Shor's algorithm to reduce the big O complexity in factoring integers. However, at a certain size, you won't be able to entangle all the particles because there will be so many they'll start to behave like a macro material. If true, this implies that quantum methods will only work up to a certain key size. Above that, you could run quantum computers in parallel, but now you're scaling your efficiency linearly instead of super-linearly, so hopefully having a huge (maybe impractically huge?) key size would be a sufficient defence. I understand that RSA gets substantially slower with larger keys though, so maybe it wouldn't be practical even if the key fits easily in memory. I'm not an expert in physics or security, but I'd love for a physicist or cryptographer to comment as I thought that was a really intriguing argument.

Wait, so can quantum computers now crack public key cryptography, or not?

rnovak 12y ago

Looks like the algo attacked was already a quantum algorithm, not classical computing algorithm.

rbanffy 12y ago
No - it's classical, but it was, until now, considered resistant to quantum algorithms (as in a QC would not yield a significant improvement over a classical computer).

gliese1337 12y ago

Only if we can actually build general purpose quantum computers. The news here is that a new quantum algorithm has been developed to attack public key cryptography; other quantum algorithms that attack certain kinds of cryptography were already known. None of them matter practically until we have computers that can actually run them, which we don't, but the discovery of another new attack algorithm means that developing such computers would be a slightly bigger deal than we thought it was before.

apendleton 12y ago
This one is also noteworthy because the algorithm it attacks was developed specifically with resistance to quantum attacks in mind, unlike the breed of public-key crypto currently in use, which is widely known to be vulnerable to quantum attacks.
- tptacek 12y ago
  That may be true of Soliloquy, but I'm not sure it's the case that lattice problems were originally researched as an antidote to QC. Lattice theory has applicability to cryptography in general, so it's natural that people explored its suitability as a crypto primitive. I don't think it's reasonable to draw the conclusion from this paper that "cryptographers set out to foil QC and in this case failed". One derivative scheme in a broad class of lattice crypto designs fell, that's all. Lattice crypto has very strong post-quantum crypto marketing, because of NTRU.
tptacek 12y ago
The news here is that a new quantum algorithm has been developed to attack one very specific form of public key cryptography.

gruntled 12y ago

If anyone can build a big enough quantum computer (enough qubits) and prevent it decohering (that is, keeping it quantum long enough) to run Shor's algorithm, standard public key crypto like RSA would be broken. That has been known in theory since the 90s. But if anyone ever builds such a quantum computer it isn't necessarily the end for public key crypto because there is a workaround that will work on classical computers, and that is to avoid trapdoor functions that can be broken by Shor's algorithm. So if a quantum computer comes along that can break, say, 256 bit RSA, we can save public key crypto by everyone switching to a different algorithm. That's the idea of post-quantum cryptography. And although RSA might be broken by a future quantum computer we can still have some sort of public key cryptography. From the looks of this blog post, though, one of the new post-quantum public key algorithms can be broken. At least it could be if anyone ever makes a big enough quantum computer. And there's still the possibility that someone will find a trapdoor function that will be quantum resistant, so it isn't the end for all public key crypto. tl;dr One more public key scheme might have fallen to a quantum algorithm. But the quantum hardware isn't there yet, so it's OK for now.

SapphireSun 12y ago
I talked to a dude who made an interesting point about quantum computers. Quantum computations rely on particles behaving in a "quantum manner" in order for Shor's algorithm to reduce the big O complexity in factoring integers. However, at a certain size, you won't be able to entangle all the particles because there will be so many they'll start to behave like a macro material. If true, this implies that quantum methods will only work up to a certain key size. Above that, you could run quantum computers in parallel, but now you're scaling your efficiency linearly instead of super-linearly, so hopefully having a huge (maybe impractically huge?) key size would be a sufficient defence. I understand that RSA gets substantially slower with larger keys though, so maybe it wouldn't be practical even if the key fits easily in memory. I'm not an expert in physics or security, but I'd love for a physicist or cryptographer to comment as I thought that was a really intriguing argument.