3 ms·

As I understand it that the picture for symmetric encryption in a quantum computer world is still relatively rosy. The key strength of something like AES is hal

As I understand it that the picture for symmetric encryption in a quantum computer world is still relatively rosy. The key strength of something like AES is halved, but with the important caveat that the difficulty is with respect to quantum operations rather than classical operations and there's no guarantee quantum computers will be able to scale as well over time as silicon has. The situation for asymmetric encryption is where the real potential trouble lies. Please correct me if I misunderstand the situation.

aparent 10y ago
You are mostly correct. In fact the key strength of something like AES is realistically not even going to be reduced by half. In terms of the query complexity (the number of calls to AES that are needed) using Grover's algorithm the key strength is half what it would be with classical brute force. In practice though these queries must be implemented as quantum circuits and run a on quantum computer which adds a pretty large overhead. This article is about the implementation of an asymmetric protocol based on the RLWE (https://en.wikipedia.org/wiki/Ring_Learning_with_Errors https://en.wikipedia.org/wiki/Ring_Learning_with_Errors) problem.
aruss 10y ago
That's right, symmetric encryption is fine. You're also right that protocols that rely on factoring or discrete log (more generally, any hidden subgroup problem) will be broken by quantum computers. However, this still means symmetric encryption is in trouble; namely in that we still need a post-quantum method for exchanging keys, otherwise symmetric ciphers will be virtually useless.
- e12e 10y ago
  How about hashing - in particular wrt key derivation? Does anyone have some insight there? Is it likely passphrase+salt+stretching might be in danger from quantum attacks? (I also wonder if DNA/RNA based biologic computing (or computing inspired by biology) might somehow change things around in terms of guessing passwords or look for hash collision...)
  - indolering 10y ago
    Hashing is in a similar position in that we just need to increase the size. Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics.
    - e12e 10y ago
      > Hashing is in a similar position in that we just need to increase the size. Size of hash, or number of iterations? Or either? And will it still be "convenient security" available for those that "only" have classical computers? (ie: is will be get away with "small" increases in size, and get to keep (some of) our current speed)? > Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics. I didn't think otherwise. But they might be relevant to combinatorial problems, and so relevant to security?
- naibafo 10y ago
  There are some quantum key distribution protocols[1], though they still have their faults. [1](https://en.wikipedia.org/wiki/Quantum_key_distribution https://en.wikipedia.org/wiki/Quantum_key_distribution)
  - bradleyjg 10y ago
    Based on what I've read, QKD requires a out of band shared secret to authenticate and rule out an active man in the middle. Given that I don't see the point at all.

aparent 10y ago

You are mostly correct. In fact the key strength of something like AES is realistically not even going to be reduced by half. In terms of the query complexity (the number of calls to AES that are needed) using Grover's algorithm the key strength is half what it would be with classical brute force. In practice though these queries must be implemented as quantum circuits and run a on quantum computer which adds a pretty large overhead. This article is about the implementation of an asymmetric protocol based on the RLWE (https://en.wikipedia.org/wiki/Ring_Learning_with_Errors https://en.wikipedia.org/wiki/Ring_Learning_with_Errors) problem.

aruss 10y ago

That's right, symmetric encryption is fine. You're also right that protocols that rely on factoring or discrete log (more generally, any hidden subgroup problem) will be broken by quantum computers. However, this still means symmetric encryption is in trouble; namely in that we still need a post-quantum method for exchanging keys, otherwise symmetric ciphers will be virtually useless.

e12e 10y ago
How about hashing - in particular wrt key derivation? Does anyone have some insight there? Is it likely passphrase+salt+stretching might be in danger from quantum attacks? (I also wonder if DNA/RNA based biologic computing (or computing inspired by biology) might somehow change things around in terms of guessing passwords or look for hash collision...)
- indolering 10y ago
  Hashing is in a similar position in that we just need to increase the size. Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics.
  - e12e 10y ago
    > Hashing is in a similar position in that we just need to increase the size. Size of hash, or number of iterations? Or either? And will it still be "convenient security" available for those that "only" have classical computers? (ie: is will be get away with "small" increases in size, and get to keep (some of) our current speed)? > Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics. I didn't think otherwise. But they might be relevant to combinatorial problems, and so relevant to security?
naibafo 10y ago
There are some quantum key distribution protocols[1], though they still have their faults. [1](https://en.wikipedia.org/wiki/Quantum_key_distribution https://en.wikipedia.org/wiki/Quantum_key_distribution)
- bradleyjg 10y ago
  Based on what I've read, QKD requires a out of band shared secret to authenticate and rule out an active man in the middle. Given that I don't see the point at all.