Kryptografia oparta na parowaniu

Kryptografia oparta na parowaniu polega na łączeniu w pary elementów dwóch grup kryptograficznych z trzecią grupą z mapowaniem mi $\ Displaystyle e: G_ {1} \ razy G_ {2} \ do G_{T}}$ do konstruowania lub analizowania systemów kryptograficznych .

Definicja

Następująca definicja jest powszechnie stosowana w większości artykułów naukowych.

Niech ${\ Displaystyle F_ {q}}$ będzie polem skończonym nad liczbą pierwszą ${\ Displaystyle q}$ , ${\ Displaystyle G_ {1}, G_ {2}}$ dwie addytywne grupy cykliczne rzędu pierwszego ${\ Displaystyle q}$ $i$ $grupa$ cykliczna q multiplikatywnie. Parowanie to mapa: ${\ Displaystyle e: G_ {1} \ razy G_ {2} \ rightarrow G_ {T}}$ , który spełnia następujące właściwości:

Dwuliniowość: ${\ Displaystyle \ dla wszystkich a, b \ w F_ {$
Non -degeneracja: ${\ displaystyle e \ neq 1}$
Obliczalność: Istnieje skuteczny algorytm do obliczania mi $\ displaystyle e}$ .

Klasyfikacja

$grupa$ używana dla pierwszych dwóch grup (tj. parowanie nazywa się i jest odwzorowaniem dwóch elementów z jednej grupy na pierwiastek z drugiej grupy.

Niektórzy badacze klasyfikują instancje parowania na trzy (lub więcej) podstawowe typy:

${\ Displaystyle G_ {1} = G_ {2}}$ ;
${\ Displaystyle G_ {1} \ neq G_ {2}}$ , ale istnieje efektywnie obliczalny homomorfizm ${\ Displaystyle \ phi: G_ {2} \ do G_ {1}}$ ;
$}$ ${\ Displaystyle G_ {2}}$ i nie ma wydajnie obliczalnych homomorfizmów między i ${\ Displaystyle G_ {1}}$ sol .

Zastosowanie w kryptografii

Jeśli są symetryczne, można użyć parowania, aby zredukować trudny problem w jednej grupie do innego, zwykle łatwiejszego problemu w innej grupie.

Na przykład w grupach wyposażonych w mapowanie dwuliniowe , takie jak parowanie Weila lub parowanie Tate'a , uważa się, że uogólnienia obliczeniowego problemu Diffiego-Hellmana są niewykonalne, podczas gdy prostszy decyzyjny problem Diffiego-Hellmana można łatwo rozwiązać za pomocą funkcji parowania. Pierwsza grupa jest czasami określana jako grupa luk ze względu na zakładaną różnicę trudności między tymi dwoma problemami w grupie.

Podczas gdy po raz pierwszy użyto ich do kryptoanalizy , parowania zostały również wykorzystane do skonstruowania wielu systemów kryptograficznych, dla których nie jest znana żadna inna wydajna implementacja, takich jak szyfrowanie oparte na tożsamości lub schematy szyfrowania oparte na atrybutach .

Kryptografia oparta na parowaniu jest używana w schemacie zobowiązań kryptograficznych KZG .

Współczesnym przykładem zastosowania parowania dwuliniowego jest schemat podpisu cyfrowego BLS .

Kryptografia oparta na parowaniu opiera się na założeniach twardości innych niż np. kryptografia krzywych eliptycznych , która jest starsza i była badana przez dłuższy czas.

Kryptoanaliza

W czerwcu 2012 r. National Institute of Information and Communications Technology (NICT), Kyushu University i Fujitsu Laboratories Limited poprawiły poprzednią granicę pomyślnego obliczania logarytmu dyskretnego na supersingularnej krzywej eliptycznej z 676 bitów do 923 bitów.

W 2016 roku algorytm Extended Tower Number Field Sieve pozwolił zmniejszyć złożoność znajdowania logarytmu dyskretnego w niektórych wynikowych grupach par. W związku z tym poziom bezpieczeństwa niektórych przyjaznych parowaniu krzywych eliptycznych został później obniżony.

Linki zewnętrzne