Quantum-Aware Key Rank for Side-Channel Attacks evaluation

In the world of digital security, the strength of a secret code is often tested by trying to steal the key not by breaking the math, but by listening to the machine. When a computer encrypts data, it leaks tiny amounts of information through its power consumption or electromagnetic signals. Security experts capture these leaks, known as traces, and use them to narrow down the list of possible keys. Instead of finding the correct key immediately, these attacks usually leave a long, ordered list of candidates, with the true key hidden somewhere in the middle. The position of the true key on this list is called its rank. If the rank is low, the key is easy to find; if it is high, the key is effectively safe. For decades, security laboratories have measured this rank to decide if a device is secure, assuming that an attacker would use a standard computer to search through the remaining possibilities.

However, the rules of the game are changing with the arrival of quantum computers. These machines operate on different physical principles and can, in theory, search through lists of possibilities much faster than any classical computer. A new study by Yevgen Kotukh addresses a critical gap in our understanding: what happens when an attacker uses a classical computer to gather the initial clues, but then switches to a quantum computer to finish the job? The research reveals that the speed-up provided by quantum computers is not as dramatic or universal as some previous theories suggested. It turns out that the advantage depends entirely on how many candidates are left to search and how much time the quantum computer is allowed to run.

The researchers built a detailed model to simulate this specific type of hybrid attacker. They imagined a scenario where a hacker first collects power traces from a device and uses standard software to create a ranked list of potential keys. This list might contain billions of candidates. The hacker then takes this list and runs a quantum algorithm to find the correct key. The study proves that for any single device with a specific number of remaining candidates, the quantum computer offers a speed-up that is exactly proportional to the square root of that number. This means if a classical computer needs to check a million keys, a quantum computer might only need to check a thousand. This is a significant improvement, but it is not the magical, exponential explosion of speed that some earlier, more abstract theories predicted. Those earlier theories suggested that quantum computers could be even faster, but the new research shows that those predictions were based on averaging results over many different devices, rather than looking at the specific reality of a single attack.

A crucial part of the study involves the physical limits of quantum computers. These machines are not yet perfect; they can only perform a certain number of operations before their delicate quantum states collapse. The researchers applied a strict limit on the depth of the quantum circuit, representing the maximum number of steps a future quantum computer could take in a year or a decade. They found that the quadratic speed-up only works when the number of remaining keys is below a certain threshold. If the list of candidates is too long, the quantum computer is forced to run many copies of itself in parallel to stay within its time limit. This parallelization eats away the speed advantage, reducing the benefit to a simple, constant factor. For modern encryption standards like AES-128, this "window" of advantage closes when the rank of the key reaches a specific point, roughly corresponding to a rank of 2 to the power of 59. Beyond this point, the quantum computer is no longer exponentially faster; it is only a fixed number of times faster, and in some cases, the advantage is so small it barely matters.

To help security laboratories adapt to this new reality, the author introduced a new metric called the "quantum-aware key rank." This tool allows evaluators to take the standard rank they already calculate and convert it into a value that reflects the security level against a quantum attacker with a specific time limit. For example, if a device has a classical rank that suggests it is safe, the quantum-aware rank might show that it is actually vulnerable because the quantum computer can find the key within the allowed time. The study provides clear formulas for this conversion, showing that to maintain the same level of security against a quantum adversary, a device needs a much higher classical rank than previously thought. Specifically, for a quantum computer limited to a depth of 2 to the power of 40, a device needs to retain a classical rank of about 2 to the power of 74 to be as secure as a device with a classical rank of 2 to the power of 48.

The research also compared two different ways a quantum computer could use the leaked information to find the key. One method involves preparing a special quantum state that reflects the likelihood of each key, while the other involves searching through blocks of keys in a structured way. The study found that on the types of data leaks typically seen in real-world attacks, these two methods are very close in performance. The deciding factor is not which method is theoretically faster, but the cost of the hardware required to implement the more complex method. The researchers simulated these attacks on a small, toy cipher and on realistic models of AES encryption to confirm their theories. They discovered that for a typical attack with a low signal-to-noise ratio, a quantum attacker with a large gate budget is worth about 22 extra power traces to a classical attacker. In other words, the quantum advantage is real, but it is bounded and predictable.

This work resolves a tension in the security community between two conflicting views: one that claimed quantum computers would offer a super-fast, exponential advantage, and another that suggested they might offer no advantage at all due to hardware limits. The study shows that both views are correct, but they apply to different situations. The super-fast advantage is an average over many possible scenarios, while the bounded, quadratic advantage is what happens in any single, real-world attack. By providing a concrete metric and a clear understanding of the limits, this research gives security evaluators the tools they need to accurately assess the risk of quantum attacks. It moves the conversation from speculation to calculation, ensuring that as quantum technology matures, our defenses can be adjusted with precision rather than guesswork.