Gustavo Banegas

Gustavo Banegas

Cryptography Researcher

Low-Communication Parallel Quantum Multi-Target Preimage Search

Published in In *Selected Areas in Cryptography* (SAC), 2017

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.

Recommended citation: Gustavo Banegas, Daniel J. Bernstein. (2017). "Low-Communication Parallel Quantum Multi-Target Preimage Search." In Selected Areas in Cryptography (SAC).
Download Paper | Download Slides | Download Bibtex