Obliczeniowe założenie Diffie-Hellmana

Obliczeniowe założenie Diffie-Hellmana (CDH) jest obliczeniowym założeniem twardości dotyczącym problemu Diffie-Hellmana . Z założeniem CDH wiąże się problem obliczania logarytmu dyskretnego w grupach cyklicznych . Problem CDH ilustruje atak podsłuchującego w wymiany klucza Diffiego-Hellmana w celu uzyskania wymienianego tajnego klucza.

Definicja

Rozważmy grupę cykliczną G rzędu q . Założenie CDH stwierdza, że ​​dane

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

dla losowo wybranego generatora g i random

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

obliczenie wartości jest trudne obliczeniowo

${\ displaystyle g ^ {ab}. \,}$

Związek z logarytmami dyskretnymi

Założenie CDH jest silnie związane z założeniem o logarytmie dyskretnym . Gdyby obliczenie logarytmu dyskretnego (o podstawie g ) w G było łatwe, to problem CDH można by łatwo rozwiązać:

Dany

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

można by skutecznie obliczyć w następujący sposób: $\ displaystyle g ^ {ab}}$

• obliczyć , biorąc dyskretny log z $}$${ \ displaystyle g ^ {a$ do bazy ${\ displaystyle g}$ ;
• sol ${\ Displaystyle g ^ {ab}}$ przez potęgowanie: $g ^ {b}) ^ {a}}$ ;

Obliczenie logarytmu dyskretnego jest jedyną znaną metodą rozwiązania problemu CDH. Ale nie ma dowodów na to, że w rzeczywistości jest to jedyna metoda. Otwartym problemem jest ustalenie, czy założenie logarytmu dyskretnego jest równoważne z założeniem CDH, chociaż w pewnych szczególnych przypadkach można to wykazać.

Związek z decyzyjnym założeniem Diffiego-Hellmana

Założenie CDH jest założeniem słabszym niż założenie decyzyjne Diffie-Hellmana (założenie DDH). Jeśli obliczenie z ${\ Displaystyle (g, g ^ {a}, g ^ {b})}$$)$ problem CDH) wtedy można by trywialnie rozwiązać problem DDH.

Wiele schematów kryptograficznych zbudowanych na podstawie problemu CDH opiera się w rzeczywistości na twardości problemu DDH. Bezpieczeństwo semantyczne wymiany kluczy Diffie -Hellman, jak również bezpieczeństwo szyfrowania ElGamal zależą od stopnia trudności problemu DDH.

Istnieją konkretne konstrukcje grup, w których mocniejsze założenie DDH nie jest spełnione, ale założenie słabszego CDH nadal wydaje się być rozsądną hipotezą.

Odmiany założenia Computational Diffie-Hellman

Zbadano następujące warianty problemu CDH i udowodniono, że są one równoważne z problemem CDH:

• Kwadratowy obliczeniowy problem Diffie-Hellmana (SCDH): Na wejściu ${\ displaystyle g, g ^ {x}}$ , oblicz ${\ displaystyle g ^ {x ^ {2}}}$ ;
• Odwrotny obliczeniowy problem Diffiego-Hellmana (InvCDH): Na wejściu ${\ displaystyle g, g ^ {x}}$ , oblicz ${\ displaystyle g ^ {x ^ {-1}}}$ ;
• Obliczenie podzielne Problem Diffiego-Hellmana (DCDH): Na wejściu ${\ displaystyle g, g ^ {x}, g ^ {y}}$ , oblicz ${\ displaystyle g ^ {y / x}}$ ;

Wariacje założenia Computational Diffie-Hellman w grupach produktów

Niech i ${\ Displaystyle$${1}}$ będą dwiema cyklicznymi grupami

• Co-Computational Diffie-Hellman (co-CDH) problem: Biorąc pod uwagę ${\ Displaystyle g, g ^ {a} \ w G_ {1}}$ i ${\ Displaystyle h \ w G_ {2}}$ , obliczyć ${\ Displaystyle h ^ {a} \ w G_ {2}}$ ;