💻 computer science

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

Questo articolo introduce QGH-256, un nuovo algoritmo di hashing quantistico che genera impronte digitali a 256 bit mappando i messaggi su grafi pesati su una griglia toroidale e utilizzando la stima della fase quantistica per estrarre caratteristiche spettrali che catturano sia proprietà strutturali che dinamiche, dimostrando una forte sensibilità crittografica e fattibilità attraverso simulazioni Qiskit.

Autori originali: Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

Pubblicato 2026-06-30

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

Articolo originale sotto licenza CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Il quadro generale: Una nuova impronta digitale

Immaginate di dover trasformare una storia lunga e disordinata (come un romanzo) in un'unica impronta digitale unica. Nel mondo digitale, di solito lo facciamo con le "funzioni hash" (come SHA-256). Ma gli autori di questo documento sono preoccupati che i futuri computer quantistici possano essere in grado di rompere queste vecchie impronte digitali.

Per questo motivo, hanno creato un nuovo tipo di impronta digitale chiamata QGH-256. Invece di limitarsi a fare calcoli matematici sui numeri, questo metodo trasforma il vostro messaggio in una mappa, invia un camminatore attraverso quella mappa e poi utilizza la fisica quantistica per misurare le "vibrazioni" della mappa stessa per creare l'impronta digitale finale.

Fase 1: Trasformare le parole in una mappa (Il Camminatore)

L'analogia: Immaginate un piccolo robot che cammina su una griglia quadrata (come una scacchiera) che si avvolge su se stessa (se si esce dal bordo destro, si rientra dal lato sinisto). Questa è chiamata una "griglia toroidale".

Come funziona: Prendete il vostro messaggio (ad esempio, "Ciao") e lo trasformate in codice binario (0 e 1).
La camminata: Il robot non cammina a caso. Legge il vostro messaggio bit per bit.
- Se vede 00, cammina verso Nord.
- Se vede 01, cammina verso Sud.
- Se vede 10, cammina verso Est.
- Se vede 11, cammina verso Ovest.
La mappa: Mentre il robot cammina, lascia una scia. Ogni volta che attraversa una linea (un arco) sulla griglia, aggiunge un "peso" a quella linea basato sui numeri presenti nel messaggio.
Il risultato: Si ottiene una mappa pesata unica. Se cambiate anche una sola lettera nel messaggio (come da "Ciao" a "Ciaa"), il robot percorrerà un sentiero completamente diverso, creando una mappa totalmente differente.

Perché è importante: Il documento afferma che, poiché la mappa è non orientata (il robot non registra in quale direzione stava guardando, ma solo quante volte ha attraversato una linea), è incredibilmente difficile osservare la mappa e capire il messaggio originale. È come cercare di indovinare l'esatto percorso fatto da un escursionista guardando solo l'erba calpestata, senza sapere da dove sia partito o dove sia finito.

Fase 2: Ascoltare la "musica" della mappa (Impronta Spettrale)

Ora che abbiamo questa mappa unica, come la trasformiamo in un'impronta digitale? Gli autori utilizzano un concetto derivato dalla fisica chiamato Analisi Spettrale.

L'analogia: Immaginate che la vostra mappa sia un enorme tamburo. Se lo colpite, vibra. Ogni tamburo ha un set specifico di "note" (frequenze) che può emettere, determinate dalla sua forma e da quanto è tesa la pelle.

In matematica, queste "note" sono chiamate autovalori (eigenvalues).
La "tensione" e la "forma" della mappa sono determinate dal Laplaciano del Grafo (una matrice matematica sofisticata che descrive le connessioni e i pesi della mappa).

Il tocco quantistico:
Di solito, per ascoltare queste note, sarebbe necessario risolvere equazioni complesse. Ma questo documento utilizza un algoritmo di Stima della Fase Quantistica (QPE - Quantum Phase Estimation).

Pensate alla QPE come a un microfono super sensibile che può "ascoltare" istantaneamente il tamburo e dirvi esattamente quali note sta suonando.
Dettaglio cruciale: Gli autori non si limitano ad ascoltare una singola nota. Inviano una "sovrapposzione" (uno stato quantistico che è come una miscela di tutti i possibili punti di partenza) nel sistema. Ciò significa che il computer quantistico sente l'intera canzone della mappa contemporaneamente, inclusi il modo in cui le note interagiscono tra loro.

Perché è speciale:
Due mappe diverse potrebbero accidentalmente avere lo stesso set di note (questo è chiamato essere "cospettrali"). Tuttavia, poiché gli autori ascoltano come le note interagiscono con la struttura specifica della mappa (gli autovettori), possono distinguere tra due mappe che suonano uguali ma che hanno forme diverse. Questo previene le "collisioni" (ovvero quando due messaggi diversi producono la stessa impronta digitale).

Fase 3: La Traccia del Calore (L'impronta digitale finale)

Una volta che il computer quantistico ha identificato le "note" (autovalori), gli autori calcolano quella che viene chiamata Traccia del Calore (Heat Trace).

L'analogia: Immaginate di versare acqua calda sulla vostra mappa. Il calore si diffonde (si propaga) attraverso la griglia.

La "Traccia del Calore" misura quanto velocemente si diffonde il calore.
Misurando questo fenomeno a diversi intervalli di tempo, si ottiene una firma unica di come è fatta la mappa.
Questa firma viene poi compressa in un codice a 256 bit (una stringa di 256 zeri e uno). Questa è la vostra impronta digitale QGH-256 finale.

Perché è sicuro? (L'effetto valanga)

Il documento testa questo nuovo metodo contro le regole di una buona serratura:

Determinismo: Se scrivete "Ciao" due volte, otterrete esattamente la stessa impronta digitale entrambe le volte.
L'effetto valanga: Se cambiate anche solo una lettera (ad esempio, da "Ciao" a "Ciaa"), il robot percorrerà un sentiero completamente diverso. Questo cambia la mappa, che cambia le "note", che cambia la "diffusione del calore", risultando in un'impronta digitale a 256 bit completamente diversa.
Resistenza alla pre-immagine: Se qualcuno ruba l'impronta digitale, non può procedere a ritroso per trovare il messaggio originale. La matematica è troppo complessa e la mappa perde informazioni sulla direzione della camminata.

Il limite: È una simulazione

Il documento ammette che attualmente non disponiamo di computer quantistici abbastanza grandi o abbastanza "silenziosi" per eseguire questo processo nella realtà.

Il problema: I veri computer quantistici sono "rumorosi" (come una radio con interferenze). Se si cerca di ascoltare le "note" della mappa su una macchina rumorosa, il risultato potrebbe essere errato e l'impronta digitale potrebbe cambiare ogni volta che la si esegue.
La soluzione nel documento: Gli autori hanno eseguito i loro test su un simulatore (un programma per computer che finge di essere un computer quantistico perfetto). Questo ha dimostrato che la matematica funziona perfettamente in teoria.
Futuro: Credono che, man mano che i computer quantistici diventeranno migliori e meno rumorosi, questo metodo rappresenterà una difesa robusta contro gli hacker, anche quelli dotati di computer quantistici.

Riassunto

Gli autori hanno costruito una nuova serratura digitale.

Trasformano il vostro messaggio in un sentiero di camminata unico su una griglia.
Utilizzano un computer quantistico per ascoltare le vibrazioni di quel sentiero.
Trasformano quelle vibrazioni in un codice a 256 bit.

Affermano che questo metodo è più difficile da violare rispetto ai metodi attuali perché si basa sulla complessa fisica delle vibrazioni di un grafo, rendendo molto difficile per i futuri computer quantistici indovinare il messaggio originale o trovare due messaggi che producano lo stesso codice.

Sintesi Tecnica: Funzione di Hash Quantistica Basata sulle Proprietà Spettrali dei Grafi e sulla Dinamica di un Discrete Walker

Problematica
Il documento affronta la crescente vulnerabilità delle funzioni di hash classiche (ad esempio, SHA-256, MD5) rispetto alle minacce del calcolo quantistico. Nello specifico, algoritmi come quelli di Shor e Grover pongono rischi esistenziali per gli standard attuali, fattorizzando efficientemente grandi interi o accelerando la ricerca non strutturata, rispettivamente. Sebbene il National Institute of Standards and Technology (NIST) stia standardizzando la Crittografia Post-Quantistica (PQC), esiste la necessità di schemi di hashing quantum-native o resilienti al calcolo quantistico che possano resistere sia ad attacchi classici che quantistici. Gli approcci esistenti spesso si affidano a operazioni bitwise lineari, che potrebbero non offrire una resistenza sufficiente contro gli acceleramenti quantistici o potrebbero non essere in grado di distinguere tra grafi strutturalmente diversi che condividono lo stesso spettro di autovalori (grafi cospettrali).

Metodologia
Gli autori propongono QGH-256, un nuovo algoritmo di hashing spettrale che integra la dinamica classica di un discrete walker con l'analisi spettrale di grafi quantistici. Il flusso di lavoro si articola attraverso le seguenti fasi:

Costruzione del Grafo Indotta dal Messaggio:
- I messaggi in input vengono convertiti in binario UTF-8 e segmentati in blocchi.
- Un discrete walker classico opera su una griglia toroidale fissa di $4 \times 4$ . A differenza dei cammini casuali (random walks), la direzione del walker ad ogni passo è dettata deterministicamente dai bit del messaggio (specificamente, il primo e l'ultimo bit di ogni blocco determinano la direzione: Nord, Sud, Est o Ovest).
- Il valore decimale di ogni blocco funge da peso per l'arco attraversato.
- Questo processo genera un grafo non orientato pesato $G = (V, E, W)$ , unico e riproducibile, per ogni messaggio in input. Gli autori osservano che recuperare il messaggio originale dal grafo è computazionalmente difficile a causa della perdita di informazione direzionale nei pesi degli archi non orientati e della complessità nel ricostruire la sequenza di attraversamento.
Impronta Digitale Spettrale tramite Quantum Phase Estimation (QPE):
- La struttura del grafo viene codificata in una matrice Laplaciana $L = D - A$ (Matrice di Grado meno Matrice di Adiacenza).
- Per utilizzare algoritmi quantistici, $L$ viene trasformata in un operatore unitario $U = e^{iLt}$ tramite l'esponenziazione di matrici.
- La Quantum Phase Estimation (QPE) è applicata a $U$ . Fondamentalmente, l'input al circuito QPE non è un singolo autovettore, ma uno stato di sovrapposizione definito nella base dei nodi del grafo ( $|\psi\rangle = \sum \alpha_i |i\rangle$ ).
- Poiché lo stato di input è una sovrapposizione degli autovettori della Laplaciana, il processo QPE agisce come un analizzatore spettrale, decomponendo lo stato nelle sue componenti di frequenza (fase). La probabilità di misurare una fase specifica è proporzionale al quadrato della sovrapposizione tra lo stato di input e il corrispondente autovettore.
Traccia del Calore e Generazione dell'Hash:
- Gli autori calcolano un "impronta digitale spettrale" valutando il valore della traccia del calore $h(t) = \sum |c_k|^2 e^{-t\tilde{\lambda}_k}$ attraverso molteplici scale temporali. Questa metrica cattura sia l'informazione sugli autovalori che il contributo degli autovettori (tramite i coefficienti $c_k$ ).
- Questo vettore di caratteristiche viene post-elaborato e compresso in un hash binario a 256 bit.

Contributi Chiave

Risoluzione delle Collisioni Co-spettrali: Un primario contributo teorico è la capacità del metodo di distinguere tra grafi cospettrali (grafi con spettri di autovalori identici ma strutture diverse). Utilizzando uno stato di sovrapposizione come input per la QPE, l'impronta digitale spettrale risultante dipende dalle sovrapposizioni degli autovettori ( $|c_k|^2$ ), non solo dagli autovalori. Ciò garantisce che grafi non isomorfi producano impronte distinte anche se condividono lo stesso spettro.
Efficienza a Passi Fissi: Gli autori hanno migliorato i precedenti algoritmi basati su walker fissando il numero di passi del walker (10.000) e regolando la dimensione del blocco in base alla lunghezza del messaggio. Ciò assicura che il costo computazionale della fase di generazione del grafo sia indipendente dalla dimensione del messaggio in input.
Design Quantum-Native: L'algoritmo sfrutta le proprietà intrinseche della meccanica quantistica (sovrapposizione e stima della fase) per generare impronte digitali ad alta entropia, posizionandolo come candidato per la sicurezza post-quantistica.

Risultati e Valutazione
Il documento valuta QGH-256 utilizzando un simulatore di stato Qiskit (Seeded Qiskit Statevector Simulator) per garantire risultati deterministici e privi di rumore, riconoscendo che l'hardware NISQ (Noisy Intermediate-Scale Quantum) attuale introdurrebbe fluttuazioni che influenzerebbero il determinismo.

Determinismo: Input identici hanno prodotto costantemente hash a 256 bit identici.
Effetto Avalanche: Una variazione di un singolo bit nell'input (ad esempio, "Hello" vs "Hella") ha prodotto una distanza di Hamming significativamente alta nell'output, confermando la sensibilità alle perturbazioni dell'input.
Resistenza alla Pre-immagine: Gli autori sostengono che invertire l'hash sia impraticabile a causa della complessità del problema inverso dell'autovalore del grafo e dell'ambiguità introdotta dalla natura non orientata del grafo.
Tempo di Computazione: Il tempo di esecuzione è stato osservato rimanere quasi costante indipendentemente dalla lunghezza del messaggio, grazie alla dimensione fissa della griglia e al numero fisso di passi del walker.

Significatività e Rivendicazioni
Il documento sostiene che QGH-256 offra un'alternativa robusta all'hashing classico integrando proprietà topologiche e dinamiche del grafo.

Resilienza Quantistica: Gli autori affermano che la dipendenza dell'algoritmo da calcoli spettrali complessi e non lineari (che coinvolgono l'esponenziazione di matrici e circuiti QPE profondi) crea un "oracolo pesante". Ciò aumenta significativamente il costo per iterazione per un avversario che tenta un attacco alla pre-immagine basato su Grover, potenzialmente compensando il vantaggio quadratico offerto dall'algoritmo di Grover.
Conformità NIST PQC: Lo schema è presentato come conforme ai criteri di sicurezza del NIST PQC (resistenza agli attacchi quantistici), prestazioni (tempo costante rispetto alla lunghezza del messaggio) e interoperabilità (output a 256 bit compatibile con le infrastrutture esistenti).
Prospettive Future: Gli autori concludono che, sebbene i limiti dell'hardware attuale (rumore, decoerenza) richiedano la simulazione per la validazione, l'approccio fornisce una via percorribile per lo sviluppo di primitive crittografiche robuste man mano che la correzione degli errori quantistici e la stabilità dei qubit maturano.

Il documento non rivendica l'implementazione immediata su hardware quantistico reale, ma posiziona QGH-256 come un framework teorico e una prova di concetto validata tramite simulazione.