💻 computer science

Quantum Hash Function Based on Spectral Properties of Graphs and Discrete Walker Dynamics

Cet article introduit QGH-256, un nouvel algorithme de hachage quantique qui génère des empreintes de 256 bits en mappant des messages sur des graphes pondérés sur une grille toroïdale et en utilisant l'Estimation de Phase Quantique pour extraire des caractéristiques spectrales qui capturent à la fois les propriétés structurelles et dynamiques, démontrant une forte sensibilité cryptographique et une faisabilité via des simulations Qiskit.

Auteurs originaux : Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

Publié 2026-06-30

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La vue d'ensemble : Une nouvelle empreinte numérique

Imaginez que vous deviez transformer une longue histoire désordonnée (comme un roman) en une empreinte digitale unique. Dans le monde numérique, nous utilisons généralement des « fonctions de hachage » (comme SHA-256) pour cela. Mais les auteurs de ce papier craignent que les futurs ordinateurs quantiques ne puissent briser ces anciennes empreintes.

Ils ont donc créé un nouveau type d'empreinte appelé QGH-256. Au lieu de simplement faire des mathématiques sur des nombres, cette méthode transforme votre message en une carte, envoie un marcheur à travers cette carte, puis utilise la physique quantique pour mesurer les « vibrations » de la carte afin de créer l'empreinte finale.

Étape 1 : Transformer les mots en une carte (Le Marcheur)

L'analogie : Imaginez un petit robot marchant sur une grille carrée (comme un échiquier) qui s'enroule sur elle-même (si vous sortez par le bord droit, vous réapparaissez à gauche). C'est ce qu'on appelle une « grille toroïdale ».

Comment ça marche : Vous prenez votre message (par exemple, « Hello ») et vous le transformez en code binaire (0 et 1).
La marche : Le robot ne marche pas au hasard. Il lit votre message bit par bit.
- S'il voit 00, il marche vers le Nord.
- S'il voit 01, il marche vers le Sud.
- S'il voit 10, il marche vers l'Est.
- S'il voit 11, il marche vers l'Ouest.
La carte : Pendant que le robot marche, il laisse une trace. Chaque fois qu'il traverse une ligne (un arête) sur la grille, il ajoute un « poids » à cette ligne en fonction des nombres de votre message.
Le résultat : Vous obtenez une carte pondérée unique. Si vous changez ne serait-ce qu'une lettre dans votre message (comme passer de « Hello » à « Hella »), le robot prend un chemin totalement différent, créant une carte totalement différente.

Pourquoi c'est important : Le papier affirme que comme la carte est non orientée (le robot n'enregistre pas la direction dans laquelle il faisait face, seulement combien de fois il a traversé une ligne), il est incroyablement difficile d'observer la carte et de deviner le message d'origine. C'est comme essayer de deviner le chemin exact emprunté par un randonneur juste en regardant l'herbe piétinée, sans savoir d'où il est parti ni où il est arrivé.

Étape 2 : Écouter la « musique » de la carte (Empreinte spectrale)

Maintenant que nous avons cette carte unique, comment la transformer en empreinte ? Les auteurs utilisent un concept de la physique appelé Analyse Spectrale.

L'analogie : Imaginez que votre carte est un tambour géant. Si vous le frappez, il vibre. Chaque tambour possède un ensemble spécifique de « notes » (fréquences) qu'il peut jouer, déterminées par sa forme et la tension de sa peau.

En mathématiques, ces « notes » sont appelées valeurs propres (eigenvalues).
La « tension » et la « forme » de la carte sont déterminées par le Laplacien du graphe (une matrice mathématique sophistiquée qui décrit les connexions et les poids de la carte).

La touche quantique :
Habituellement, pour entendre ces notes, il faudrait résoudre des équations complexes. Mais ce papier utilise un algorithme d'Estimation de Phase Quantique (QPE).

Considérez la QPE comme un microphone ultra-sensible capable d'« écouter » instantanément le tambour et de vous dire exactement quelles notes il joue.
Détail crucial : Les auteurs n'écoutent pas seulement une note. Ils envoient une « superposition » (un état quantique qui est comme un mélange de tous les points de départ possibles) dans le système. Cela signifie que l'ordinateur quantique entend toute la chanson de la carte à la fois, y compris la façon dont les notes interagissent entre elles.

Pourquoi c'est spécial :
Deux cartes différentes pourraient accidentellement avoir le même ensemble de notes (c'est ce qu'on appelle être « cospétrales »). Cependant, parce que les auteurs écoutent comment les notes interagissent avec la structure spécifique de la carte (les vecteurs propres), ils peuvent faire la différence entre deux cartes qui sonnent pareil mais qui sont visuellement différentes. Cela empêche les « collisions » (où deux messages différents produisent la même empreinte).

Étape 3 : La trace de chaleur (L'empreinte finale)

Une fois que l'ordinateur quantique a identifié les « notes » (valeurs propres), les auteurs calculent ce qu'on appelle la Trace de Chaleur (Heat Trace).

L'analogie : Imaginez verser de l'eau chaude sur votre carte. La chaleur se propage (diffuse) à travers la grille.

La « Trace de Chaleur » mesure la vitesse à laquelle la chaleur se propage.
En mesurant cela à différents moments, on obtient une signature unique de la forme de la carte.
Cette signature est ensuite compressée en un code de 256 bits (une chaîne de 256 zéros et uns). C'est votre empreinte finale QGH-256.

Pourquoi est-ce sécurisé ? (L'effet d'avalanche)

Le papier teste cette nouvelle méthode contre les règles d'un bon verrou :

Déterminisme : Si vous tapez « Hello » deux fois, vous obtenez exactement la même empreinte les deux fois.
L'effet d'avalanche : Si vous changez une seule lettre (par exemple, de « Hello » à « Hella »), le robot suit un chemin totalement différent. Cela change la carte, ce qui change les « notes », ce qui change la « propagation de la chaleur », ce qui aboutit à un code de 256 bits totalement différent.
Résistance à la pré-image : Si quelqu'un vole l'empreinte, il ne peut pas revenir en arrière pour trouver le message d'origine. Les mathématiques sont trop complexes et la carte perd l'information sur la direction de la marche.

Le bémol : C'est une simulation

Le papier admet qu'actuellement, nous ne possédons pas d'ordinateurs quantiques assez grands ou assez calmes pour exécuter cela en conditions réelles.

Le problème : Les vrais ordinateurs quantiques sont « bruyants » (comme une radio avec de la friture). Si vous essayez d'écouter les « notes » de la carte sur une machine bruyante, le résultat pourrait être erroné et l'empreinte pourrait changer à chaque exécution.
La solution dans le papier : Les auteurs ont effectué leurs tests sur un simulateur (un programme informatique simulant un ordinateur quantique parfait). Cela a prouvé que les mathématiques fonctionnent parfaitement en théorie.
Futur : Ils pensent qu'à mesure que les ordinateurs quantiques deviendront meilleurs et moins bruyants, cette méthode constituera une défense solide contre les pirates, même ceux utilisant des ordinateurs quantiques.

Résumé

Les auteurs ont construit un nouveau verrou numérique.

Ils transforment votre message en un chemin de marche unique sur une grille.
Ils utilisent un ordinateur quantique pour écouter les vibrations de ce chemin.
Ils transforment ces vibrations en un code de 256 bits.

Ils affirment que cela est plus difficile à briser que les méthodes actuelles car cela repose sur la physique complexe de la façon dont un graphe vibre, ce qui rend extrêmement difficile pour même les futurs ordinateurs quantiques de deviner le message d'origine ou de trouver deux messages produisant le même code.

Résumé Technique : Fonction de Hachage Quantique Basée sur les Propriétés Spectrales des Graphes et la Dynamique des Marcheurs Discrets

Énoncé du Problème
Le document traite de la vulnérabilité croissante des fonctions de hachage cryptographiques classiques (par exemple, SHA-256, MD5) face aux menaces de l'informatique quantique. Plus précisément, des algorithmes comme ceux de Shor et de Grover posent des risques existentiels pour les standards actuels en factorisant efficacement les grands entiers et en accélérant les recherches non structurées, respectivement. Bien que le NIST (National Institute of Standards and Technology) normalise la cryptographie post-quantique (PQC), il existe un besoin de schémas de hachage natifs ou résilients au quantique capables de résister aux attaques classiques et quantiques. Les approches existantes reposent souvent sur des opérations binaires linéaires, qui peuvent ne pas offrir une résistance suffisante contre les accélérations quantiques ou peuvent échouer à distinguer des graphes structurellement différents partageant le même spectre de valeurs propres (graphes cospectraux).

Méthodologie
Les auteurs proposent QGH-256, un nouvel algorithme de hachage spectral qui intègre la dynamique classique des marcheurs discrets et l'analyse spectrale de graphes quantiques. Le flux de travail passe par les étapes suivantes :

Construction de Graphe Induite par le Message :
- Les messages d'entrée sont convertis en binaire UTF-8 et segmentés en blocs.
- Un marcheur discret classique opère sur une grille toroïdale fixe de $4 \times 4$ . Contrairement aux marches aléatoires, la direction du marcheur à chaque étape est dictée de manière déterministe par les bits du message (plus précisément, le premier et le dernier bit de chaque bloc déterminent la direction : Nord, Sud, Est ou Ouest).
- La valeur décimale de chaque bloc sert de poids pour l'arête traversée.
- Ce processus génère un graphe non orienté, pondéré et unique $G = (V, E, W)$ pour chaque message d'entrée. Les auteurs notent que la récupération du message d'origine à partir du graphe est informatiquement difficile en raison de la perte d'information directionnelle dans les poids des arêtes non orientées et de la complexité de la reconstruction de la séquence de traversée.
Empreinte Spectrale via l'Estimation de Phase Quantique (QPE) :
- La structure du graphe est encodée dans une matrice Laplacienne $L = D - A$ (matrice de degré moins la matrice d'adjacence).
- Pour utiliser les algorithmes quantiques, $L$ est transformée en un opérateur unitaire $U = e^{iLt}$ via l'exponentiation de matrice.
- L'Estimation de Phase Quantique (QPE) est appliquée à $U$ . Crucialement, l'entrée du circuit QPE n'est pas un vecteur propre unique mais un état de superposition défini dans la base des nœuds du graphe ( $|\psi\rangle = \sum \alpha_i |i\rangle$ ).
- Parce que l'état d'entrée est une superposition des vecteurs propres du Laplacien, le processus QPE agit comme un analyseur spectral, décomposant l'état en ses composantes de fréquence (phase). La probabilité de mesurer une phase spécifique est proportionnelle au carré du recouvrement entre l'état d'entrée et le vecteur propre correspondant.
Trace de Chaleur et Génération de Hachage :
- Les auteurs calculent une « empreinte spectrale » en évaluant la valeur de la trace de chaleur $h(t) = \sum |c_k|^2 e^{-t\tilde{\lambda}_k}$ à travers plusieurs échelles de temps. Cette métrique capture à la fois l'information sur les valeurs propres et la contribution des vecteurs propres (via les coefficients $c_k$ ).
- Ce vecteur de caractéristiques est post-traité et compressé en un hachage binaire de 256 bits fixe.

Contributions Clés

Résolution des Collisions Co-spectrales : Une contribution théorique primaire est la capacité de la méthode à distinguer les graphes co-spectraux (graphes ayant des spectres de valeurs propres identiques mais des structures différentes). En utilisant un état de superposition comme état d'entrée pour la QPE, l'empreinte spectrale résultante dépend des recouvrements de vecteurs propres ( $|c_k|^2$ ), et non seulement des valeurs propres. Cela garantit que des graphes non isomorphes produisent des empreintes distinctes même s'ils partagent le même spectre.
Efficacité à Étapes Fixes : Les auteurs ont amélioré les algorithmes basés sur les marcheurs en fixant le nombre d'étapes du marcheur (10 000) et en ajustant la taille des blocs en fonction de la longueur du message. Cela garantit que le coût computationnel de la phase de génération du graphe est indépendant de la taille du message d'entrée.
Conception Native Quantique : L'algorithme tire parti des propriétés intrinsèques de la mécanique quantique (superposition et estimation de phase) pour générer des empreintes à haute entropie, positionnant l'algorithme comme un candidat pour la sécurité post-quantique.

Résultats et Évaluation
Le papier évalue QGH-256 en utilisant un Simulateur d'État de Vecteur d'État Qiskit avec graine (Seeded Qiskit Statevector Simulator) pour garantir des résultats déterministes et sans bruit, reconnaissant que le matériel NISQ (Noisy Intermediate-Scale Quantum) actuel introduirait des fluctuations affectant le déterminisme.

Déterminisme : Des entrées identiques ont produit de manière cohérente des hachages de 256 bits identiques.
Effet d'Avalanche : Un changement d'un seul bit dans l'entrée (par exemple, "Hello" vs "Hella") a entraîné une distance de Hamming significativement élevée dans la sortie, confirmant la sensibilité aux perturbations d'entrée.
Résistance à la Pré-image : Les auteurs soutiennent que l'inversion du hachage est irréalisable en raison de la complexité du problème inverse des valeurs propres du graphe et de l'ambiguïté introduite par la nature non orientée du graphe.
Temps de Calcul : Le temps d'exécution est resté presque constant quelle que soit la longueur du message, grâce à la taille fixe de la grille et au nombre fixe d'étapes du marcheur.

Signification et Revendications
Le document affirme que QGH-256 offre une alternative robuste au hachage classique en intégrant les propriétés topologiques et dynamiques des graphes.

Résilience Quantique : Les auteurs affirment que le recours à des calculs spectraux complexes et non linéaires (impliquant l'exponentiation de matrice et des circuits QPE profonds) crée un « oracle lourd ». Cela augmente considérablement le coût par itération pour un adversaire tentant une attaque de pré-image basée sur l'algorithme de Grover, ce qui peut compenser l'accélération quadratique offerte par l'algorithme de Grover.
Conformité NIST PQC : Le schéma est présenté comme répondant aux critères de sécurité du NIST PQC (résistance aux attaques quantiques), de performance (temps constant par rapport à la longueur du message) et d'interopérabilité (sortie de 256 bits compatible avec les infrastructures existantes).
Perspectives : Les auteurs concluent que, bien que les limitations actuelles du matériel (bruit, décohérence) nécessitent une simulation pour la validation, l'approche offre une voie viable pour le développement de primitives cryptographiques robustes à mesure que la correction d'erreurs quantiques et la stabilité des qubits progressent.

Le document ne prétend pas un déploiement immédiat sur du matériel quantique réel, mais positionne QGH-256 comme un cadre théorique et une preuve de concept validée par simulation pour le hachage cryptographique post-quantique.