The Truth About Quantum Computers and Symmetric Key Security
On Monday, Valsorda finally channeled years’ worth of frustration, fueled by the widely held misunderstanding, into a blog post titled “Quantum Computers Are Not a Threat to 128-bit Symmetric Keys.” In a digital landscape teeming with misconceptions, Valsorda aimed to clarify an important point regarding the security of encryption.
Misconceptions Around Symmetric Key Security
“There’s a common misconception that quantum computers will ‘halve’ the security of symmetric keys, requiring 256-bit keys for 128 bits of security,” he wrote. “That is not an accurate interpretation of the speedup offered by quantum algorithms, it’s not reflected in any compliance mandate, and risks diverting energy and attention from actually necessary post-quantum transition work.” This highlights a crucial need for clear communication about the implications of quantum computing on cybersecurity.
The Math Behind the Misunderstanding
The explanation for this misconception lies in the differing methods of brute-force searches on classical computers versus those utilizing Grover’s algorithm. Classical computers can perform multiple searches simultaneously. This capability allows them to break large tasks into smaller ones, completing the overall job faster. In contrast, Grover’s algorithm requires a long-running serial computation, where each search is executed one at a time.
“What makes Grover special is that as you parallelize it, its advantage over non-quantum algorithms gets smaller,” Valsorda explained in an interview. To illustrate this concept, he presented a simplified example:
Imagine it with small numbers, let’s say there are 256 possible combinations to a lock. A normal attack would take 256 tries. You decide it’s too long, so you get three friends, and each of you does 64 tries. This is classical parallelization. With Grover, you could theoretically do √256 = 16 tries in a row. However, if you again sought help from your three friends, each would then need to do √256/4 = 8 tries.
So in total, you would perform 8 * 4 = 32 tries, far exceeding the 16 tries you would have done alone. Therefore, when seeking to parallelize the attack, the process becomes slower overall, a phenomenon not witnessed in classical attacks.
Understanding the Real Security Levels
Of course, the actual numbers are significantly larger. Still, if we impose reasonable constraints on an attacker, such as having to complete a run in 10 years, the total work required exceeds the conventional 2^64. Furthermore, positing 2^64 as a baseline is misleading since it assumes AES can be performed as a single operation on a single qubit, which isn’t the case.
The combination of these observations transforms the actual cost of attacking AES-128 into around 2^104, a number far beyond acceptable security thresholds.
Expert Insights for Clarity
In further clarification, Sophie Schmieg, a senior cryptography engineer at Google, encapsulates this notion succinctly: it is essential to address these misconceptions to maintain trust in cryptographic systems.
For an in-depth read on the topic, check out Valsorda’s blog post and the discussion surrounding it here.
Image Credit: arstechnica.com
