Kryptografia II stopień

W11. Anonimowość i zaprzeczalność

Podpis pierścieniowy przekonuje, że podpisał ktoś ze zbioru kluczy. Podpis grupowy może mieć zarządcę i kontrolowane otwarcie tożsamości. Podpis progowy wymaga współpracy określonej liczby podmiotów. To różne funkcjonalności.

Interfejs podpisu pierścieniowego

Rozszerzamy znany interfejs podpisu, a nie zastępujemy go anonimową „czarną skrzynką”. Schemat $\Pi_{\mathrm{ring}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{RingSign},\mathsf{RingVerify})$ tworzy parametry i klucze użytkowników. Jawny pierścień jest uporządkowaną listą kluczy $L=(pk_1,\ldots,pk_n)$. Podpisujący zna tylko własny $sk_j$, zgodny z $pk_j$ na tej liście.

Indeks $j$ jest lokalnym wejściem podpisującego, nie argumentem weryfikatora. Wynik $b=1$ oznacza akceptację względem wiadomości i wskazanego pierścienia. Poprawność wymaga akceptacji uczciwego podpisu. Niepodrabialność i anonimowość są odrębnymi wymaganiami. Ich definicje ustalają m.in. dopuszczalne klucze, dostęp do podpisywania i ujawnienia sekretów. Najpierw poznamy mechanizm dowodu „znam jeden ze świadków”, a potem dokładną konstrukcję Herranza–Sáeza.

W grze anonimowości przeciwnik wskazuje dwóch uprawnionych podpisujących i wiadomość. Otrzymuje podpis jednego z nich, wybranego losowo. Trzeba określić dostęp do kluczy i losowości. Anonimowość bez ujawnień nie implikuje anonimowości po ujawnieniu losowości.

Najpierw algebra dowodu OR

OR

or. Lub, czyli alternatywa logiczna. To angielskie słowo, nie akronim. Dowód OR dotyczy spełnienia co najmniej jednej z podanych relacji.

Dowodzimy znajomości logarytmu $A_0=g^{a_0}$ lub $A_1=g^{a_1}$.

Znając $a_0$, losujemy $u_0$ i wyznaczamy $X_0=g^{u_0}$. Gałąź 1 symulujemy przez $c_1,s_1$ i $X_1=g^{s_1}\cdot A_1^{-c_1}$. Po globalnym wyzwaniu $c$ ustalamy $c_0=c-c_1$ oraz $s_0=u_0+c_0\cdot a_0$.

Weryfikator sprawdza oba równania i sumę $c_0+c_1=c$. Dla ustalonego $c$ wyzwania są jednostajne w zbiorze o tej sumie. Odpowiedzi są przesunięciami jednostajnej losowości. Rozkład transkryptu nie wskazuje rzeczywistej gałęzi. To argument dla tego protokołu i rozkładu, nie dowód każdej ring signature.

Po Fiat–Shamir globalne wyzwanie musi wiązać uporządkowany pierścień, zobowiązania i wiadomość. Rewinding przy wielu zapytaniach wymaga kontroli ich wzorca. Herranz–Sáez analizują określone konstrukcje, nie dowolne sklejenie podpisów.

Więcej gałęzi i rachunek anonimowości

Rozszerzenie dowodu OR do wielu kluczy: dla wszystkich gałęzi poza rzeczywistą losujemy $c_i,s_i$ i wyznaczamy $X_i=g^{s_i}\cdot A_i^{-c_i}$. W rzeczywistej gałęzi $j$ wysyłamy $X_j=g^u$. Po wyzwaniu globalnym ustalamy $c_j=c-\sum_{i\ne j}c_i$ i $s_j=u+a_j\cdot c_j$. Weryfikacja obejmuje każde równanie i sumę wyzwań. Podpis pierścieniowy musi dodatkowo określić kodowanie listy, dopuszczalne klucze i model bezpieczeństwa.

Pogłębienie: anonimowość przez liczenie. Dla ustalonego $c$ wektor wyzwań o sumie $c$ jest jednostajny. Każdy ma prawdopodobieństwo $q^{-(n-1)}$. Wektor odpowiedzi jest jednostajny na $\mathbb Z_q^n$, gdy rzeczywisty nonce losujemy z całego ciała. Zobowiązania są jednoznacznie wyznaczone przez klucze, wyzwania i odpowiedzi. Warunkowe prawdopodobieństwo takiego akceptującego transkryptu przy ustalonym $c$ wynosi $q^{-(2n-1)}$ niezależnie od indeksu rzeczywistej gałęzi. Jeśli liczymy także niezależne, jednostajne losowanie globalnego $c$, prawdopodobieństwo konkretnego pełnego transkryptu wynosi $q^{-2n}$. Jest to argument dla uczciwego interaktywnego wyzwania. Przeniesienie do wersji nieinteraktywnej musi uwzględnić wyrocznię i ewentualne ujawnienia.

Odbiorca a osoba trzecia

Jeśli odbiorca może sam stworzyć transkrypt o tym samym rozkładzie, pokazanie go osobie trzeciej nie dowodzi samo w sobie udziału nadawcy. Dodatkowe logi lub ujawniony stan mogą zmienić sytuację. HVZK nie rozwiązuje wszystkich modeli zaprzeczalności.

Powiązania: C9: anonimowość, C10: zaprzeczalność, hierarchiczne podpisy pierścieniowe.

Podpis pierścieniowy Herranza–Sáeza: jeden sekret, wspólne równanie

Cel: odbiorca ma wiedzieć, że podpisał posiadacz jednego z kluczy wskazanego pierścienia. Nie powinien dowiedzieć się, którego. Nie ma zarządcy otwierającego tożsamość. Pozostali użytkownicy w pierścieniu nie muszą uczestniczyć w podpisywaniu ani wyrażać zgody na każdy podpis.

Poniższa konstrukcja pochodzi z pracy Javiera Herranza i Germána Sáeza, Forking Lemmas in the Ring Signatures' Scenario, §4.2–4.4. Nie jest poprzednim dowodem OR z wyzwaniami sumującymi się do jednej wartości. Tutaj każdy element zobowiązania ma własny hasz, a podpis zawiera jedną odpowiedź skalarną. Publikacja oryginalna.

Parametry i oznaczenia. Grupa $G=\langle g\rangle$ ma pierwszy rząd $q$. Ustalony, uporządkowany pierścień to $L=(A_1,\ldots,A_n)$, gdzie $A_i=g^{a_i}\ne1_G$. Przyjmujemy różne klucze i $1\le n<q$. Sekret $a_i$ jest niezerowym skalarem. Wiadomość oznaczamy $m$, zobowiązania $R_i$, wyzwania $c_i$, a łączną odpowiedź $z$. Podpis to $\sigma=(R_1,\ldots,R_n,z)$.

Stosujemy $\mathcal H(m,R)\in\mathbb Z_q$, z jednoznacznym kodowaniem pary. W publikacji sekrety oznaczono $x_i$, klucze $y_i$, wyzwania $h_i$, a odpowiedź symbolem $\sigma$. Nasza zmiana liter nie zmienia równań. Publikacja zapisuje też wyzwania w podpisie. Tutaj je odtwarzamy i zawsze sprawdzamy równanie z rzeczywistymi wartościami hasza.

Podpisywanie krok po kroku

Podpisujący ma indeks $j$ i zna tylko swój sekret $a_j$.

1. Pozostałe miejsca. Dla $i\ne j$ kolejno losuje $u_i\overset{\$}{\leftarrow}\mathbb Z_q^*\setminus U$, gdzie $U$ jest zbiorem już wybranych skalarów. Początkowo $U=\varnothing$. Po każdym losowaniu dodaje $u_i$ do $U$. To losowanie bez zwracania, nie niezależne losowania z całego zbioru. Oblicza $R_i=g^{u_i}$ i $c_i=\mathcal H(m,R_i)$.
2. Zamknięcie równania. Losuje $u\overset{\$}{\leftarrow}\mathbb Z_q$ i oblicza

3. Jeżeli $R_j=1_G$ albo $R_j=R_i$ dla któregoś $i\ne j$, ponownie losuje tylko $u$. Zachowuje pozostałe zobowiązania.
4. Oblicza $c_j=\mathcal H(m,R_j)$ oraz

5. Zwraca $\sigma$. Indeks $j$ i losowość nie są elementami publicznego podpisu.

Dlaczego to możliwe? Do przygotowania $R_j$ wystarczają cudze klucze publiczne. Własny sekret jest potrzebny dopiero przy obliczaniu $z$. Podpisujący dopasowuje jedną pozycję tak, aby wszystkie składniki złożyły się w równanie weryfikacyjne.

Weryfikacja i dowód poprawności

Sprawdzamy typy i przynależność do grupy, zakres skalaru oraz różność i niezerowość zobowiązań. Te ostatnie ograniczenia są częścią rozpatrywanego profilu generycznych podpisów w raporcie. Następnie odtwarzamy wszystkie $c_i$ i akceptujemy dokładnie wtedy, gdy

Po podstawieniu $R_j$ czynniki $A_i^{-c_i}$ dla $i\ne j$ skracają się z $A_i^{c_i}$. Pozostaje

To dowód poprawności. Nie dowodzi jeszcze ani anonimowości, ani niepodrabialności. Każda z tych własności wymaga osobnego argumentu.

Dwie różne gwarancje i granice modelu

Anonimowość nie ukrywa adresu sieciowego, czasu działania ani ujawnionych wyborów losowych. Niepodrabialność nie zabrania użytkownikowi w pierścieniu podpisywania. Taka osoba właśnie ma do tego uprawnienie. Sam napis „hash odporny na kolizje” nie zastępuje założenia ROM w poniższym dowodzie niepodrabialności.

Dowód dotyczy ustalonego pierścienia. Nie przenosimy go automatycznie na adaptacyjnie rejestrowane złośliwe klucze, przejmowanie sekretów użytkowników czy dowolne zmiany pierścienia. W aplikacji o zmiennych pierścieniach trzeba określić ich kodowanie i związanie z podpisem oraz osobno przeanalizować model.

Pełne dowody: anonimowość przez liczenie, symulacja wyroczni i redukcja DL, fork wielu zapytań i stałe.