Technische Samenvatting: Niet-adaptieve cryptanalytische tijd-ruimte ondergrenzen via een Shearer-achtige ongelijkheid voor permutaties

1. Probleemstelling en Motivatie

Dit artikel onderzoekt de kracht van adaptiviteit in cryptanalytische tijd-ruimte afwegingen binnen het voorverwerkingsmodel (niet-uniform). In dit model bestaat een aanvaller uit een voorverwerkingsfase die een adviesstring van $S$ bits genereert op basis van het probleeminstance, gevolgd door een online-fase die specifieke uitdagingen oplost met behulp van $T$ oracle-aanvragen en de adviesstring.

Hoewel veel state-of-the-art cryptanalytische algoritmen (bijvoorbeeld Pollard's Rho voor Discrete Logaritme, adaptieve aanvallen op Even-Mansour) sterk vertrouwen op adaptiviteit – waarbij aanvragen afhankelijk zijn van eerdere oracle-antwoorden – was het onduidelijk of niet-adaptieve algoritmen (waarbij aanvragen van tevoren vastliggen, mogelijk afhankelijk van slechts het advies) vergelijkbare efficiëntie konden bereiken. Eerdere ondergrenstechnieken voor deze problemen waren over het algemeen niet in staat om onderscheid te maken tussen adaptieve en niet-adaptieve algoritmen, en leverden vaak grenzen op die te zwak waren om aan te tonen dat adaptiviteit een significant voordeel biedt.

De auteurs behandelen de vraag die door Corrigan-Gibbs en Kogan [CK19] werd gesteld: Wat is de kracht van adaptiviteit in niet-uniforme cryptanalytische algoritmen? Specifiek streven ze ernaar scherpe ondergrenzen te bewijzen die aantonen dat niet-adaptieve algoritmen in de voorverwerkingsinstelling voor fundamentele cryptografische problemen de efficiëntie van adaptieve algoritmen niet kunnen evenaren.

2. Methodologie en Technisch Kader

2.1 Het Permutatie Uitdaging (PC) Model

Om de analyse van diverse problemen (Discrete Logaritme, DDH, sqDDH en Even-Mansour sleutelherstel) te verenigen, introduceren de auteurs het Permutatie Uitdaging (PC) model.

• Structuur: Het model omvat een "inwendige permutatie" $\sigma: [N] \to [N]$ en een geheim $d$.
• Aanvragen: De aanvaller doet twee soorten aanvragen:
  1. Inwendige aanvragen: Directe toegang tot $\sigma$ (of $\sigma^{-1}$).
  2. Uitwendige aanvragen: Toegang tot een "uitwendige functie" gedefinieerd door een translatiefunctie $tr(d, m)$ en een nabewerkingsfunctie $post(d, \cdot)$. De aanvraag $m$ wordt via $tr$ vertaald naar een invoer voor $\sigma$, en de uitvoer wordt nabewerkt.
• Definitie van Niet-Adaptiviteit: Een algoritme is niet-adaptief als zijn voor-vertaalde aanvragen (de $m$-waarden en inwendige aanvraagindices) van tevoren vastliggen op basis van de adviesstring $z$, maar niet op basis van de specifieke uitdaging $d$ of de uitvoer van $\sigma$. Cruciaal is dat de werkelijke oracle-aanvragen aan $\sigma$ afhankelijk kunnen zijn van $d$ vanwege de translatiefunctie, waardoor het model klassieke niet-adaptieve algoritmen zoals Baby-Step Giant-Step kan vastleggen.

2.2 Informatietheoretische Hulpmiddelen

De kern van het bewijs steunt op informatietheoretische hulpmiddelen die worden toegepast op verdelingen over de ruimte van permutaties $S_N$, in plaats van productruimten.

• Shearer's Lemma voor Permutaties: De auteurs maken gebruik van een variant van Shearer's lemma voor willekeurige bjecties (afgeleid van Barthe et al. [BCELM11] en Caputo en Salez [CS24]). Deze ongelijkheid relateert de Kullback-Leibler (KL)-divergentie van een verdeling over permutaties aan de KL-divergenties van zijn marginaalverdelingen op deelverzamelingen van indices.
• Concentratieongelijkheden voor Read-$k$ Families: Zij leiden een concentratiegrens af voor families van functies over permutaties waarbij elke functie afhankelijk is van een "read-$k$" verzameling variabelen (elke coördinaat wordt door ten hoogste $k$ functies geraadpleegd). Dit breidt het resultaat van Gavinsky et al. [GLSS15] uit van productruimten naar de ruimte van bjecties.
• Uniformiteit van Translatie: Een belangrijke technische voorwaarde is dat de translatiefunctie $tr$**$u$-uniform** moet zijn. Dit betekent dat voor elke vaste uitwendige aanvraag de resulterende invoer voor de permutatie bijna uniform over $[N]$ verdeeld is wanneer het geheim $d$ uniform wordt gekozen.

2.3 Bewijsstrategie

De hoofdstelling (Stelling 4.1) begrenst de succeskans van een niet-adaptieve voorverwerkingsaanvaller door deze te relateren aan de succeskans van een niet-voorverwerkende aanvaller.

1. Hybride Argument: Het bewijs introduceert een "middenspel" waarbij de aanvaller een beperkt aantal permutatiewaarden kan vastleggen (simulatie van inwendige aanvragen), maar de rest uniform wordt bemonsterd.
2. KL-Divergentie Analyse: Door te conditioneren op de adviesstring analyseren de auteurs de KL-divergentie tussen de verdeling van de permutatie in de voorverwerkingsinstelling versus de uniforme verdeling.
3. Toepassing van Shearer-achtige Grenzen: Met behulp van de $u$-uniformiteit van de translatiefunctie tonen ze aan dat de verzameling vertaalde uitwendige aanvragen een read-$k$ familie vormt. De concentrieongelijkheid (Stelling 1.9) begrenst vervolgens het voordeel dat wordt behaald uit de adviesstring, en toont aan dat tenzij de adviesstring groot genoeg is ($S \gg \sqrt{N}$), de succeskans niet significant kan overschrijden die van een niet-voorverwerkend algoritme.

3. Belangrijkste Bijdragen en Resultaten

Het artikel stelt scherpe ondergrenzen vast die aantonen dat adaptiviteit een significant voordeel biedt in het voorverwerkingsmodel voor verschillende cryptografische problemen.

3.1 Discrete Logaritme (DLOG)

• Resultaat: Voor een generieke groep van priemorde $N$ heeft elk niet-adaptief $(S, T)$-algoritme met voorverwerking een succeskans begrensd door:
  $$\text{Succes} \le 2 \cdot \text{Max}_{S}^{\text{DLOG}}(T) + \frac{4 \log(2) ST}{N} + \frac{T^2}{N}$$
  waarbij $\text{Max}_{S}^{\text{DLOG}}(T) \le T^2/N$ de grens is voor niet-voorverwerkende algoritmen (Shoup [Sho97]).
• Implicatie: De online-tijdcomplexiteit $T = O(\sqrt{N})$ van het niet-adaptieve Baby-Step Giant-Step algoritme kan niet worden verbeterd door voorverwerking, tenzij de adviesstringgrootte $S$ $\Omega(\sqrt{N})$ overschrijdt. Dit staat in schril contrast met adaptieve algoritmen (bijvoorbeeld Mihalcik [Mih10], Bernstein en Lange [BL13], Corrigan-Gibbs en Kogan [CK18]) die de afweging $ST^2 = \tilde{O}(N)$ bereiken, waardoor $T = O(N^{1/3})$ mogelijk is met $S = \tilde{O}(N^{1/3})$.

3.2 Decisional Diffie-Hellman (DDH) en sqDDH

• Resultaat: Vergelijkbare grenzen worden afgeleid voor DDH en sqDDH. Voor sqDDH is de grens scherp en komt overeen met een eenvoudige niet-adaptieve variant van het adaptieve algoritme. Voor DDH veronderstellen de auteurs dat de grens niet strak is en stellen ze de optimale grens voor als $1/2 + \tilde{O}(T^2/N + ST/N)$.
• Implicatie: Niet-adaptieve voorverwerking biedt niet dezelfde afwegingsverbeteringen als adaptieve voorverwerking voor deze beslissingsproblemen.

3.3 Even-Mansour (EM) Cryptosysteem

• Resultaat: Voor sleutelherstelaanvallen op de Even-Mansour cipher versnelt onbeperkte voorverwerking niet-adaptieve aanvallen niet (tenzij $S \ge \tilde{\Omega}(\sqrt{N})$).
• Implicatie: Dit staat in schril contrast met adaptieve aanvallen (bijvoorbeeld Fouque, Joux en Mavromati [FJM14]) die online complexiteit $T = \tilde{O}(2^{n/3})$ kunnen bereiken met $S = \tilde{O}(2^{n/3})$. De niet-adaptieve ondergrens bevestigt dat de geheugenreductie in adaptieve aanvallen fundamenteel berust op adaptiviteit.

4. Betekenis en Beperkingen

Betekenis

• Formele Rechtvaardiging van Adaptiviteit: Het artikel levert het eerste formele bewijs dat adaptiviteit essentieel is voor het bereiken van sub-$\sqrt{N}$ tijdcomplexiteit in DLOG en sub-$2^{n/3}$ complexiteit in Even-Mansour sleutelherstel binnen het voorverwerkingsmodel.
• Nieuw Technisch Hulpmiddel: De toepassing van een Shearer-achtige ongelijkheid voor permutaties (Stelling 1.8) in een algoritmische context is een nieuwe bijdrage. De auteurs merken op dat dit de eerste keer is dat een dergelijke variant wordt gebruikt voor ondergrensargumenten in dit domein.
• Gereinigd Model: Het Permutatie Uitdaging model abstracteert succesvol een breed scala aan zoek- en beslissingsproblemen, waardoor een collectieve analyse van hun niet-adaptieve tijd-ruimte afwegingen mogelijk is.

Beperkingen en Open Problemen

• Uitdaging-afhankelijke Aanvragen: De bewijsstrategie steunt op de onafhankelijkheid van voor-vertaalde aanvragen van de uitdaging. Het uitbreiden van deze resultaten om voor-vertaalde aanvragen toe te staan die afhankelijk zijn van de uitdaging (bijvoorbeeld $f(d + f(d))$) vereist nieuwe concentratieongelijkheden, aangezien huidige Shearer-achtige grenzen dergelijke samengestelde invoer niet effectief verwerken.
• Adaptieve Rondes: Het artikel laat het probleem open om tijd-ruimte afwegingen te karakteriseren voor adaptieve algoritmen met een specifiek aantal adaptiviteitsrondes $r$. De auteurs veronderstellen een grens van $\tilde{O}(T^2/N + rST/N)$.
• DDH Striktheid: De ondergrens voor niet-adaptieve DDH wordt verondersteld los te zijn, met de auteurs die suggereren dat de ware grens strakker zou kunnen zijn dan de bewezen grens.

Het artikel concludeert dat eerdere generieke technieken (compressieargumenten, voor-bemonstering, standaard concentratieongelijkheden) inherent beperkt zijn in het onderscheiden tussen adaptieve en niet-adaptieve algoritmen, waarbij verbetering op adaptieve grenzen maximaal polylogaritmische factoren bedraagt. De nieuwe informatietheoretische aanpak die hier wordt gepresenteerd, overwint deze barrière voor de specifieke klasse van niet-adaptieve algoritmen die worden geanalyseerd.