0
$\begingroup$

I noticed some new quantum cryptography algorithms are being developed.

I know very little about quantum computing but my understanding is that it will just be a much more powerful computer and therefore all the current key sizes that we use for cryptography will be rendered vulnerable to brute force attacks. Maybe these algorithms just find a practical ways of increasing the key size?

From a quick read of the abstract of one of the papers, it looks like they use different underlying maths than AES for example, but why? Why not just use AES but with bigger key sizes?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ One of the researchers (DJB) proposed (as a joke?) a version of RSA with terabyte-sized keys as a post-quantum cryptographic algorithm. That is not feasible to implement on current hardware, so alternatives that don't have such huge key sizes are being researched. $\endgroup$
    – user
    Commented Jul 6, 2022 at 16:48
  • 3
    $\begingroup$ "my understanding is that it will just be a much more powerful computer" - This is incorrect. Quantum computers are much much faster than classical computers at solving specific classes of problems, and have the same (or, practically, probably worse) performance as classical computers for other problems. There are quantum algorithms that can do factorization quickly, which causes problems for encryption schemes that rely on factorization of large primes being hard. There's a decent overview here: levelup.gitconnected.com/… $\endgroup$
    – Josh Eller
    Commented Jul 6, 2022 at 17:14

1 Answer 1

Reset to default
8
$\begingroup$

I know very little about quantum computing but my understanding is that it will just be a much more powerful computer and therefore all the current key sizes that we use for cryptography will be rendered vulnerable to brute force attacks.

No; Quantum Computing is a different computing model; some problems which appear to be difficult for standard computers are known to be quite easy for a Quantum Computer; for other problems, they don't appear to become all that much easier for a Quantum Computer.

It turns out that the public key algorithms that we currently use in practice (RSA, DH, ECC) are the former - they are much easier to break on a Quantum Computer than they are known to be on a conventional one.

These "postquantum algorithms" are algorithms based on these latter problems; that is, ones where we don't know how a Quantum Computer has much advantage in solving; that is, breaking them is infeasible on both a conventional and a quantum computer.

Why not just use AES but with bigger key sizes?

Actually, AES-256 (that is, AES with 256 bit keys) are believed to be perfectly quantum safe; in fact, I would argue that AES-128 is also practically-speaking quantum safe (because the best known quantum algorithm against it, Grover's, takes too long to be practical).

However, that doesn't answer your question "why don't we use AES for everything?" Well, one thing that AES doesn't do is public key operations; for example, we don't know how to use AES in such a way that someone with the public key can encrypt, but only someone with the private key can decrypt. We are used to these public key operations, which makes things convenient, and just AES doesn't give us that.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ "we don't know how to use AES [as public key encryption]" we know that it's impossible to build strong asymmetric encryption from standard symmetrical crypto. $\endgroup$
    – CodesInChaos
    Commented Jul 6, 2022 at 21:21
  • 1
    $\begingroup$ @CodesInChaos technically that result only applies to relativizing constructions. So there's a theoretical chance that a non-relativizing construction exists. (Though I'd say most people would consider that unlikely.) $\endgroup$
    – Maeher
    Commented Jul 7, 2022 at 9:04
  • $\begingroup$ Can you elaborate why quantum computers are better at solving prime factorization, RSA & co vs AES? $\endgroup$
    – david_adler
    Commented Jul 7, 2022 at 10:09
  • 1
    $\begingroup$ @david_adler: to solve factorization and discrete log, there's a known quantum algorithm (Shor's) that quickly solves those problems (and it's a low degree polynomial; increasing the size of the problem doesn't make it that much harder). In contrast, against AES, the best known algorithm (Grover's) takes square root time, in theory, it can find a 128 bit key with circa $2^{64}$ entangled AES evaluations; however to achieve that, those are sequential operations, and performing $2^{64}$ AES computations in a row would take too long. Adding parallelism dilutes this 'square-root' advantage $\endgroup$
    – poncho
    Commented Jul 7, 2022 at 12:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.