Computational Diffie–Hellman antagande

Det beräkningsmässiga Diffie–Hellman (CDH) antagandet är ett beräkningshårdhetsantagande om Diffie–Hellman-problemet . CDH-antagandet involverar problemet med att beräkna den diskreta logaritmen i cykliska grupper . CDH-problemet illustrerar attacken av en avlyssnare i Diffie–Hellmans nyckelutbytesprotokoll för att erhålla den utbytta hemliga nyckeln.

Definition

Betrakta en cyklisk grupp G av ordningen q . CDH-antagandet säger att givet

$(g,g^{a},g^{b})\,$

för en slumpmässigt vald generator g och slumpmässig

$a,b\in \{0,\ldots ,q-1\},\,$

det är beräkningsmässigt svårlöst att beräkna värdet

$g^{ab}.\,$

Relation till diskreta logaritmer

CDH-antagandet är starkt relaterat till det diskreta logaritm-antagandet . Om det var lätt att beräkna den diskreta logaritmen (bas g ) i G , skulle CDH-problemet lätt kunna lösas:

Given

$(g,g^{a},g^{b}),\,$

man skulle effektivt kunna beräkna $g^{ab}$ på följande sätt:

• beräkna $a$ genom att ta den diskreta loggen av $g^{a}$ till basen $g$ ;
• beräkna $g^{ab}$ genom exponentiering: $g^{ab}=(g^{b})^{a}$ ;

Att beräkna den diskreta logaritmen är den enda kända metoden för att lösa CDH-problemet. Men det finns inga bevis för att det faktiskt är den enda metoden. Det är ett öppet problem att avgöra om det diskreta log-antagandet är ekvivalent med CDH-antagandet, även om detta i vissa speciella fall kan visas vara fallet.

Relation till Decision Diffie–Hellman Assumption

CDH-antagandet är ett svagare antagande än Decision Diffie–Hellman-antagandet (DDH-antagandet). Om det var enkelt att beräkna $g^{ab}$ från ${\displaystyle (g,g^{a},g^{b})} (CDH-problem),$ då skulle man kunna lösa DDH-problemet trivialt.

Många kryptografiska scheman som är konstruerade från CDH-problemet förlitar sig i själva verket på hårdheten hos DDH-problemet. Den semantiska säkerheten för Diffie-Hellman Key Exchange samt säkerheten för ElGamal-krypteringen är beroende av hårdheten hos DDH-problemet.

Det finns konkreta konstruktioner av grupper där det starkare DDH-antagandet inte håller men det svagare CDH-antagandet verkar fortfarande vara en rimlig hypotes.

Variationer av Computational Diffie–Hellman-antagandet

Följande varianter av CDH-problemet har studerats och visat sig vara likvärdiga med CDH-problemet:

• Square computational Diffie-Hellman problem (SCDH): På ingång $g,g^{x}$ , beräkna $g^{x^{2}}$ ;
• Inverst beräknings-Diffie-Hellman-problem (InvCDH): På ingång $g,g^{x}$ , beräkna $g^{x^{-1}}$ ;
• Delbar beräkning Diffie-Hellman-problem (DCDH): På ingång $g,g^{x},g^{y}$ , beräkna $g^{y/ x}$ ;

Variationer av Computational Diffie–Hellman-antagandet i produktgrupper

Låt $G_{1}$ och $G_{2}$ vara två cykliska grupper.

• Co-Computational Diffie–Hellman (co-CDH) problem: Givet $g,g^{a}\in G_{1}$ och $h\in G_ {2}$ , beräkna $h^{a}\in G_{2}$ ;