💻 computer science

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

Questo articolo dimostra che il puzzle logico Hotaru Beam è NP-completo e presenta un protocollo di prova a conoscenza zero fisico per verificare la conoscenza di una soluzione senza rivelarla.

Autori originali: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Pubblicato 2026-03-03

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Articolo originale sotto licenza CC BY 4.0 (http://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

Immagina di trovarti di fronte a un gioco di logica chiamato Hotaru Beam (che in giapponese significa "Raggio di Lucciole").

1. Il Gioco: Un Puzzle di Lucciole

Pensa a una griglia come a una scacchiera. Su questa scacchiera ci sono delle lucciole (cerchietti). Alcune lucciole hanno un numero scritto dentro, altre no.

L'obiettivo: Devi collegare tutte le lucciole tra loro disegnando dei "raggi di luce" (linee).
Le regole:
1. Le linee non possono incrociarsi né diramarsi (come un fiume che non può avere due rami).
2. Se una lucciola ha un numero (es. "2"), la sua linea deve fare esattamente 2 curve prima di fermarsi. Se non ha numeri, può fare quante curve vuole.
3. Alla fine, tutte le lucciole devono essere collegate in un unico grande gruppo.

Il problema è: esiste una soluzione per questo puzzle?
Gli autori del paper (Taisei, Peter e Takuro) hanno dimostrato due cose fondamentali:

È difficile: Trovare la soluzione è un compito così complesso che, se il puzzle è grande, potrebbe richiedere un tempo infinito anche per un computer superpotente (in termini tecnici, il gioco è "NP-completo"). È come cercare di risolvere un labirinto gigante senza mappa.
È dimostrabile senza svelare il segreto: Hanno creato un modo per dimostrare a qualcuno che conosci la soluzione, senza però mostrargliela.

2. La Magia: La "Prova a Conoscenza Zero" (Zero-Knowledge Proof)

Immagina di essere Peter (il prover) e di avere la soluzione del puzzle. Hai una Vera (il verifier) che vuole essere sicura che tu sappia davvero come risolverlo, ma non vuole che tu le mostri il disegno finale. Se te lo mostri, lei lo ruba e non è più un segreto!

Come fai a convincerla senza mostrare nulla? Usando un protocollo con le carte da gioco.

L'Analogia della "Scatola Magica"

Immagina che il puzzle sia coperto da un telo. Tu hai la mappa sotto il telo.

Il metodo: Invece di alzare il telo, usi delle carte coperte (con il dorso uguale per tutte) per simulare il tuo percorso.
Le carte:
- Cuori (♡): Rappresentano uno spazio vuoto sulla griglia dove la luce può passare.
- Fiori (♣): Rappresentano un muro o un percorso già occupato.
- Numeri: Le lucciole stesse.
- Pile di carte: Rappresentano le righe e le colonne della griglia.

3. Come funziona il trucco (Il Protocollo)

Ecco cosa fa Peter per convincere Vera passo dopo passo, usando solo carte e movimenti:

Preparazione: Peter dispone le carte sulla tavola per rappresentare la griglia vuota. Vera controlla che sia tutto a posto, poi tutte le carte vengono girate a faccia in giù. Nessuno vede più nulla, tranne Peter che può sbirciare (perché è lui che ha la soluzione).
Disegnare il raggio (Senza mostrare):
- Peter deve "disegnare" un raggio da una lucciola all'altra.
- Usa un trucco chiamato "Mescolamento a scorrimento". Immagina di avere una fila di carte coperte. Peter le sposta in modo circolare (come un nastro che gira) senza che Vera sappia di quanto le ha spostate.
- Poi, sceglie una carta specifica (quella che rappresenta il punto di partenza) e la gira.
- Con un altro trucco, sostituisce le carte "vuote" (Cuori) con carte "muro" (Fiori) lungo il percorso che lui sa essere corretto, ma lo fa in modo che Vera veda solo che qualcosa è cambiato, senza capire dove esattamente o quanto è lungo il percorso.
- Il trucco delle curve: Se il raggio deve fare una curva, Peter usa un altro meccanismo di carte per cambiare direzione senza che Vera veda l'angolo.
La Tavola delle Connessioni (Il Registro):
- Oltre alla griglia, Peter ha un "registro" (una tabella di carte) che tiene traccia di quali lucciole sono collegate.
- Ogni volta che collega due lucciole, aggiorna il registro con un trucco logico (usando coppie di carte speciali) per dire: "Queste due fanno parte dello stesso gruppo".
- Vera non vede i valori, ma alla fine controlla che il registro sia tutto pieno di "Vero" (T), il che significa che tutte le lucciole sono collegate.

4. Perché è geniale?

Il punto di forza di questo lavoro è che Peter non mente mai, ma non rivela mai nulla.

Se Peter non sapesse la soluzione, non riuscirebbe a fare i movimenti con le carte in modo coerente. Vera lo scoprirebbe subito (perché le carte non combacerebbero).
Se Peter conosce la soluzione, può dimostrare di averla seguendo le regole, ma Vera alla fine non sa quale sia la soluzione. Potrebbe essere una delle milioni di soluzioni possibili, ma lei non ne ha idea.

In sintesi

Gli autori hanno preso un gioco di logica giapponese, dimostrato che è matematicamente molto difficile da risolvere, e poi hanno inventato un gioco di carte fisico (che puoi fare a casa con un mazzo di carte vero) per dimostrare a un amico: "Guarda, so come si risolve questo puzzle, ma non te lo dirò mai!".

È come se tu avessi la chiave di un caveau blindato. Invece di aprire la porta e mostrare l'oro, fai un trucco con le mani che convince l'osservatore che hai la chiave, senza mai toccare la serratura o mostrare cosa c'è dentro.

Il risultato? Un nuovo modo sicuro e divertente per dimostrare la conoscenza di soluzioni a puzzle complessi, usando solo carta, carte e un po' di magia matematica.

1. Il Problema: Hotaru Beam

Hotaru Beam è un puzzle logico creato da Nikoli, giocato su una griglia rettangolare.

Componenti: Sulla griglia sono posizionati cerchi chiamati "lucciole" (hotaru). Ogni lucciola ha un punto di partenza (un punto sulla sua circonferenza) e può contenere un numero intero.
Obiettivo: Disegnare linee (raggi di luce) partendo dal punto di ogni lucciola per collegare tutte le lucciole in un'unica componente connessa.
Vincoli:
1. Non intersezione e non diramazione: I raggi non possono incrociarsi né ramificarsi; un raggio non può terminare nel punto di partenza di un altro raggio.
2. Vincolo di curvatura: Se una lucciola contiene un numero $k$ , il raggio che parte da essa deve avere esattamente $k$ curve (pieghe). Se non c'è numero, il numero di curve è illimitato.
3. Connettività: Tutte le lucciole devono essere collegate tra loro attraverso i raggi.

2. Metodologia e Risultati Teorici

A. NP-Completezza

Gli autori dimostrano che decidere se un'istanza di Hotaru Beam ammette una soluzione è un problema NP-completo.

Dimostrazione: La prova avviene tramite una riduzione polinomiale dal problema Planar Monotone 3-SAT (una variante del problema di soddisfacibilità booleana con formule monotone e rappresentazione planare).
Costruzione: Vengono creati "gadgets" (sottoreti di lucciole e vincoli) che simulano le variabili booleane e le clausole del 3-SAT.
- I gadgets delle variabili permettono due configurazioni di raggi (vero/falso).
- I gadgets delle clausole (positive e negative) permettono di collegarsi alle variabili solo se la clausola è soddisfatta.
- La connettività globale nel puzzle corrisponde alla soddisfacibilità della formula booleana.

B. Zero-Knowledge Proof (ZKP) Fisico

Il contributo principale è la progettazione di un protocollo ZKP fisico (realizzabile con carte da gioco e oggetti quotidiani) che permette a un "Prover" (Peter) di convincere un "Verificatore" (Vera) di conoscere una soluzione senza rivelare nulla della soluzione stessa.

Strumenti e Rappresentazione:

Carte: Si utilizzano carte con simboli (♣, ♠, ♡, ♢) e numeri. Le carte sono inizialmente coperte (faccia in giù).
Strutture di dati:
1. La Scacchiera (Board): Una griglia $w \times h$ di carte che rappresenta i punti della griglia. Le carte $\heartsuit$ indicano punti liberi, le carte $\clubsuit$ indicano percorsi occupati dai raggi, e le carte numeriche indicano le lucciole.
2. Tabella delle Connessioni (Connections Table): Una struttura a colonne che traccia la connettività tra le lucciole. Ogni colonna contiene una carta numerica seguita da coppie di carte logiche (rappresentanti Vero/Falso). Se la coppia $(i, j)$ è Vero, le lucciole $i$ e $j$ sono connesse.

Protocollo Principale:
Il protocollo si basa sull'incorporazione sequenziale dei raggi della soluzione:

Inizializzazione: Peter dispone le carte secondo l'istanza del problema. Vera verifica l'ordine iniziale e le carte vengono coperte.
Incorporamento di un segmento (Segment Embedding):
- Peter deve "disegnare" un segmento del raggio sostituendo carte $\heartsuit$ (libere) con $\clubsuit$ (occupate) o $\diamondsuit$ (marcatori).
- Viene utilizzato un protocollo di maschera (mask sequence) e uno shuffle a spostamento di mucchi (pile-shifting shuffle) per garantire che Vera veda solo che un segmento valido è stato disegnato, senza conoscere la lunghezza esatta ( $l$ ) o la direzione precisa, a meno che non sia richiesto dal protocollo.
- Per i raggi con vincoli di curvatura, il processo viene ripetuto segmentando il raggio alle curve.
Gestione della Connettività:
- Quando un raggio collega la lucciola $s$ alla lucciola $t$ , Peter aggiorna la Connections Table impostando la coppia logica $(s, t)$ su Vero.
- Viene utilizzato un protocollo di copia dei valori logici e disgiunzione per aggiornare la tabella senza rivelare quali lucciole sono state colpite, mantenendo l'invariante che la tabella riflette correttamente la connettività attuale.
Verifica Finale:
- Dopo aver incorporato tutti i raggi, Peter esegue un'operazione di chiusura sulla Connections Table per assicurarsi che tutte le coppie logiche siano Vero (garantendo che tutte le lucciole siano in un'unica componente connessa).
- Vera scopre le carte della tabella delle connessioni. Se tutte sono Vero, accetta la prova.

3. Contributi Chiave e Innovazioni

Gestione del Vincolo di Curvatura: A differenza di altri puzzle come Numberlink o Bridges (che hanno già ZKP fisici), Hotaru Beam impone un numero specifico di curve. Gli autori introducono un protocollo innovativo per incorporare i raggi rivelando il numero di curve senza rivelare la geometria esatta del percorso.
Tracciamento Dinamico della Connettività: L'introduzione della Connections Table permette di verificare la condizione di connettività globale in modo incrementale e sicuro, senza dover rivelare l'intera struttura del grafo durante il processo.
Protocolli Fisici Avanzati: L'uso combinato di pile-shifting shuffle, pile choosing e protocolli di appartenenza a insiemi permette di nascondere informazioni critiche (come la direzione di un segmento o la lunghezza esatta) mantenendo la validità logica della prova.

4. Significato e Implicazioni

Teoria della Complessità: La dimostrazione di NP-completezza colloca Hotaru Beam nella classe dei problemi computazionalmente difficili, confermando che non esistono algoritmi efficienti noti per risolverlo in generale.
Sicurezza e Crittografia Fisica: Il lavoro dimostra che è possibile costruire protocolli ZKP complessi e specifici per puzzle geometrici utilizzando solo oggetti fisici, rendendo la crittografia accessibile e comprensibile anche ai non esperti.
Generalizzabilità: Le tecniche sviluppate (in particolare la gestione dei vincoli geometrici e il tracciamento della connettività) offrono spunti per la progettazione di ZKP fisici per altri problemi su griglie o per la dimostrazione dell'esistenza di specifici grafi in contesti fisici.

In sintesi, il paper fornisce una soluzione completa al problema della complessità di Hotaru Beam e propone un protocollo pratico, sicuro ed efficiente per dimostrare la conoscenza di una soluzione senza comprometterne la segretezza.