In cryptography, it is widely assumed that quantum computers running Grover's search algorithm halve the effective security of a cryptographic key. A cryptographic algorithm with λ-bits key (e.g AES) provides only λ/2 bits security level against a quantum key search adversary: Instead of using AES with 128-bit keys it is thus recommended to use AES with 256-bit keys to protect against quantum attacks This rule of thumb, however, assumes that keys are perfectly uniformly distributed. In practice, that is not always guaranteed: random number generators in embedded devices or quantum key distribution systems can deviate from the ideal. How much security remains in such cases? The traditional measure for how close a key distribution is to the ideal is the statistical distance, which sums all deviations across every possible key value. Prior results at SAC 2025 (PDF-Datei) (wird in neuem Tab geöffnet) showed that when this distance is large, little can be said formally about the actual security level, which is an unsatisfying gap, particularly for security-critical systems.

A different measure, a sharper picture

In their paper “Tighter Bit-Security Bounds in Quantum Key Search via the Chebyshev Distance”, Professor Marc Fischlin, Evangelos Gkoumas, and Gonne Kretschmer show that the so-called Chebyshev distance offers a way forward. Rather than summing all deviations, it measures only the largest deviation of the most probable key.

The central result of the paper is that a small Chebyshev distance may compensate for larger statistical distance, potentially ensuring that the expected bit security of λ/2 is maintained. The standard security assumption thus rests on a formally more solid foundation than previously proven. This result is not a free pass for arbitrary implementations. It formally describes the conditions under which the security assumption holds, and in doing so provides a basis for analyzing concrete systems.