Quantum-Assisted Seed Recovery Under Probabilistic Leakage in Post-Quantum Cryptography

Abstract

Seed-based key generation is widely used in post-quantum cryptography because it provides compact secret-key representations and deterministic regeneration of cryptographic material. The same design, however, concentrates security on a short secret state: partial or noisy leakage about the seed may sharply reduce the space of plausible secrets. Existing posterior-guided recovery methods exploit such leakage by ranking candidate seeds according to posterior scores and then validating them against the target public key. This work studies how posterior-guided seed recovery changes in the presence of a quantum adversary. Building on the recently introduced Bitwise Bayesian Leakage Model (BBLM) and Seed Recovery Framework (SRF), we keep the leakage-processing stages classical, including posterior inference, candidate generation, ranking, score-band construction, and success-probability estimation. The quantum component is introduced only at the validation stage, where sequential public-key checks over an SRF-selected candidate set are replaced by Grover-assisted search. Instead of applying Grover search to the full seed space $\{0,1\}^{\lambda }$ , we apply it to the index set of the candidate band selected by SRF. For each index $\iota $ , the oracle coherently reconstructs the associated seed candidate $\textsf {seed}_{\iota } $ from the SRF preprocessing structures and evaluates a reversible public-key validation predicate on $\textsf {seed}_{\iota } $ . This yields a band-index oracle whose cost accounts for reversible index-to-seed reconstruction, read-only coherent access to the SRF data structures, seed expansion, scheme-specific public-key validation, comparison with the target public key, conditional phase marking, and uncomputation of all auxiliary workspace. As a concrete case study, we instantiate the seed-level validation component for the RYDE post-quantum signature scheme and develop a logical-oracle-level cost model that separates generic band-index and Grover costs from RYDE-specific validation costs. The analysis includes an explicit access model for the SRF data structures, a full logical-oracle-level cost decomposition, and leakage-driven experiments reporting a representative selected score band, candidate-set size, empirical inclusion probability, oracle cost, Grover iterations, final-check cost, expected validation-stage cost, the corresponding full recovery-cost expression, and calibration trends across leakage parameters. We also compare classical SRF validation, restricted Grover-assisted SRF, and full-space Grover search. The results characterize how posterior-guided candidate restriction and Grover-assisted validation interact under probabilistic leakage at the logical-oracle level, rather than claiming a hardware-level attack estimate.