💻 computer science

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

Deze paper bewijst dat Hotaru Beam NP-volledig is en presenteert een fysisch protocol voor een zero-knowledge-bewijs dat toelaat een oplossing voor dit raadsel te verifiëren zonder deze te onthullen.

Oorspronkelijke auteurs: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Gepubliceerd 2026-03-03

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een raadsel oplost, zoals een kruiswoordpuzzel, maar dan met lichtstralen en vuurvliegjes. Dat is Hotaru Beam. In dit artikel van onderzoekers van de Chuo Universiteit in Tokio wordt uitgelegd hoe je kunt bewijzen dat je de oplossing voor zo'n raadsel kent, zonder de oplossing zelf aan te tonen.

Hier is een uitleg in gewone taal, met een paar leuke vergelijkingen.

1. Het Raadsel: Hotaru Beam

Stel je een rooster voor (zoals een schaakbord), maar dan met vuurvliegjes (de "Hotaru") erop. Elke vuurvlieg heeft een getal of een stipje.

De taak: Je moet lichtstralen trekken van de ene vuurvlieg naar de andere.
De regels:
1. De stralen mogen elkaar niet kruisen en mogen niet vertakken.
2. Als er een getal in een vuurvlieg staat (bijvoorbeeld '2'), mag de stral precies twee keer buigen.
3. De belangrijkste regel: Alle vuurvliegjes moeten uiteindelijk met elkaar verbonden zijn in één grote groep.

Het probleem is dat het vinden van de juiste route erg moeilijk kan zijn. De onderzoekers bewijzen eerst wiskundig dat dit raadsel "NP-compleet" is. Dat is een fancy manier van zeggen: "Het is een raadsel dat heel lastig op te lossen is, maar als je de oplossing al hebt, kun je heel snel controleren of hij klopt."

2. Het Magische Bewijs: Zero-Knowledge Proof

Nu komt het interessante deel. Stel, jij hebt de oplossing gevonden. Je wilt je vriendin Vera overtuigen dat je het echt weet, maar je wilt haar niet laten zien hoe je de lijnen hebt getrokken. Je wilt haar niet verraden waar je buigt of welke route je neemt.

In de wiskunde heet dit een Zero-Knowledge Proof (een "weten-zonder-te-vertellen"-bewijs).

De analogie: Stel je voor dat je in een donkere kamer staat met een gesloten doos. Je vriendin vraagt: "Heb je de sleutel?" Jij zegt: "Ja." Ze zegt: "Bewijs het, maar laat de sleutel niet zien."
- In plaats van de sleutel te laten zien, doe je een trucje: je laat haar zien dat je de doos kunt openen en sluiten zonder dat ze de sleutel ziet. Als je dit vaak genoeg doet, is de kans dat je het toeval hebt gedaan verwaarloosbaar klein. Dan gelooft ze je.

3. De Magische Kaarten (De "Physical" Deel)

De onderzoekers hebben een manier bedacht om dit te doen met speelkaarten, zodat je het niet op een computer hoeft, maar echt met je handen kunt doen.

De Spelers: Jij bent Peter (de bewijzer) en je vriendin is Vera (de controleur).
De Kaarten:
- Harten (♡): Een leeg vakje op het bord.
- Klaveren (♣): Een vakje dat al bezet is door een lichtstraal.
- Ruiten (♢): Een speciaal markeringspunt (een "startpunt" voor de volgende stap).
- Getallenkaarten: De vuurvliegjes zelf.
- Schoppen (♠) en Ruiten (♢) paren: Gebruikt om te zeggen "Ja" (waar) of "Nee" (onwaar).

4. Hoe werkt het bewijs? (De Trucjes)

Peter moet Vera overtuigen dat hij een geldig pad heeft getekend, zonder het pad te laten zien. Hij gebruikt twee slimme hulpmiddelen:

A. Het Bord (De Lichtstralen)

Peter legt kaarten neer die het hele bord voorstellen.

Verbergen: Hij legt de kaarten met de rug naar boven. Vera ziet niets.
Het "Masker": Peter gebruikt een trucje met kaarten (een "masker") om een stukje van zijn lichtstraal te tekenen. Hij vervangt een paar "lege" kaarten (Harten) door "bezet" kaarten (Klaveren).
De Wiskundige Magie: Hij doet dit met een shuffle (het schudden van stapels kaarten). Hij schudt de kaarten zo, dat Vera niet kan zien waar hij precies heeft getekend, maar ze kan wel zien dat de regels zijn gevolgd (bijvoorbeeld: "Er is een stukje getekend, en het past in het rooster").
De Bochten: Als het getal in de vuurvlieg zegt dat er 2 bochten zijn, doet hij dit proces twee keer. Hij laat Vera zien dat er precies twee keer een "bocht" is gemaakt, maar hij laat niet zien naar welke kant de bocht gaat.

B. De Verbindingslijst (De "Connectivity Table")

Dit is het slimste deel. Het grootste probleem bij dit raadsel is dat alle vuurvliegjes aan elkaar moeten hangen. Hoe bewijs je dat, zonder de lijnen te laten zien?

Peter houdt een lijst bij (een tabel van kaarten) die aangeeft welke vuurvliegjes met elkaar verbonden zijn.

Stel, vuurvlieg 1 en vuurvlieg 5 zijn verbonden. Dan zet hij in de lijst bij "1" en "5" een kaartje dat zegt "JA".
Als hij een nieuwe lichtstraal tekent die vuurvlieg 5 verbindt met vuurvlieg 3, dan worden 1, 5 en 3 allemaal met elkaar verbonden.
De truc: Peter gebruikt een kaart-truc om de "JA"-kaarten te combineren. Als 1 met 5 verbonden is, en 5 met 3, dan maakt hij automatisch een "JA" tussen 1 en 3.
Aan het einde kijkt Vera in de lijst. Als er overal "JA" staat, weet ze dat alle vuurvliegjes aan elkaar hangen, zonder dat ze ooit heeft gezien hoe de lijnen eruitzagen.

5. Waarom is dit cool?

Tot nu toe waren dit soort bewijzen vaak alleen voor computers of erg ingewikkeld. Dit artikel laat zien dat je dit kunt doen met gewone speelkaarten.

Het is veilig: Vera kan niet achterhalen wat het antwoord is, zelfs niet als ze heel slim is.
Het is betrouwbaar: Als Peter probeert te liegen (bijvoorbeeld door een onmogelijke lijn te tekenen), zal de kaart-truc vroeg of laat mislukken en zal Vera het zien.
Het is toepasbaar: De onderzoekers denken dat deze kaart-trucs ook voor andere raadsels (zoals Sudoku of andere lijn-puzzels) kunnen worden gebruikt.

Kortom: Dit artikel is een handleiding voor hoe je een raadseloplossing kunt "vertonen" alsof je een goochelaar bent: je laat je publiek zien dat je de magie kunt doen, maar je houdt je geheimen (de oplossing) strak voor je borst. En je doet het allemaal met een pak kaarten op een tafel.

1. Probleemdefinitie: Hotaru Beam

Hotaru Beam is een logische puzzel, ontwikkeld door het Japanse bedrijf Nikoli, die wordt gespeeld op een rechthoekig rooster.

Doel: Alle "vliegen" (cirkels met een stip op de rand) met elkaar verbinden door lijnen (stralen) te trekken.
Regels:
1. Geen kruisingen of vertakkingen: Stralen mogen elkaar niet kruisen en mogen niet vertakken. Een straal eindigt altijd op de rand van een vlieg.
2. Buigingsbeperking: Sommige vliegen bevatten een getal dat het exacte aantal keren aangeeft dat de stral moet buigen. Als er geen getal staat, is het aantal buigingen onbeperkt.
3. Connectiviteit: Alle vliegen moeten via de getekende stralen verbonden zijn tot één enkel samenhangend component.
Complexiteit: Het bepalen of een gegeven puzzel een oplossing heeft, is een beslissingsprobleem.

2. Methodologie en Bewijs van NP-Completiteit

De auteurs bewijzen eerst dat Hotaru Beam NP-compleet is.

Reductie: Ze voeren een reductie uit vanuit het Planar Monotone 3-SAT probleem (een variant van het 3-SAT probleem waarbij de formule monotoon is en als planaire graaf kan worden weergegeven).
Constructie:
- Variabelen worden gemodelleerd met "gadgets" (specifieke roosterconfiguraties) die twee mogelijke toestanden hebben (waar/true of onwaar/false), corresponderend met de richting van de stralen.
- Clauses (logische disjuncties) worden gemodelleerd met gadgets die verbinding maken met de variabelen.
- Een oplossing voor de Hotaru Beam-puzzel bestaat dan en slechts dan als de oorspronkelijke 3-SAT formule satisfiable is.
Conclusie: Omdat het probleem in NP ligt (een oplossing is in polynomiale tijd te verifiëren) en NP-moeilijk is (via reductie), is Hotaru Beam NP-compleet.

3. Methodologie: Fysieke Zero-Knowledge Proofs (ZKP)

Het hoofddoel van het artikel is het ontwerpen van een fysieke Zero-Knowledge Proof voor Hotaru Beam. Dit betekent dat een bewijzer (Peter) aan een verifieerder (Vera) kan bewijzen dat hij de oplossing kent, zonder enige informatie over de oplossing zelf prijs te geven.

Het Protocol:
Het protocol maakt gebruik van kaarten met symbolen (♣, ♠, ♡, ♢) en nummers.

Data-structuren:
1. Het Bord (Board): Een rooster van kaarten dat het spelbord representeren.
  - Vliegen worden weergegeven door nummers.
  - Beschikbare roosterpunten worden weergegeven door ♡-kaarten.
  - Bezette punten (onderdeel van een straal) worden gemarkeerd met ♣-kaarten.
2. Connectiviteitstabel (Connections Table): Een structuur van $n$ kolommen (voor elke vlieg) die de connectiviteit bijhoudt. Elke kolom bevat een logisch paar kaarten (♣♡ voor "waar", ♡♣ voor "onwaar") dat aangeeft of twee vliegen in hetzelfde samenhangende component zitten.

Kernprotocollen:

Segment Embedding Protocol: Peter moet een segment van een stral tekenen (een reeks kaarten van ♡ naar ♣) zonder de lengte of richting te onthullen.
- Dit wordt gedaan met een masker-sequentie en een pile-shifting shuffle (een protocol waarbij kaartenstapels willekeurig worden verschoven zodat de absolute positie onbekend blijft).
- Peter vervangt een reeks ♡-kaarten door ♣-kaarten en een specifieke ♢-kaart, maar Vera ziet alleen dat de vervanging conform de regels is gebeurd, niet waar of hoe lang de stral is.
Logische Operaties: Om de connectiviteit bij te houden, gebruikt Peter protocollen voor logische OR-bewerkingen op de kaartenparen. Als twee vliegen verbonden worden, worden de corresponderende waarden in de connectiviteitstabel bijgewerkt naar "waar" (T).
Verificatie van het einde: Wanneer een stral een vlieg bereikt, moet Peter bewijzen dat de eindkaart een nummer is (een vlieg) zonder de waarde of positie te onthullen. Dit wordt gedaan door een wisseloperatie met de connectiviteitstabel.

Afronding:
Na het tekenen van alle stralen, voert Peter een reeks operaties uit om de connectiviteitstabel te "samenstellen". Omdat de oplossing een samenhangend component moet vormen, moeten uiteindelijk alle logische paren in de tabel "waar" (T) zijn. Vera controleert aan het einde of alle paren inderdaad T zijn.

4. Belangrijkste Bijdragen

NP-Completiteit Bewijs: Het eerste formele bewijs dat Hotaru Beam NP-compleet is.
Fysieke ZKP Implementatie: Het ontwikkelen van een volledig werkend fysiek protocol met kaarten voor Hotaru Beam.
Innovatieve Protocollen:
- Een methode om stralen te tekenen met een specifiek (of onbekend) aantal buigingen zonder de geometrie te onthullen.
- Een dynamische "connectivity table" die de samenhang van het netwerk bijhoudt zonder de exacte paden te onthullen.
Unieke Uitdaging: Het oplossen van de complexiteit die ontstaat door de combinatie van de connectiviteitsbeperking (gemeenschappelijk bij puzzles zoals Numberlink) en de strikte beperking op het aantal buigingen.

5. Resultaten en Betekenis

Resultaat: Het papier demonstreert dat het mogelijk is om een complexe geometrische puzzel met strikte topologische en meetkundige beperkingen op te lossen in een Zero-Knowledge setting.
Betekenis:
- Toepasbaarheid: De ontwikkelde protocollen (vooral het segment embedding en het bijhouden van connectiviteit) kunnen worden toegepast op andere roosterpuzzels en problemen die het bestaan van specifieke grafen of paden vereisen.
- Educatief en Praktisch: Fysieke ZKPs maken cryptografische concepten toegankelijk voor niet-experts, wat de betrouwbaarheid en implementeerbaarheid van deze protocollen vergroot.
- Theoretische Inzichten: Het bewijst dat zelfs bij puzzels met complexe "global constraints" (zoals "alle punten moeten verbonden zijn" en "exact X buigingen"), efficiënte en veilige verificatie mogelijk is zonder de oplossing te lekken.

Samenvattend biedt dit artikel een robuust wiskundig bewijs van de complexiteit van Hotaru Beam en een creatieve, fysieke oplossing voor het veilig verifiëren van oplossingen, wat een waardevolle bijdrage levert aan het veld van de fysieke cryptografie en de complexiteitstheorie.