Problem med att hitta klo

Problemet att hitta klo är ett klassiskt problem inom komplexitetsteorin , med flera tillämpningar inom kryptografi . Kort sagt, givet två funktioner f , g , betraktade som orakel , är problemet att hitta x och y som f ( x ) = g ( y ). Paret ( x , y ) kallas då en klo . Vissa problem, särskilt inom kryptografi, löses bäst när de ses som ett problem att hitta klös, därför ger alla algoritmiska förbättringar för att lösa problemet att hitta klös en bättre attack mot kryptografiska primitiver som hashfunktioner .

Definition

Låt $A,B,C$ vara ändliga mängder, och $f:A\to C$ , $g:B\to C$ två funktioner. Ett par $(x,y)\in A\times B$ kallas en klo om $f(x)=g( y)$ . Problemet att hitta en klo definieras som att hitta en sådan klo, givet att en sådan finns.

Om vi ​​ser $f,g$ som slumpmässiga funktioner, förväntar vi oss att det finns en klo om $|A|\cdot |B|\geq |C|$ . Mer exakt, det finns exakt $|A|\cdot |B|$ par av formen $(x,y)$ med $x\in A,y\in B$ ; sannolikheten att ett sådant par är en klo är $1/|C|$ . Så om $|A|\cdot |B|\geq |C|$ , det förväntade antalet klor är minst 1.

Algoritmer

Om klassiska datorer används liknar den bästa algoritmen en Meet-in-the-middle-attack, som först beskrevs av Diffie och Hellman . Algoritmen fungerar enligt följande: anta $|A|\leq |B|$ . För varje $x\in A$ sparar du paret $(f(x),x)$ i en hashtabell indexerad med $f(x)$ . Sedan, för varje $y\in B$ , slå upp tabellen vid $g(y)$ . Om ett sådant index finns, hittade vi en klo. Detta tillvägagångssätt tar tid $O(|A|+|B|)$ och minne $O(|A|)$ .

Om kvantdatorer används, visade Seiichiro Tani att en klo kan hittas i komplexitet ${\sqrt[{3}]{|A|\cdot |B|}}$ .

Shengyu Zhang visade att asymptotiskt är dessa algoritmer de mest effektiva möjliga.

Ansökningar

Som nämnts visas de flesta tillämpningar av problemet med att hitta klo i kryptografi . Exempel inkluderar:

• Kollisionsfynd på kryptografiska hashfunktioner .
• Meet-in-the-midten-attacker : med denna teknik kan k bitar av runda nycklar hittas i tiden ungefär 2 ^k/2+1 . Här f kryptering halvvägs och g dekrypterar halvvägs. Det är därför Triple DES tillämpar DES tre gånger och inte bara två.