Statistical-Plausibility Oracles for Quantum Key-Recovery: A Corpus-Driven Complexity Analysis

Abstract The efficiency of a Grover-based quantum key-recovery attack is governed not only by the size of the key space, but by the fraction of keys the oracle accepts as plausible. For ciphers whose keys are judged by statistical plausibility, that fraction reflects how strongly the language constrains admissible character sequences and, as we show empirically, how long the intercepted ciphertext is. We study this through a corpus-driven experiment on the monoalphabetic substitution cipher, using character trigram language models trained on four Renaissance Italian texts. The oracle threshold is defined as a scalar fraction of the best observed decryption score ( $$S_{\max }/\tau$$ ), producing a threshold that scales naturally with cipher length. Over a 21-letter alphabet we estimate the plausible key fraction across combinations of cipher length and stringency parameter, and derive Grover oracle costs analytically. Full Grover statevector simulation over completely enumerated key spaces at two reduced alphabet sizes confirms that the oracle’s acceptance density varies with cipher length, driven by the interplay between score-distribution concentration and the best-observed-score anchor $$S_{\max }$$ , and that the Boyer iteration formula provides a reliable near-optimal stopping criterion throughout. Parallel QUBO annealing experiments under the same scoring function exhibit a contrasting failure pattern under alphabet compression, establishing the two attack paradigms as probes of complementary landscape properties. An analytical projection across alphabet sizes shows that Grover oracle call counts grow far more slowly than the key space, roughly three orders of magnitude against the sixteen-order growth in the key space cardinality, so that the quantum speedup over classical random search increases with alphabet size, reaching thousands times at the full 21-letter scale.