• 0 Posts
  • 1 Comment
Joined 2 years ago
cake
Cake day: February 1st, 2023

help-circle
  • A quantum computer doesn’t just calculate every possibility simultaneously, it’s much more limited. It “calculates more things at once” in some cases.

    Generally speaking, some things that are hard for a regular computer are easy quantum computers. So if an encryption algorithm is based on the difficulty of those things (e.g. RSA is based on the difficulty of factoring a semiprime number), and the thing is easy for a quantum computer (e.g. factoring a semiprime), then you could defeat the algorithm with a quantum computer.

    How do you protect yourself? You base the algorithm on something that is difficult for both a regular and quantum computer, that’s what post-quantum algorithms do.

    But quantum computers have one last ace up their sleeve. There is a sure-fire algorithm (Grover’s algorithm) to speed up any situation where you need to find an unknown value of a known length (in this case the secret key). To keep it simple, if to find the key a traditional computer would need N steps (because there are N possible keys), a quantum computer would need just √N, which is much less. Now, this sounds massive, and it is, but if you consider that with M bits there are 2^M keys, then if you just need to check √(2^M) keys, it’s like using keys of M/2 bits, so to defend against this you just need to make the key twice as long.

    Lastly, as a footnote: quantum computers can be faster than regular computers, but strictly speaking, regular computers are more powerful, that is to say they can do more things. We say that traditional computers are turing-complete, which means that they can compute anything that is computable, that is not the case for quantum computers, which means that some things (even easy things) that a computer can do, cannot be done on a quantum computer. For example, there is no way to implement regular expressions in quantum computers, it’s impossible. I know regex look difficult, but in computation theory they are among the easiest things a computer can do.

    Edit: one quick addition to the paragraph about Grover’s algorithm. If a quantum computer really just tried all the solutions at once it would be much faster than that. It would be (may my professor forgive me for saying this) “like if it guessed the bits of the key one at a time and were right on the first try”, so if you had your M bits key, you would need just M steps instead of the 2^(M/2) steps of Grover’s algorithm (this is like the difference speed difference between “checking if a word is palindrome” and “calculating who will win a game of chess when using a perfect strategy”). A computer that works like that… doesn’t (and probably will never) exist. But in literature they are called non-deterministic Turing machines. They would be powerful like a regular computer (not more) but unreasonably faster.