5 ms·

Looks like an arms race to me. Whoever can get to it faster gets to decrypt the existing algorithms. Can someone more knowledgable validate this?

dlubarov 8y ago
It sounds like the money is going through the NIST and NSF, so presumably any resulting research will become public. If the government wanted to keep the research secret, I would expect the money to go to the CIA or somewhere else.
- whatshisface 8y ago
  Typically it would be the NSA that worked on secret cryptographic technology, although this might distract them from their charter of bugging civilians... (Having a quantum computer may not help with that because they would probably want to keep it secret and not build enough to decrypt everybody's SSL)
imhoguy 8y ago
Still this works the best: https://www.xkcd.com/538/ https://www.xkcd.com/538/
- adrianN 8y ago
  First you need to find out on who to apply the $5 wrench. That's a lot easier if you can monitor all communication.
akvadrako 8y ago
There are two major points to clarify this characterisation: · Existing algorithms are not proven to be secure, even classically. Quantum encryption provides an additional level of safety, but against unknown and unexpected attacks. · Practical quantum computers are very speculative, much more so than nuclear fusion or AI. They might not be built in the next million years.
- amirhirsch 8y ago
  seems like you’re getting downvoted for expressing quantum computing skepticism on Hacker News. I bet $150,000 that by January 1, 2040, a quantum computer will not exist that is able to factor a 2048-bit product of two primes. Anyone want to take me up?
  - charleslmunger 8y ago
    NIST thinks that 2048 bit RSA will be secure until 2030. Presumably their analysis does not include a quantum computer, because if it did they wouldn't recommend 3072 bit RSA for security beyond 2030. Their analysis is indexed against DES (so cracking 2048 bit RSA using the best known methods would be equivalent to cracking a hypothetical 112-bit DES). It's possible that you're right that a quantum computer won't exist in 2040 that will break 2048 bit RSA, but that doesn't mean it won't be broken anyway by then.
    - amirhirsch 8y ago
      Of course, for all we know factorization is in P or even NC (as the GP notes, we don’t really have proofs). I’m more hopeful we will find a proof of P!=NC or P!=NP than there being a quantum computer that beats RSA2048 in 21 years. It aught to be lower-hanging-fruit to prove that factorization is not in NC (polylog depth, polynomial component circuit) and therefore NC!=NP => (P!=NP or NC!=P) so at least one of the two probably true statements is true...
nyolfen 8y ago
this is like saying the same about computers in the 60s. there are many applications besides cryptography, and there is already fairly robust research into post-quantum crypto.
- ineedasername 8y ago
  does post quantum crypto require a quantum computer to implement?
  - krastanov 8y ago
    No, that is the main point. Quantum computers break some forms of asymmetric encryption, but there are "post quantum" protocol that you run on classical computer and neither a quantum nor a classical computer can break them (a conjecture, as usual with complexity theory).
    - ineedasername 8y ago
      thanks!

dlubarov 8y ago

It sounds like the money is going through the NIST and NSF, so presumably any resulting research will become public. If the government wanted to keep the research secret, I would expect the money to go to the CIA or somewhere else.

whatshisface 8y ago
Typically it would be the NSA that worked on secret cryptographic technology, although this might distract them from their charter of bugging civilians... (Having a quantum computer may not help with that because they would probably want to keep it secret and not build enough to decrypt everybody's SSL)

imhoguy 8y ago

Still this works the best: https://www.xkcd.com/538/ https://www.xkcd.com/538/

adrianN 8y ago
First you need to find out on who to apply the $5 wrench. That's a lot easier if you can monitor all communication.

akvadrako 8y ago

There are two major points to clarify this characterisation: · Existing algorithms are not proven to be secure, even classically. Quantum encryption provides an additional level of safety, but against unknown and unexpected attacks. · Practical quantum computers are very speculative, much more so than nuclear fusion or AI. They might not be built in the next million years.

amirhirsch 8y ago
seems like you’re getting downvoted for expressing quantum computing skepticism on Hacker News. I bet $150,000 that by January 1, 2040, a quantum computer will not exist that is able to factor a 2048-bit product of two primes. Anyone want to take me up?
- charleslmunger 8y ago
  NIST thinks that 2048 bit RSA will be secure until 2030. Presumably their analysis does not include a quantum computer, because if it did they wouldn't recommend 3072 bit RSA for security beyond 2030. Their analysis is indexed against DES (so cracking 2048 bit RSA using the best known methods would be equivalent to cracking a hypothetical 112-bit DES). It's possible that you're right that a quantum computer won't exist in 2040 that will break 2048 bit RSA, but that doesn't mean it won't be broken anyway by then.
  - amirhirsch 8y ago
    Of course, for all we know factorization is in P or even NC (as the GP notes, we don’t really have proofs). I’m more hopeful we will find a proof of P!=NC or P!=NP than there being a quantum computer that beats RSA2048 in 21 years. It aught to be lower-hanging-fruit to prove that factorization is not in NC (polylog depth, polynomial component circuit) and therefore NC!=NP => (P!=NP or NC!=P) so at least one of the two probably true statements is true...

nyolfen 8y ago

this is like saying the same about computers in the 60s. there are many applications besides cryptography, and there is already fairly robust research into post-quantum crypto.

ineedasername 8y ago
does post quantum crypto require a quantum computer to implement?
- krastanov 8y ago
  No, that is the main point. Quantum computers break some forms of asymmetric encryption, but there are "post quantum" protocol that you run on classical computer and neither a quantum nor a classical computer can break them (a conjecture, as usual with complexity theory).
  - ineedasername 8y ago
    thanks!