Right Divisibility in Erasing Semi-Thue Systems: A Minimal View of Intruder Deduction

Stel je voor dat je een meester-slotenmaker bent die probeert uit te vogelen of een dief een specifieke kluis kan openen. In de wereld van digitale beveiliging zijn berichten als vergrendelde dozen, en de "dief" (of indringer) heeft een gereedschapskist met operaties: ze kunnen twee dozen aan elkaar ritsen, ze vergrendelen met een sleutel, of ze verwerken tot een vingerafdruk. De grote vraag voor beveiligingsexperts is: "Gezien de dozen die de dief al heeft gestolen, kan hij een nieuwe, specifieke doos (zoals een geheime sleutel) bouwen met alleen zijn gereedschap?" Dit wordt het intruder deduction problem genoemd.

Om dit op te lossen, doen wetenschappers vaak alsof deze complexe dozen gewoon eenvoudige reeksen letters zijn. Als je alle sierlijke vormen weghaalt en alleen naar de volgorde van de letters kijkt, wordt het probleem een spel van woordpuzzels. Je hebt een beginwoord en een doelwoord, en je hebt een lijst met regels die je vertellen hoe je delen van woorden kunt afhakken of herschikken. De vraag is: "Kan ik me een weg van het startwoord naar het doelwoord hakken en plakken?" Dit artikel duikt diep in een zeer specifieke, vereenvoudigde versie van dit spel om precies te zien waar de regels het puzzelspel oplosbaar maken en waar ze het onmogelijk maken om ooit het antwoord te weten.

---

Het Grote Woordspel: Hakken, Plakken en de Grenzen van de Logica

In dit artikel besluiten de auteurs Raja O. P. Damanik en Alwen Tiu om te stoppen met het bekijken van de complexe, 3D-vormen van cryptografische berichten en ze in plaats daarvan te beschouwen als eenvoudige woorden. Stel je voor dat elk bericht gewoon een lange reeks kralen aan een ketting is. De "regels" die de indringer volgt, zijn als een paar magische scharen die de voorkant van de ketting of de achterkant van de ketting kunnen afknippen, maar nooit het midden.

De auteurs stellen een eenvoudige vraag: Als ik een ketting ABC heb en ik wil er Z van maken, kan ik dat doen door kralen aan de voorkant toe te voegen en dan mijn schaar te gebruiken om de voorkant af te knippen? Dit wordt het right-divisibility problem genoemd. Het klinkt eenvoudig, maar in de wereld van de logica is het een mijnenveld. Soms zijn de regels zo ingewikkeld dat geen enkele computer, hoe snel ook, ooit kan vertellen of het antwoord "ja" of "nee" is. Het artikel is een kaart die precies laat zien welke soorten scharen (regels) het spel oplosbaar maken en welke het spel volledig breken.

De "Prefix-Erasing" Scharen: De Makkelijke Modus

Eerst kijken de auteurs naar een specifiek type regel genaamd prefix-erasing. Stel je een regel voor die zegt: "Als je de letters 'BA' aan het begin van een woord ziet, knip ze eraf!" Dus BA-RED wordt RED. Als je een lijst van deze regels hebt en ze zijn "convergent" (wat betekent dat het niet uitmaakt in welke volgorde je de scharen toepast, je eindigt altijd met hetzelfde definitieve woord), bewijzen de auteurs iets wonderlijks: Je kunt de puzzel oplossen.

Ze zeiden niet alleen dat het mogelijk is; ze bouwden een supersnel algoritme om het te doen. Als je hen twee woorden geeft, kan hun methode in een flits (specifiek in een tijd die evenredig is aan de lengte van de woorden) vertellen of het ene woord in het andere kan worden veranderd. Het is alsof je een toverstaf hebt die direct vertelt of een specifieke sequentie van snedes zal werken. Dit bevestigt dat voor deze specifieke, "voorzijde-hakende" regels, het intruder deduction problem veilig en oplosbaar is.

De "Suffix-Erasing" Scharen: De Tricky Modus

Vervolgens draaien ze het scenario om. Wat als de scharen alleen de achterkant van het woord afknippen? Dit wordt suffix-erasing genoemd. Stel je een regel voor die zegt: "Als een woord eindigt op 'ED', knip het eraf!" Dus RED wordt R.

Hier wordt het spel veel moeilijker. De auteurs laten zien dat je de puzzel weliswaar nog steeds kunt oplossen, maar dat het niet zo eenvoudig is als de voorzijde-hakende versie. De methode die ze vonden, is als het proberen op te lossen van een doolhof door achterstevoren vanaf de uitgang te lopen. Je moet veel mogelijke paden verkennen, en in het slechtste geval groeit het aantal paden exponentieel (zoals een sneeuwbal die van een heuvel rolt en steeds groter wordt). De goede hoop is echter dat het wel oplosbaar is. Het artikel bewijst dat voor deze "achterzijde-hakende" regels er altijd een manier is om het antwoord te vinden, zelfs als dat wat rekenkracht kost.

De "Simultaneous Lifting" Valstrik: Game Over

Maar dan introduceren de auteurs een twist. Wat als de indringer een superkrachtig hulpmiddel heeft? Stel je een regel voor die zegt: "Neem een woord, hak het middengedeelte eraf, maar behoud de voorkant en de achterkant, en doe dit voor twee verschillende delen tegelijkertijd." Dit wordt simultaneous variable-lifting genoemd.

Dit klinkt als een kleine verandering, maar het breekt het spel volledig. De auteurs bewijzen dat als je deze gelijktijdige hakregels toestaat, het probleem onbeslisbaar wordt. Dit is een groot ding. Het betekent dat er voor dit type regel geen algoritme bestaat dat ooit een antwoord kan garanderen. Hoeveel tijd je een computer ook geeft, hij kan eeuwig blijven draaien zonder te weten of de indringer het doelwoord kan bouwen.

Om dit te bewijzen, hebben ze niet alleen gegokt; ze hebben aangetoond dat het oplossen van deze woordpuzzel exact hetzelfde is als het oplossen van een beroemd, onoplosbaar probleem genaamd het MPCP (Modified Post Correspondence Problem). Aangezien wiskundigen al weten dat de MPCP onmogelijk op te lossen is, hebben zij bewezen dat deze versie van het intruder deduction problem ook onmogelijk is.

Waarom dit ertoe doet

Je vraagt je misschien af: "Wie geeft erom of woorden worden afgehakt?" Het antwoord is: iedereen die encryptie gebruikt. Echte beveiligingsprotocollen gebruiken complexe wiskunde die lijkt op deze woordspellen. Door het probleem terug te brengen tot de essentie (gewoon woorden en eenvoudige snedes), hebben de auteurs de exacte grens gevonden tussen "oplosbaar" en "onmogelijk".

Ze hebben aangetoond dat als je beveiligingsregels lijken op eenvoudige voorzijde-hakende of achterzijde-hakende scharen, we tools kunnen bouwen om automatisch te controleren of een hacker kan inbreken. Maar als de regels te flitsend worden — waarbij gelijktijdige hakkingen op meerdere plaatsen tegelijk worden toegestaan — stuiten we op een muur waar we nooit zeker kunnen zijn. Dit helpt beveiligingsexperts om te weten welke soorten encryptiesystemen automatisch te analyseren zijn en welke te chaotisch zijn voor onze huidige tools.

Kortom, dit artikel is een gids voor de grenzen van de logica. Het vertelt ons dat hoewel we veel van de puzzels van de indringer kunnen oplossen, er een specifieke vorm van complexiteit bestaat waarbij het antwoord simpelweg niet bekend kan zijn. En weten waar die lijn getrokken is, is de eerste stap naar het bouwen van veiligere digitale sloten.