4 ms·

> in particular, they can't run Shor's algorithm to factorize numbers and break a big part of encryption methods Given a sufficient time horizon, large swathes

> in particular, they can't run Shor's algorithm to factorize numbers and break a big part of encryption methods Given a sufficient time horizon, large swathes of crypto will be broken by such a computer and has many people worried. NIST is working on algorithms resistant to quantum attacks, but we're still far off.

Yajirobe 7y ago
> NIST is working on algorithms resistant to quantum attacks, but we're still far off. These have existed for years already
- octosphere 7y ago
  Yes but isn't there a competition to find an algo that can be widely deployed and not subject to weird requirements? A sort of 'goldilocks' algo. For example, I can't recall the name of the algo, but one such candidate for a post-quantum algo required keysizes to be 1TB in size. Another had large computation requirements and so thus couldn't do on-the-fly crypto (which is needed to do LUKS style encryption of disks for example). (Sorry for my lack of sources but it was a Youtube video of some talk about post-quantum crypto algos I randomly stumbled upon and forgot to bookmark)
  - EGreg 7y ago
    Excuse me if I’m being ignorant but isn’t a quantum computer unable to reverse hashes? Are they going to make a preimage attack or a collision attack on SHA512 for example, by trying all combinations at once? If hashes are safe, then why not simply base our signatures and other stuff on them? The only thing that may be missing is actual encryption / decryption, but that can be done by XORing with “one-time” pads built from peeling onion layers from hashes.
    - speakeron 7y ago
      A quantum computer can find hash collisions in the square root of the time a classical computer can using Grover's algorithm. (So a 256-bit hash becomes as difficult as a 128-bit hash to reverse). Symmetric encryption (e.g. AES) is the same, so encryption itself doesn't have any problems with quantum computing (if you consider 128-bit AES to be safe in general). Quantum computing affects the distribution of symmetric keys using public key encryption (and so affects a large amount of encryption as used in people's daily lives) which is vulnerable to quantum computers with sufficient bits.
      - EGreg 7y ago
        In that case we are perfectly fine. We can distribute symmetric keys in a different way. Just run a hash 10,000,000 times and your public key will be the last result, while the private key will be the first input. Only you can reconstruct the other layers going backwards, as you “peel the onion” and you can use those numbers any way you want. My favorite application is to generate random numbers among untrusting participants by everyone revealing the next number and then using functions of that as seeds to an RNG. It can be used for tons of byzantine fault tolerant applications. The only problem is that it seems to also have forward secrecy built in because once you’ve revealed the next onion layer, anyone could have constructed the transcript up to that point. So you can only be sure that the author signed something if you are sure they didn’t reveal the next private key to anyone else (to verify it).
        atq2119 7y ago
        This doesn't work for encryption, though. You'd need a cryptosystem where it's possible to encrypt a message with H(x) such that it can only (efficiently) be decrypted given x, for a hash function H. To the best of my knowledge, no such hash function is known.
        EGreg 7y ago
        It’s an open question whether hash functions can be used for encryption using XOR: https://crypto.stackexchange.com/questions/35809/whats-wrong-with-xor-encryption-with-hash-and-an-iterated-salt https://crypto.stackexchange.com/questions/35809/whats-wrong... Here is a basic explanation: https://cryptography.fandom.com/wiki/Snuffle https://cryptography.fandom.com/wiki/Snuffle Note however that you would need a nonce / salt transmitted with each message because otherwise decrypting messages encrypted with the same key would just be as easy as XORing them!
  - hyper_reality 7y ago
    Yes, NIST has an ongoing standardisation process for Post-Quantum cryptography: https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization https://csrc.nist.gov/Projects/post-quantum-cryptography/Pos... With the 1TB keysizes, what you are thinking of is Berstein et al.'s tongue in cheek paper "Post-quantum RSA": https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf
lonelappde 7y ago
That's not an interesting statement. It's already possible to crack encryption given sufficient time. The amount of time matters.
- octosphere 7y ago
  I meant having a sufficient amount of time before certain crypto schemes are broken. Maybe I really meant reasonable. In a reasonable amount of time we can expect quantum computers to attack crypto schemes. If you mean brute forcing an encrypted message, then yeah: that could take until the heat death of the universe for complex passphrases. Infact you might even need several universes of time to crack some passphrases.

Yajirobe 7y ago

> NIST is working on algorithms resistant to quantum attacks, but we're still far off. These have existed for years already

octosphere 7y ago
Yes but isn't there a competition to find an algo that can be widely deployed and not subject to weird requirements? A sort of 'goldilocks' algo. For example, I can't recall the name of the algo, but one such candidate for a post-quantum algo required keysizes to be 1TB in size. Another had large computation requirements and so thus couldn't do on-the-fly crypto (which is needed to do LUKS style encryption of disks for example). (Sorry for my lack of sources but it was a Youtube video of some talk about post-quantum crypto algos I randomly stumbled upon and forgot to bookmark)
- EGreg 7y ago
  Excuse me if I’m being ignorant but isn’t a quantum computer unable to reverse hashes? Are they going to make a preimage attack or a collision attack on SHA512 for example, by trying all combinations at once? If hashes are safe, then why not simply base our signatures and other stuff on them? The only thing that may be missing is actual encryption / decryption, but that can be done by XORing with “one-time” pads built from peeling onion layers from hashes.
  - speakeron 7y ago
    A quantum computer can find hash collisions in the square root of the time a classical computer can using Grover's algorithm. (So a 256-bit hash becomes as difficult as a 128-bit hash to reverse). Symmetric encryption (e.g. AES) is the same, so encryption itself doesn't have any problems with quantum computing (if you consider 128-bit AES to be safe in general). Quantum computing affects the distribution of symmetric keys using public key encryption (and so affects a large amount of encryption as used in people's daily lives) which is vulnerable to quantum computers with sufficient bits.
    - EGreg 7y ago
      In that case we are perfectly fine. We can distribute symmetric keys in a different way. Just run a hash 10,000,000 times and your public key will be the last result, while the private key will be the first input. Only you can reconstruct the other layers going backwards, as you “peel the onion” and you can use those numbers any way you want. My favorite application is to generate random numbers among untrusting participants by everyone revealing the next number and then using functions of that as seeds to an RNG. It can be used for tons of byzantine fault tolerant applications. The only problem is that it seems to also have forward secrecy built in because once you’ve revealed the next onion layer, anyone could have constructed the transcript up to that point. So you can only be sure that the author signed something if you are sure they didn’t reveal the next private key to anyone else (to verify it).
      - atq2119 7y ago
        This doesn't work for encryption, though. You'd need a cryptosystem where it's possible to encrypt a message with H(x) such that it can only (efficiently) be decrypted given x, for a hash function H. To the best of my knowledge, no such hash function is known.
        EGreg 7y ago
        It’s an open question whether hash functions can be used for encryption using XOR: https://crypto.stackexchange.com/questions/35809/whats-wrong-with-xor-encryption-with-hash-and-an-iterated-salt https://crypto.stackexchange.com/questions/35809/whats-wrong... Here is a basic explanation: https://cryptography.fandom.com/wiki/Snuffle https://cryptography.fandom.com/wiki/Snuffle Note however that you would need a nonce / salt transmitted with each message because otherwise decrypting messages encrypted with the same key would just be as easy as XORing them!
- hyper_reality 7y ago
  Yes, NIST has an ongoing standardisation process for Post-Quantum cryptography: https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization https://csrc.nist.gov/Projects/post-quantum-cryptography/Pos... With the 1TB keysizes, what you are thinking of is Berstein et al.'s tongue in cheek paper "Post-quantum RSA": https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf

lonelappde 7y ago

That's not an interesting statement. It's already possible to crack encryption given sufficient time. The amount of time matters.

octosphere 7y ago
I meant having a sufficient amount of time before certain crypto schemes are broken. Maybe I really meant reasonable. In a reasonable amount of time we can expect quantum computers to attack crypto schemes. If you mean brute forcing an encrypted message, then yeah: that could take until the heat death of the universe for complex passphrases. Infact you might even need several universes of time to crack some passphrases.