Paper 2026/863 Original: eprint.iacr.org/2026/863 ↗

Conquering Bad Norms in RstOE: Pure-Database Substitution and Early-Defense

Abstract

The Recording Standard Oracle with Errors (RstOE) technique is a quantum-security proof technique that provides a structured framework for analyzing adversarial capabilities in quantum settings. For example, it can be applied to prove the quantum security of compressing pseudorandom functions. However, against adaptive quantum chosen-plaintext adversaries, traditional RstOE-based proofs may suffer from the ''trivialization of norm'' problem. In the RstOE analyses considered in this paper, this issue can be traced to three recurring causes: delayed evaluation of bad events, the presence of unrecorded external variables, and unconstrained independence among intermediate variables. To address this obstacle, we propose two refinements of the RstOE methodology, namely Pure-Database Substitution and Early-Defense. Pure-Database Substitution algebraically eliminates unrecorded external variables and reformulates collision constraints in terms of internal database records. Building on this substitution, Early-Defense moves the collision check to the point at which a new internal variable is sampled. Because the bad event then depends on this freshly generated quantum randomness, only a negligible fraction of the $2^n$ superposition branches satisfy the collision constraint. This reduces the amplitude of transitions into the bad subspace and avoids the $O(1)$ norm collapse. We demonstrate the method on TNT as a case study and outline extensions to EDMQ, EDMDQ, LRWQ, and QPMAC.