💻 computer science

Formal Verification of Probing Security via Conditional Independence

Dit artikel stelt een nieuwe formele verificatiemethode voor voor de proefveiligheid van gemaskerde cryptografische algoritmen door gebruik te maken van probabilistische separatielogica (Lilac) om een verband te leggen tussen non-interferentie-eigenschappen en conditionele onafhankelijkheid.

Oorspronkelijke auteurs: Satoshi Kura, Katsuyuki Takashima

Gepubliceerd 2026-05-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Satoshi Kura, Katsuyuki Takashima

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 probeert een geheim recept veilig te houden in een drukke, lawaaierige keuken. In de wereld van cryptografie is dit "geheime recept" een privésleutel, en de "ruis" is een side-channel-aanval. Aanvallers proberen niet de wiskunde te kraken; ze proberen te gluren naar de "lekken" (zoals energieverbruik of timing) terwijl de computer getallen berekent om je geheim te raden.

Om dit te voorkomen, gebruiken cryptografen een techniek die Masking heet. Denk aan masking als het verscheuren van je geheime recept in $t+1$ stukken papier (aandelen). Je geeft elk stuk aan een van de $t+1$ verschillende koks. Zolang een afluisteraar slechts $t$ stukken (of minder) kan bespieden, ziet hij niets anders dan willekeurige onzin. Hij kan het recept niet reconstrueren omdat hem minstens één cruciaal stuk ontbreekt.

Echter, bewijzen dat een complex recept (algoritme) echt veilig is, is ongelooflijk moeilijk. Als je het handmatig controleert, kun je een klein lek missen, en dan faalt het hele beveiligingssysteem. Hier komt het artikel om de hoek kijken.

Het Probleem: Het controleren van het "Lek"

De auteurs willen een formeel bewijs (een wiskundige garantie) opbouwen dat een gemaskeerd algoritme veilig is. Traditioneel gebeurt dit met behulp van het concept van een "Simulator".

Het idee van de Simulator: Stel je een magische doos (de simulator) voor die probeert precies na te bootsen wat de afluisteraar ziet. Als de magische doos exact hetzelfde "lek" kan creëren met alleen openbare informatie (zoals de ingrediëntenlijst) en zonder ooit de stukken van het geheime recept te hebben gezien, dan is het echte algoritme veilig. De afluisteraar leert niets nieuws.

Maar het handmatig bouwen van deze simulators is foutgevoelig. De auteurs wilden een betere manier om dit te bewijzen.

De Oplossing: Een Nieuw Logisch Hulpmiddel (Lilac)

De auteurs introduceren een verbinding tussen "Simulators" en een concept dat Conditionele Onafhankelijkheid heet.

De Analogie: Stel je voor dat je probeert de verjaardag van een vriend te raden (het geheim).
- Scenario A: Je weet hun leeftijd en de maand waarin ze geboren zijn (Openbare Info).
- Scenario B: Je weet ook hun geheime dagboekaantekening (Geheime Info).
- Conditionele Onafhankelijkheid: Als het weten van de dagboekaantekening je gok over de verjaardag niet verandert zodra je de leeftijd en maand al weet, dan is het dagboek "conditioneel onafhankelijk" van de verjaardag, gegeven de leeftijd/maand.

Het artikel bewijst dat als er een simulator bestaat, het geheim conditioneel onafhankelijk is van het lek, gegeven de openbare info.

Om dit wiskundig te controleren, gebruiken ze een hulpmiddel dat Lilac heet.

Wat is Lilac? Denk aan Lilac als een zeer strenge, superkrachtige regelboek voor waarschijnlijkheid. Het is als een logicspel waarbij je moet bewijzen dat twee stapels kaarten (willekeurige variabelen) onafhankelijk van elkaar zijn geschud.
De "Separating Conjunction": In dit regelboek is er een speciaal symbool (zoals een toverstaf) dat zegt: "Deze twee stapels kaarten zijn volledig gescheiden en beïnvloeden elkaar niet."
De Innovatie: De auteurs hebben nieuwe regels toegevoegd aan dit regelboek om "Conditionering" (het "gegeven dat..."-deel) te behandelen. Dit stelt hen in staat om te bewijzen dat zelfs als de afluisteraar bepaalde data ziet, dit het geheim niet onthult omdat ze al de openbare data hebben.

Wat Ze Eigenlijk Hebben Gedaan

De auteurs hebben niet alleen over theorie gesproken; ze hebben een systeem gebouwd om echte cryptografische algoritmen te verifiëren met behulp van deze nieuwe logica. Ze hebben hun methode toegepast op drie specifieke "gadgets" (bouwstenen) die worden gebruikt in moderne encryptie:

MINIADDREPNOISE: Een hulpmiddel dat willekeurige ruis toevoegt aan data (zoals het toevoegen van zout aan soep om de oorspronkelijke smaak te verbergen). Ze bewezen dat zelfs als een aanvaller een glimp opvangt van een deel van de gezoute soep, hij de oorspronkelijke smaak niet kan achterhalen.
REFRESH: Een hulpmiddel dat de verschenen stukken van het geheim opnieuw schudt zodat ze er gloednieuw uitzien, waardoor aanvallers ze niet in de tijd kunnen volgen. Ze bewezen dat dit opnieuw schudden veilig is.
SECMULT (Veilige Vermenigvuldiging): Een hulpmiddel dat twee geheime getallen met elkaar vermenigvuldigt zonder het resultaat te onthullen tot het allerlaatste moment. Dit is een van de moeilijkste bewerkingen om veilig te stellen. Ze bewezen dat deze vermenigvuldiging veilig is tegen "t-probing"-aanvallen.

De Conclusie

Het artikel stelt dat door het complexe idee van "Simulators" te vertalen naar de taal van "Conditionele Onafhankelijkheid", ze het Lilac-logicasysteem kunnen gebruiken om automatisch en rigoureus te verifiëren dat deze cryptografische hulpmiddelen veilig zijn.

Ze hebben dit succesvol aangetoond door formele bewijzen te schrijven voor MINIADDREPNOISE, REFRESH en SECMULT, en zo te laten zien dat deze specifieke algoritmen voldoen aan de strenge beveiligingseisen die nodig zijn om geheimen te beschermen tegen side-channel-aanvallen. Ze hebben niet beweerd alle toekomstige beveiligingsproblemen op te lossen of dit toe te passen op medische apparatuur; hun werk gaat strikt over het bewijzen van de veiligheid van deze specifieke cryptografische wiskundige bewerkingen met behulp van een nieuw logisch raamwerk.

Technische Samenvatting: Formele Verificatie van Probing Security via Conditionele Onafhankelijkheid

Probleemstelling

Kantoorbijkantooraanvallen vormen een aanzienlijke bedreiging voor de veiligheid van cryptografische schema's, wat heeft geleid tot de wijdverbreide invoering van maskering als tegenmaatregel. Maskering splitst geheime waarden in delen (shares) om ervoor te zorgen dat lekkage uit een willekeurige subset van tussentijdse waarden het onderliggende geheim niet onthult. Het bewijzen van de veiligheid van gemaskerde algoritmen, met name onder het ISW-probing-model (waarbij een adversary maximaal $t$ tussentijdse waarden kan afzoeken), is echter berucht voor foutgevoeligheid bij handmatige uitvoering. Verschillende gebreken zijn geïdentificeerd in handmatige veiligheidsbewijzen, wat formele verificatie noodzakelijk maakt.

Hoewel probabilistische separatielogica succesvol is toegepast om eigenschappen zoals inputonafhankelijkheid te verifiëren (bijvoorbeeld bij eenmalige pads), is deze nog niet gebruikt om probing security (specifiek $t$ -noninterferentie) van gemaskerde algoritmen te verifiëren. Bestaande formele verificatietools vertrouwen vaak op substitutiegebaseerde methoden of typeinferentie, die mogelijk de modulariteit of expressiviteit missen die vereist is voor complexe conditionele onafhankelijkheidsredenering die inherent is aan maskering.

Methodologie

Dit werk stelt een nieuwe aanpak voor formele verificatie voor door een rigoureuze verbinding te leggen tussen op simulatoren gebaseerde veiligheidsdefinities en conditionele onafhankelijkheid. De methodologie steunt op Lilac, een probabilistische separatielogica die is ontworpen om te redeneren over conditionele onafhankelijkheid.

1. Theoretische Grondslag: Simulatoren en Conditionele Onafhankelijkheid

De auteurs herformuleren de standaard op simulatoren gebaseerde definitie van noninterferentie in termen van conditionele onafhankelijkheid.

Op simulatoren gebaseerd perspectief: Een gemaskerd algoritme is veilig als, voor elke set afgezochte waarden $O$ (geobserveerd door een adversary), er een simulator bestaat die de verdeling van $O$ kan genereren met behulp van slechts een subset van inputdelen $I$ , zonder toegang tot de resterende geheime delen.
Conditioneel onafhankelijk perspectief: Deze veiligheidseis is equivalent aan de stelling dat de geobserveerde waarden $O$ conditioneel onafhankelijk zijn van de geheime inputdelen ( $\Delta \setminus I$ ), gegeven de publieke inputdelen $I$ . Formeel wordt dit uitgedrukt als $O \perp (\Delta \setminus I) \mid I$ .

Het artikel toont aan dat deze equivalentie geldt binnen het semantische kader van Lilac, dat probabilistische onafhankelijkheid modelleert met behulp van onafhankelijke combinaties van kansruimten en conditionering via disintegratie.

2. Uitbreiding van Lilac

Om Lilac toe te passen op probing security, breiden de auteurs de logica uit met specifieke bewijsregels die niet aanwezig waren in de oorspronkelijke Lilac-formulering:

Semi-Graphoid Axioma's: Het artikel bewijst dat de semi-graphoid axioma's voor conditionele onafhankelijkheid (Symmetrie, Decompositie, Zwakke Unie en Contractie) gelden binnen de semantiek van Lilac. Deze axioma's zijn cruciaal voor het manipuleren van conditionele onafhankelijkheidsstellingen tijdens bewijzen.
Composabiliteitsregels: Er worden nieuwe regels geïntroduceerd om de compositie van noninterferentie-eigenschappen te behandelen, specifiek voor sequentiële compositie en for-lussen. Deze regels maken modulaire verificatie mogelijk van complexe algoritmen die zijn opgebouwd uit kleinere onderdelen (gadgets).
Bezit en Verzwakking: Aanvullende regels faciliteren redenering over het bezit van random variabelen en de verzwakking van noninterferentie-eigenschappen bij het omgaan met ongedeelde inputs of subsets van variabelen.

3. Verificatiekader

Het verificatieproces omvat:

Het vertalen van gemaskerde algoritmen (geschreven in de probabilistische programmeertaal APPL) naar Hoare-triplets binnen Lilac.
Het gebruik van de gevestigde equivalentie (Stelling V.1) om de verificatie van $(I, O)$ -noninterferentie te reduceren tot het bewijzen van een specifiek conditioneel onafhankelijk Hoare-triplet:
$\{ \text{own } \Delta \} \ M \ \{ Y. \ C_{x \leftarrow I}(\text{own}(\Delta \setminus I) * \text{own } O) \}$
Het toepassen van de uitgebreide set bewijsregels (inclusief de nieuwe semi-graphoid- en composabiliteitsregels) om de vereiste gevolgtrekkingen af te leiden.

Belangrijkste Bijdragen

Formele Connectie: Het artikel vestigt een formele equivalentie tussen op simulatoren gebaseerde definities van probing security en conditionele onafhankelijkheidseigenschappen die in Lilac uitdrukbaar zijn. Dit overbrugt de kloof tussen cryptografische veiligheidsnoties en probabilistische separatielogica.
Uitbreiding van Lilac: De auteurs bieden een suite aanvullende bewijsregels die noodzakelijk zijn voor het verifiëren van gemaskerde algoritmen, inclusief de semi-graphoid axioma's voor conditionele onafhankelijkheid en composabiliteitsregels voor sequentiële compositie en lussen.
Casestudies: De effectiviteit van de aanpak wordt aangetoond door de formele verificatie van de probing security van drie kritieke algoritmen met behulp van Lilac:
- MINIADDREPNOISE: Een subrutine voor het toevoegen van uniforme ruis aan gemaskerde waarden.
- REFRESH: Een fundamenteel algoritme voor het vernieuwen van delen om lekkageaccumulatie te voorkomen.
- SECMULT: Een standaard gemaskerd vermenigvuldigingsalgoritme.
- ADDREPNOISEER: Een variant die wordt gebruikt in het Raccoon-handtekeningsschema (een kandidaat voor de NIST-post-kwantumcryptografie-standaardisatie), waarbij wordt bewezen dat het voldoet aan de eigenschap $t$ -Strong Noninterference met Ongedeelde Input ( $t$ -SNIU).

Resultaten

Het artikel leidt succesvol Hoare-triplets af voor de doelalgoritmen, waarmee hun noninterferentie-eigenschappen worden bevestigd.

Voor MINIADDREPNOISE toont het bewijs aan dat de outputdelen conditioneel onafhankelijk zijn van de niet-geobserveerde inputdelen, gegeven de geobserveerde inputs.
Voor REFRESH verifieert het bewijs dat het algoritme voldoet aan $t$ -Strong Noninterference ( $t$ -SNI), een sterkere eigenschap dan standaard noninterferentie, die essentieel is voor composabiliteit bij masking van hogere orde.
Voor SECMULT en ADDREPNOISEER maken de bewijzen gebruik van de nieuwe composabiliteitsregels om de geneste lussen en complexe data-afhankelijkheden aan te pakken die inherent zijn aan deze algoritmen.

De verificatie van ADDREPNOISEER is bijzonder significant, aangezien deze een sleutelcomponent valideert van het veiligheidsbewijs van het Raccoon-handtekeningsschema, dat rust op de $t$ -SNIU-eigenschap.

Betekenis en Claims

De auteurs claimen dat dit werk de eerste toepassing biedt van probabilistische separatielogica (specifiek Lilac) op de formele verificatie van probing security voor gemaskerde algoritmen. Door veiligheidsbewijzen te vertalen naar conditionele onafhankelijkheidsredenering, biedt de aanpak een modulair en logisch rigoureus alternatief voor bestaande substitutiegebaseerde of type-inferentietools.

Het artikel benadrukt dat hoewel het onderliggende idee van het verbinden van simulatoren met conditionele onafhankelijkheid conceptueel eenvoudig is, de formalisatie ervan in Lilac technisch niet triviaal is vanwege de afhankelijkheid van de logica van onafhankelijke combinaties in plaats van standaard product-kansruimten. De succesvolle afleiding van de hoofdstelling en de toepassing op cryptografische componenten uit de praktijk (Raccoon) tonen aan dat dit kader levensvatbaar is voor het verifiëren van complexe masking-schema's van hogere orde.

Het werk blijft bescheiden wat betreft de omvang, met de opmerking dat de huidige resultaten beperkt zijn tot de informatietheoretische setting van probing security. De auteurs identificeren het uitbreiden van de aanpak naar de computational setting en het implementeren van de methode in een interactieve theoremaprover als belangrijke richtingen voor toekomstig werk. Zij suggereren ook dat het kader kan worden toegepast op andere op simulatoren gebaseerde veiligheidseigenschappen, zoals die gevonden in veilige multi-party berekening.