Low-Communication Parallel Quantum Multi-Target Preimage Search

This paper proposes a new quantum algorithm for multi-target preimage search that achieves asymptotic improvements in parallel quantum settings.

Key points:

• Improves upon the van Oorschot–Wiener rho method in the quantum regime
• Exploits the presence of multiple targets for better resource tradeoffs
• Challenges NIST’s assumptions on AES-128, AES-192, and AES-256 quantum resistance
• Suggests that multi-key Grover search may be more efficient than sequential search

This work motivates a re-evaluation of symmetric key security claims in the NIST post-quantum guidelines.