Titre: Compromis temps-mémoire quantiques et application à la recherche de
collisions
Résumé:
Deux méthodes prédominent pour démontrer des bornes inférieures temporelles
dans le modèle de requêtes quantiques : la méthode polynomiale et la
méthode par adversaire. Bien que très puissantes, ces techniques sont
souvent difficiles et peu intuitives à appliquer. Dans cet exposé, je
présenterai une version simplifiée et généralisée d'une nouvelle méthode
"d'enregistrement de requêtes quantiques" introduite par Mark Zhandry en
2019. Cette approche permet de reprouver de façon intuitive plusieurs
bornes existantes, mais également d'obtenir de nouveaux résultats
concernant la complexité en mémoire. Je détaillerai notamment une
application aux attaques de collisions avec faible mémoire quantique,
montrant que toute attaque quantique optimale en temps nécessite un espace
de calcul important.