Niezaprzeczalny podpis

Podpis niezaprzeczalny to schemat podpisu cyfrowego , który pozwala sygnatariuszowi na wybranie, komu pozwoli weryfikować podpisy. Schemat dodaje wyraźne odrzucenie podpisu, uniemożliwiając sygnatariuszowi późniejszą odmowę weryfikacji podpisu przez pominięcie; sytuacji, która zdewaluowałaby podpis w oczach weryfikatora. Został wynaleziony przez Davida Chauma i Hansa van Antwerpena w 1989 roku.

Przegląd

W tym schemacie sygnatariusz posiadający klucz prywatny może opublikować podpis wiadomości. Jednak podpis niczego nie ujawnia odbiorcy/weryfikatorowi wiadomości i podpisu bez udziału w jednym z dwóch interaktywnych protokołów:

Protokół potwierdzenia, który potwierdza, że kandydat jest ważnym podpisem wiadomości wystawionym przez sygnatariusza, identyfikowanego przez klucz publiczny.
Protokół dezawuowania, który potwierdza, że kandydat nie jest ważnym podpisem wiadomości wystawionej przez sygnatariusza.

Motywacją dla schematu jest umożliwienie podpisującemu wyboru, komu podpisy będą weryfikowane. Jednakże odmowa wzięcia udziału w weryfikacji przez sygnatariusza może w późniejszym czasie twierdzić, że podpis jest nieważny, co obniżyłoby wartość podpisów dla weryfikatorów. wiarygodną zaprzeczenie osoby podpisującej .

Ważne jest, aby wymiany potwierdzenia i wyrzeczenia się nie były zbywalne. Osiągają to poprzez posiadanie właściwości wiedzy zerowej; obie strony mogą tworzyć transkrypcje zarówno potwierdzenia, jak i odrzucenia, które są nie do odróżnienia przez stronę trzecią od prawidłowych wymian.

Schemat podpisu wyznaczonego weryfikatora ulepsza podpisy, których można odmówić, umożliwiając, dla każdego podpisu, przeniesienie interaktywnej części schematu na inną stronę, wyznaczonego weryfikatora, zmniejszając obciążenie sygnatariusza.

Protokół o zerowej wiedzy

Następujący protokół został zaproponowany przez Davida Chauma .

Wybrano grupę G , w której problem logarytmu dyskretnego jest nierozwiązywalny i wszystkie operacje w schemacie odbywają się w tej grupie. Zwykle będzie to skończona grupa cykliczna rzędu p zawarta w Z / nZ , przy czym p jest dużą liczbą pierwszą ; ta grupa jest wyposażona w operację grupową mnożenia liczb całkowitych modulo n . Dowolny prymitywny element (lub generator), g , z G jest wybrany; obliczone potęgi g następnie łączą przestrzeganie ustalonych aksjomatów.

Alicja generuje parę kluczy, losowo wybiera klucz prywatny x , a następnie wyprowadza i publikuje klucz publiczny y = g ^x .

Podpisywanie wiadomości

Alicja podpisuje wiadomość, m , obliczając i publikując podpis, z = m ^x .

Protokół bierzmowania (tj. wyznania).

Bob chce zweryfikować podpis, z , m przez Alicję pod kluczem, y .

Bob wybiera dwie losowe liczby: a i b i używa ich do zaślepienia wiadomości, wysyłając do Alicji:
c = m ^a g ^b .
Alicja wybiera losową liczbę q , używa jej do oślepienia c , a następnie podpisuje ją swoim kluczem prywatnym x , wysyłając do Boba:

s ₁ = cg ^q i

s ₂ = s ₁^x .

Zauważ, że
s ₁^x = (cg ^q ) ^x = (m ^a g ^b ) ^x g ^qx = (m ^x ) ^a (g ^x ) ^b+q = z ^za y ^b+q .
Bob ujawnia a i b .
Alicja sprawdza, czy aib są prawidłowymi wartościami ślepymi, a jeśli tak, ujawnia q . Odsłonięcie tych blindów powoduje, że wymiana wiedzy jest zerowa.
Bob weryfikuje s ₁ = cg ^q , udowadniając, że q nie zostało wybrane nieuczciwie, oraz
s ₂ = z ^a y ^b+q ,
udowadniając, że z jest prawidłowym podpisem złożonym kluczem Alicji. Zauważ, że
z ^za y ^b+q = (m ^x ) ^za (g ^x ) ^b+q .

Alicja może oszukiwać w kroku 2, próbując losowo odgadnąć s ₂ .

Protokół zrzeczenia się

Alicja chce przekonać Boba, że z nie jest prawidłowym podpisem m pod kluczem, g ^x ; tj. z ≠ m ^x . Alicja i Bob uzgodnili liczbę całkowitą k , która określa obciążenie obliczeniowe Alicji i prawdopodobieństwo, że przypadkowo odniesie sukces.

Bob wybiera losowe wartości, s ∈ {0, 1, ..., k} i a , i wysyła:

v ₁ = m ^s g ^a i

v ₂ = z ^s y ^a ,

gdzie potęgowanie przez a służy do zaślepienia wysyłanych wartości. Zauważ, że
v ₂ = z ^s y ^za = (m ^x ) ^s (g ^x ) ^za = v ₁^x .
Alicja, używając swojego klucza prywatnego, oblicza v ₁^x , a następnie iloraz,
v ₁^x v ₂⁻¹ = (m ^s g ^a ) ^x (z ^s g ^xa ) ⁻¹ = m ^sx z ^−s = (m ^x z ⁻¹ ) ^s .
Zatem v ₁^x v ₂⁻¹ = 1, chyba że z ≠ m ^x .
Alicja testuje następnie v ₁^x v ₂⁻¹ pod kątem równości z wartościami:
(m ^x z ⁻¹ ) ⁱ dla i ∈ {0, 1, …, k} ;
które są obliczane przez wielokrotne mnożenie m ^x z ⁻¹ (zamiast potęgowania dla każdego i ). Jeśli test się powiedzie, Alicja przypuszcza, że odpowiednie i to s ; w przeciwnym razie przypuszcza wartość losową. gdzie z = mx ^_ , (m ^x z ⁻¹ ) ⁱ = v ₁^x v ₂⁻¹ = 1 dla wszystkich ja , s jest nieodwracalne.
Alicja zobowiązuje się do i : wybiera losowe r i wysyła hash(r, i) do Boba.
Bob ujawnia .
Alicja potwierdza, że a jest prawidłową ślepą (tj. można wygenerować v ₁ i v _{2 ), a jeśli tak, ujawnia} r . Odsłonięcie tych blindów powoduje, że wymiana wiedzy jest zerowa.
Bob sprawdza hash(r, i) = hash(r, s) , udowadniając, że Alicja zna s , stąd z ≠ m ^x .

Jeśli Alicja spróbuje oszukać w kroku 3, zgadując losowo s , prawdopodobieństwo powodzenia wynosi 1/(k + 1) . Tak więc, jeśli k = 1023 i protokół przeprowadza się dziesięć razy, jej szanse wynoszą od 1 do 2 ¹⁰⁰ .

Zobacz też