6 ms·

You probably mean well, but this is dangerous misinformation. There are no popular public-key encryption schemes that are safe against quantum computing. The o

You probably mean well, but this is dangerous misinformation. There are no popular public-key encryption schemes that are safe against quantum computing. The only popular public-key encryption schemes are based on RSA and ECC, both of which are broken by variants of Shor's algorithm. Yes, popular symmetric cryptography is safe to the best of our knowledge, but that doesn't help much since virtually all symmetric crypto that is actually applicable at scale relies on some initial public-key crypto for bootstrapping. And yes, there's research into post-quantum public-key cryptography, but it's pretty underwhelming so far. It seems possible, but at a horrible loss of performance (keys are sized on the order of kilobytes or more, as opposed to 32 bytes for ECC). I'm pretty pessimistic about the consequences of quantum computing, to be honest.

alfiedotwtf 8y ago
Not sure why you're greyed out (hopefully not because you're being downvoted) because you're absolutely right - all asymmetric cryptography we have right now will be broken. On the other hand... I doubt we'll have working quantum computers for at least the next 500 years.
- WilliamEdward 8y ago
  500 years is a big leap but I appreciate the caution. We actually already do have working quantum computers. If you mean personal quantum computers, commercially, I would give it about a century, give or take a decade.
  - alfiedotwtf 8y ago
    No. I'm talking about quantum computers that are actually practical. Running stable at 0.004K for only a few milliseconds in a lab is not practical.
  - AlexCoventry 8y ago
    "Working" in this context clearly means "able to break deployed cryptosystems." We are a long way from that. https://www.forbes.com/sites/fredcampbell/2018/03/14/how-capable-is-googles-bristlecone-quantum-processor/#32f012f01775 https://www.forbes.com/sites/fredcampbell/2018/03/14/how-cap...
eponeponepon 8y ago
Instinctively, I want to think that post-quantum crypto means both ends. That is to say, if it transpires that quantum computing can break all pre-quantum encryption schemes, it ought to follow that there will be post-quantum encryption schemes that it can't. I don't understand quantum computing well enough to know if that's a reliable instinct though. Is it anywhere near the mark?
- throwawaymath 8y ago
  No, that's not really correct. The theoretical capability of a quantum computer to "collapse" to optimal routes to solutions during computation does not imply the existence of cryptographic trapdoor functions which are likewise intractable. More concisely: the existence of a quantum computer does not imply the existence of problems it cannot solve. They're orthogonal things. That being said, Mahadev's recent research constructing a quantum verification protocol using the LWE is exciting along similar lines to what you're thinking. It allows us to say with authority that one of the following must be true: 1. LWE protocols are not post-quantum resistant, or 2. Quantum verification is possible via LWE-based cryptography.
tptacek 8y ago
SIDH keys can be as small as 330 bytes. That's not much bigger than a modern RSA key. Lattice keys are also in the (higher) hundreds of bytes, and were briefly (as an experiment) deployed in Chrome.
- throwawaymath 8y ago
  In fairness, SIDH trades off the tiny key sizes for a slower key exchange time. Personally I think there's more potential in getting lattice keys smaller since the LWE-type systems are fast.
calhoun137 8y ago
"Damgerous misinformation" to say quantum computers are not magical oracles? The entire subject of QC is literally a hoax! The only danger is that if people dont think they are magical they might want to cut off the funding. If I were to say I know a magical oracle who can break encryption with pure thought, it wouldnt be much different than the kinds of claims you hear about quantum computers on a daily basis. I used to do experimental physics for many years, all of my colleages and I thought quantum computers were a joke. Main stream physics people understand there is an intense debate over whether or not its even possible to build a quantum computer. Nothing to see here, its just the QC hype train doing its thing.
- WilliamEdward 8y ago
  I said this in another comment, but there's two sides to this QC thing: People who think QCs are magic and can do everything, and people who think they know better when they tell people that QCs are not magic and cannot do everything. In reality, you're both slightly skewed. To undermine the potential of QCs is a blunder, as big a blunder as thinking they can do everything. The hype train is exactly where it needs to be.
- Misdicorl 8y ago
  There isn't a debate about whether it's possible since it's already been done... Your comment is either lacking context to explain what you really mean or simple fabrication. Neither is acceptable
  - wbhart 8y ago
    Physcial qubits currently suffer from noise problems and so logical qubits have to be simulated. You can't just implement them directly in a scalable way in hardware. So, you could say that a meaningful, scalable quantum computer of any kind has not yet been built. You can certainly say that a quantum computer capable of breaking real world encryption is very far from current reality.
    - Misdicorl 8y ago
throwawaymath 8y ago
I'm not pessimistic about them. I'm actually (weakly) pessimistic I'll see significant cryptographic breaks due to large scale quantum computers within thirty years. We are very, very far off from quantum computers that can break RSA or even elliptic curve systems (which are a bit easier to break for quantum computers). Google's Bristlecone has 72 physical qubits but I don't recall seeing any published information about how many logical qubits they managed to achieve. Shor's algorithm requires O(n^3) time and 3n logical qubits to break an n-bit key. The state of the art in quantum error correction requires high tens of thousands to low hundreds of thousands of physical qubits to achieve the logical qubits needed to break a typical 2048-bit RSA semiprime. 4096-bit keys are even farther off. Research in post-quantum cryptography is really important, but I think you should take most of the non-scientific reporting about quantum computing and cryptography with a (large) grain of salt. The Economist is actually very level headed in its coverage here and it still neglects to mention that realistically we're far off, even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade. I also think you're being too uncharitable to post-quantum cryptography. You'll find that many of the lattice-based systems (particular the various flavors of LWE) are very fast (and getting faster) and perform reasonably well in real world experiments. I'm cautiously optimistic we'll have lattice-based schemes with keys smaller by an order of magnitude in a decade, and very optimistic we'll have achieved that before 2048-bit RSA can be broken on a quantum computer.
- scottlocklin 8y ago
  Quantum computers have been factoring the number 15 for 20 years now; seems like you're being kind of overly pessimistic. /sarcasm
- lisper 8y ago
  > even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade You seem to be ignoring the possibility of a technological breakthrough that will produce a major improvement in QEC in one fell swoop. Granted that is unlikely, but it's not impossible. And given what is at stake, I think it's a possibility that needs to be taken seriously despite the long odds.
Dylan16807 8y ago
So your argument is that a few kilobytes to bootstrap a session that could last for days isn't feasible? And that if a system isn't 'popular' right now it doesn't count? You have a strange standard for 'dangerous'.
3pt14159 8y ago
I think some combination of a web-of-trust and symmetric cryptography (or even OTPs for the really scary stuff, like code updates to self-driving cars) will work if we need them to. Take Apple (my dev machine) or DigitalOcean (my server provider. They already have root. If my MBP came with a custom-to-me symmetric key to communicate with Apple I could get a signature from them of the symmetric key that DigitalOcean generated for me. The real issue is that everyone is reactive so these types of things don't get fixed until there's a proof-of-concept attack that works. I remember people talking about how states would propagandize social media platforms in the early 2000s and nobody took them seriously; myself included. Though I never mocked them because I didn't see how they were wrong I just saw no evidence that it was happening so I figured someone else was already on it. Nobody is magically on it. National security podcasts are stressing about quantum computers because they know it's probably going to break PKI. The thing I still don't understand about quantum is that it seems to break entropy once you get enough qubits because it covers too many options at once. I keep meaning to experiment with it to understand it better, but I don't have enough time.

alfiedotwtf 8y ago

Not sure why you're greyed out (hopefully not because you're being downvoted) because you're absolutely right - all asymmetric cryptography we have right now will be broken. On the other hand... I doubt we'll have working quantum computers for at least the next 500 years.

WilliamEdward 8y ago
500 years is a big leap but I appreciate the caution. We actually already do have working quantum computers. If you mean personal quantum computers, commercially, I would give it about a century, give or take a decade.
- alfiedotwtf 8y ago
  No. I'm talking about quantum computers that are actually practical. Running stable at 0.004K for only a few milliseconds in a lab is not practical.
- AlexCoventry 8y ago
  "Working" in this context clearly means "able to break deployed cryptosystems." We are a long way from that. https://www.forbes.com/sites/fredcampbell/2018/03/14/how-capable-is-googles-bristlecone-quantum-processor/#32f012f01775 https://www.forbes.com/sites/fredcampbell/2018/03/14/how-cap...

eponeponepon 8y ago

Instinctively, I want to think that post-quantum crypto means both ends. That is to say, if it transpires that quantum computing can break all pre-quantum encryption schemes, it ought to follow that there will be post-quantum encryption schemes that it can't. I don't understand quantum computing well enough to know if that's a reliable instinct though. Is it anywhere near the mark?

throwawaymath 8y ago
No, that's not really correct. The theoretical capability of a quantum computer to "collapse" to optimal routes to solutions during computation does not imply the existence of cryptographic trapdoor functions which are likewise intractable. More concisely: the existence of a quantum computer does not imply the existence of problems it cannot solve. They're orthogonal things. That being said, Mahadev's recent research constructing a quantum verification protocol using the LWE is exciting along similar lines to what you're thinking. It allows us to say with authority that one of the following must be true: 1. LWE protocols are not post-quantum resistant, or 2. Quantum verification is possible via LWE-based cryptography.

tptacek 8y ago

SIDH keys can be as small as 330 bytes. That's not much bigger than a modern RSA key. Lattice keys are also in the (higher) hundreds of bytes, and were briefly (as an experiment) deployed in Chrome.

throwawaymath 8y ago
In fairness, SIDH trades off the tiny key sizes for a slower key exchange time. Personally I think there's more potential in getting lattice keys smaller since the LWE-type systems are fast.

calhoun137 8y ago

"Damgerous misinformation" to say quantum computers are not magical oracles? The entire subject of QC is literally a hoax! The only danger is that if people dont think they are magical they might want to cut off the funding. If I were to say I know a magical oracle who can break encryption with pure thought, it wouldnt be much different than the kinds of claims you hear about quantum computers on a daily basis. I used to do experimental physics for many years, all of my colleages and I thought quantum computers were a joke. Main stream physics people understand there is an intense debate over whether or not its even possible to build a quantum computer. Nothing to see here, its just the QC hype train doing its thing.

WilliamEdward 8y ago
I said this in another comment, but there's two sides to this QC thing: People who think QCs are magic and can do everything, and people who think they know better when they tell people that QCs are not magic and cannot do everything. In reality, you're both slightly skewed. To undermine the potential of QCs is a blunder, as big a blunder as thinking they can do everything. The hype train is exactly where it needs to be.
Misdicorl 8y ago
There isn't a debate about whether it's possible since it's already been done... Your comment is either lacking context to explain what you really mean or simple fabrication. Neither is acceptable
- wbhart 8y ago
  Physcial qubits currently suffer from noise problems and so logical qubits have to be simulated. You can't just implement them directly in a scalable way in hardware. So, you could say that a meaningful, scalable quantum computer of any kind has not yet been built. You can certainly say that a quantum computer capable of breaking real world encryption is very far from current reality.
  - Misdicorl 8y ago

throwawaymath 8y ago

I'm not pessimistic about them. I'm actually (weakly) pessimistic I'll see significant cryptographic breaks due to large scale quantum computers within thirty years. We are very, very far off from quantum computers that can break RSA or even elliptic curve systems (which are a bit easier to break for quantum computers). Google's Bristlecone has 72 physical qubits but I don't recall seeing any published information about how many logical qubits they managed to achieve. Shor's algorithm requires O(n^3) time and 3n logical qubits to break an n-bit key. The state of the art in quantum error correction requires high tens of thousands to low hundreds of thousands of physical qubits to achieve the logical qubits needed to break a typical 2048-bit RSA semiprime. 4096-bit keys are even farther off. Research in post-quantum cryptography is really important, but I think you should take most of the non-scientific reporting about quantum computing and cryptography with a (large) grain of salt. The Economist is actually very level headed in its coverage here and it still neglects to mention that realistically we're far off, even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade. I also think you're being too uncharitable to post-quantum cryptography. You'll find that many of the lattice-based systems (particular the various flavors of LWE) are very fast (and getting faster) and perform reasonably well in real world experiments. I'm cautiously optimistic we'll have lattice-based schemes with keys smaller by an order of magnitude in a decade, and very optimistic we'll have achieved that before 2048-bit RSA can be broken on a quantum computer.

scottlocklin 8y ago
Quantum computers have been factoring the number 15 for 20 years now; seems like you're being kind of overly pessimistic. /sarcasm
lisper 8y ago
> even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade You seem to be ignoring the possibility of a technological breakthrough that will produce a major improvement in QEC in one fell swoop. Granted that is unlikely, but it's not impossible. And given what is at stake, I think it's a possibility that needs to be taken seriously despite the long odds.

Dylan16807 8y ago

So your argument is that a few kilobytes to bootstrap a session that could last for days isn't feasible? And that if a system isn't 'popular' right now it doesn't count? You have a strange standard for 'dangerous'.

3pt14159 8y ago

I think some combination of a web-of-trust and symmetric cryptography (or even OTPs for the really scary stuff, like code updates to self-driving cars) will work if we need them to. Take Apple (my dev machine) or DigitalOcean (my server provider. They already have root. If my MBP came with a custom-to-me symmetric key to communicate with Apple I could get a signature from them of the symmetric key that DigitalOcean generated for me. The real issue is that everyone is reactive so these types of things don't get fixed until there's a proof-of-concept attack that works. I remember people talking about how states would propagandize social media platforms in the early 2000s and nobody took them seriously; myself included. Though I never mocked them because I didn't see how they were wrong I just saw no evidence that it was happening so I figured someone else was already on it. Nobody is magically on it. National security podcasts are stressing about quantum computers because they know it's probably going to break PKI. The thing I still don't understand about quantum is that it seems to break entropy once you get enough qubits because it covers too many options at once. I keep meaning to experiment with it to understand it better, but I don't have enough time.