3 ms·

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 diff

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!
    - atq2119 7y ago
      Snuffle is symmetric key encryption, and yes, it's a well-known construction. However, you previously suggested that an asymmetric encryption scheme (with public and private keys) could be constructed using a hash.
      - EGreg 7y ago
        oh, right. It’s only good for signing and random number generation, not encryption. Still that’s plenty useful! It can be used for blockchains and crypto currency.

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!
  - atq2119 7y ago
    Snuffle is symmetric key encryption, and yes, it's a well-known construction. However, you previously suggested that an asymmetric encryption scheme (with public and private keys) could be constructed using a hash.
    - EGreg 7y ago
      oh, right. It’s only good for signing and random number generation, not encryption. Still that’s plenty useful! It can be used for blockchains and crypto currency.