Kryptografia II stopień

W14. Zobowiązania i reszyfrowanie

Zobowiązanie ukrywa decyzję, a zarazem utrudnia jej zmianę. Publikujemy $C$, później otwieramy wiadomość i losowość. Ukrywanie chroni nadawcę. Wiązanie chroni odbiorcę.

Interfejs zobowiązania

Zapisujemy $\Pi_{\mathrm{com}}=(\mathsf{Setup},\mathsf{Commit},\mathsf{CheckOpen})$. Po ustaleniu $pp$ wywołanie $(C,o)\leftarrow\mathsf{Commit}(pp,m)$ zwraca publiczne zobowiązanie $C$ i prywatne dane otwarcia $o$. Przy otwarciu autor ujawnia $m,o$, a odbiorca liczy $b=\mathsf{CheckOpen}(pp,C,m,o)$. Uczciwe otwarcie ma dawać $b=1$. Odbiorca nie dysponuje procedurą Dec z tajnym kluczem. To autor musi ujawnić otwarcie.

Realizacja Pedersena: $pp=(G,q,g,h)$, wiadomość $m\in\mathbb Z_q$, świeża losowość $r\overset{\$}{\leftarrow}\mathbb Z_q$ i dane otwarcia $o=r$. CheckOpen sprawdza typy oraz poniższe równanie. Nazwa Commit oznacza tu algorytm zobowiązania do wiadomości, a nie krok identyfikacji Schnorra. Kontekst schematu rozróżnia te dwa interfejsy.

Pedersen: $C=g^m\cdot h^r$, gdzie generatory mają rząd $q$, a otwierający nie zna $\log_g h$. Jednostajne $r$ daje $C$ jednostajne niezależnie od $m$. Dwa otwarcia przy $m\ne m'$ dają:

Mianownik nie jest zerowy, inaczej równość wymuszałaby $m=m'$ modulo $q$. To redukcja wiązania do DL. Podmiot wybierający $h=g^\alpha$ i zachowujący $\alpha$ ma pułapkę do zmiany otwarcia. Ustanowienie parametrów jest częścią modelu.

Zobowiązanie pozostaje, lecz wiadomość się zmienia

W zapisie schematu mamy $C=g^m\cdot h^r$. Jeżeli otwierający celowo ustawił $h=g^7$, może zwiększyć wiadomość o jeden i skorygować losowość:

Realizacja na krzywej. Generatory $g,h$ odpowiadają punktom $P_1,Q$. Równanie zobowiązania to $C=m\cdot P_1+r\cdot Q$, a znana relacja to $Q=7\cdot P_1$. Odwrotność i wszystkie działania na skalarach wykonujemy w $\mathbb Z_q$, nie na liczbach zmiennoprzecinkowych. Przy poprawnym ustawieniu parametrów nikt nie powinien znać relacji logarytmicznej między generatorami. W demonstracji drugi wariant wyznacza $Q$ przez mapowanie do $G_1$ z osobną etykietą domeny. Nie deklarujemy przez to konkretnego profilu RFC 9380.

Znajomość pułapki narusza wiązanie. Nie usuwa samego argumentu doskonałego ukrywania przy jednostajnym, nieujawnionym $r$. Na ekranie pokazujemy $r$ wyłącznie do sprawdzenia rachunku. Po ujawnieniu otwarcia nie oczekujemy już ukrywania wiadomości.

Reszyfrowanie ElGamala przez świeże $t$:

zachowuje wiadomość, ponieważ czynniki skracają się podczas deszyfrowania. Rerandomizacja nie daje integralności. Proxy re-encryption zmienia uprawnienia do deszyfrowania i jest inną funkcjonalnością.

Powiązania: C11.5: ukrywanie i związanie Pedersena. Dla porównania innej funkcjonalności opartej na działaniach grupowych: C8: szyfrowanie publiczne. Zobowiązania wracają w dowodach wiedzy, protokołach losowania i weryfikacji obliczeń.

W14a. Rerandomizacja i delegowanie deszyfrowania

Serwer przechowuje zaszyfrowane dane. Chcemy pozwolić mu coś z nimi zrobić bez ujawniania wiadomości. Odświeżenie wyglądu szyfrogramu oraz zmiana uprawnionego odbiorcy to dwa różne zadania. Pierwsze prowadzi do miksów, drugie do proxy re-encryption, czyli reenkrypcji przez pośrednika.

ElGamal: nowa losowość, ten sam klucz

Przyjmijmy $A=g^a$ i wiadomość $M\in G$. ElGamal tworzy $(U,V)=(g^r,M\cdot A^r)$.

Każdy znający publiczny $A$ może wybrać niezależne $t\overset{\$}{\leftarrow}\mathbb Z_q$ i obliczyć:

Odbiorca odzyskuje $V'/(U')^a=M$. Losowość $r+t$ jest jednostajna, nawet gdy ustalimy poprzednie $r$. Publiczna transformacja nie wymaga znajomości ani $r$, ani $M$. W grupie zapisanej addytywnie mamy:

To nie jest zmiana adresata. Wciąż odszyfrowuje Alicja z sekretem $a$. To również nie jest integralność: publiczna możliwość zmiany szyfrogramu jest tutaj zamierzona. Bezpieczeństwo poufności ElGamala wiążemy z DDH w wybranej grupie, nie z samą poprawnością deszyfrowania. W demonstratorze zwykły ElGamal działa w $G_2$, bez udostępniania odpowiednika sekretnego klucza w $G_1$.

BBS: prosty iloraz kluczy i jego cena

BBS

Blaze–Bleumer–Strauss. Nazwiska autorów omawianej reenkrypcji. Nie chodzi o generator Blum–Blum–Shub.

W konstrukcji typu Blaze–Bleumer–Strauss zmieniamy także format szyfrowania. Nie należy podstawić poniższego klucza reenkrypcji do zwykłego ElGamala z poprzedniego akapitu.

Dla niezerowych sekretów Alicji $a$ i Boba $b$ przyjmujemy:

Proxy zmienia pierwszy składnik, zachowując drugi:

W MCL używamy równoważnego zapisu $U=r\cdot A$, $V=M+r\cdot P_2$, $U'=rk_{A\to B}\cdot U$. Bob oblicza $M=V-b^{-1}\cdot U'$. Widząc iloraz sekretów, od razu zadajmy trzy pytania:

• Kto tworzy klucz delegacji? Do wyliczenia skalaru $b\cdot a^{-1}$ potrzeba obu sekretów lub odpowiedniej procedury między stronami. Sam publiczny $g^b$ nie daje skalaru $b$.
• W jaką stronę działa uprawnienie? Odwrotność daje $rk_{B\to A}$. Iloczyn kluczy delegacji pozwala przejść przez kolejnych odbiorców. To delegacja dwukierunkowa i wieloetapowa.
• Co daje zmowa? Proxy zna $rk_{A\to B}$, a Bob zna $b$. Razem obliczają $a=b\cdot(rk_{A\to B})^{-1}$. Ujawniają cały sekret Alicji, nie tylko jedną wiadomość.

Niezmieniony drugi składnik pozwala też łączyć szyfrogramy przed transformacją i po niej. Przekazanie dostępu nie oznacza anonimowości relacji. Jest to dydaktyczna postać algebry BBS, EUROCRYPT 1998, nad grupą rzędu będącego liczbą pierwszą.

AFGH: pairing zmienia typ szyfrogramu

AFGH

Ateniese–Fu–Green–Hohenberger. Nazwiska autorów omawianego schematu reenkrypcji z pairingiem.

Chcemy, aby Alicja tworzyła delegację z własnego sekretu i publicznego klucza Boba. W ulepszonym wariancie Ateniese–Fu–Green–Hohenberger klucz ma dwa składniki sekretne. Jeden odpowiada za własne szyfrogramy, drugi za odbiór delegowanych szyfrogramów.

Rachunek potęgowy instancji dydaktycznej. Dla generatorów $g_1\in G_1$, $g_2\in G_2$ i pairingu $e:G_1\times G_2\to G_T$ oznaczmy $Z=e(g_1,g_2)$. Niezerowe $a_1,a_2$ są sekretami Alicji, a niezerowe $b_1,b_2$ sekretami Boba. Ich klucze publiczne to $(Z^{a_1},g_2^{a_2})$ oraz $(Z^{b_1},g_2^{b_2})$. Alicja tworzy $rk_{A\to B}=(g_2^{b_2})^{a_1}$. Dla świeżo wylosowanego $r\overset{\$}{\leftarrow}\mathbb Z_q$ szyfrogram wiadomości $M\in G_T$ ma postać $(R,S)=(g_1^r,M\cdot Z^{a_1\cdot r})$. Proxy oblicza:

Drugi rachunek wykonuje Bob, znający $b_2$. To samo potęgowanie w grupach źródłowych poniżej zapisujemy jako mnożenie punktów przez skalary. Jest to ta sama dydaktyczna specjalizacja typów, z ograniczeniem dotyczącym przenoszenia dowodu opisanym dalej.

Dla demonstracji ustalamy $e:G_1\times G_2\to G_T$, generatory $P_1,P_2$ i $Z=e(P_1,P_2)$. Wiadomość $M$ jest elementem $G_T$. Skalary $a_1,a_2,b_1,b_2$ są niezerowe. Grupy źródłowe zapisujemy addytywnie, a $G_T$ multiplikatywnie:

1. Alicja deleguje: tworzy $rk_{A\to B}=a_1\cdot V_B=a_1\cdot b_2\cdot P_2$ i przekazuje go proxy. Nie potrzebuje $b_2$.
2. Nadawca szyfruje dla Alicji: dla losowego $r$ tworzy szyfrogram drugiego poziomu $(R,S)=(r\cdot P_1,M\cdot U_A^r)\in G_1\times G_T$.
3. Proxy przekształca: oblicza $D=e(R,rk_{A\to B})=Z^{r\cdot a_1\cdot b_2}$ i przekazuje Bobowi szyfrogram pierwszego poziomu $(D,S)\in G_T^2$.
4. Bob odszyfrowuje: oblicza $S/D^{b_2^{-1}}=M$. Alicja nadal może odszyfrować pierwotną parę jako $S/e(R,P_2)^{a_1}$.

Dlaczego tylko jeden etap delegacji? Po transformacji pierwszy składnik leży w $G_T$, a nie w $G_1$. Nie wolno podać go jako pierwszego argumentu tego samego pairingu. Zmiana typu wyjścia jest tutaj częścią funkcjonalności, nie usterką interfejsu.

Oryginalna publikacja opisuje pairing symetryczny. Powyższy układ typów dla BLS12-381 jest specjalizacją dydaktyczną do sprawdzania równań, a nie deklaracją przeniesienia oryginalnego twierdzenia bezpieczeństwa na pairing typu 3. Źródło konstrukcji z dwoma skalarami to Third Attempt w AFGH, NDSS 2005 i §3.3 wersji TISSEC 2006. W tej wersji oryginalny argument poufności wykorzystuje eDBDH, a ochrony sekretu głównego problem logarytmu dyskretnego.

NDSS

Network and Distributed System Security Symposium. Sympozjum o bezpieczeństwie sieci i systemów rozproszonych.

TISSEC

Transactions on Information and System Security. Dawny tytuł czasopisma ACM o bezpieczeństwie informacji i systemów.

eDBDH

extended Decisional Bilinear Diffie–Hellman. Rozszerzony decyzyjny biliniowy problem Diffiego–Hellmana. Dokładny zestaw dodatkowych danych określa założenie w publikacji o reenkrypcji.

Nieodzyskany skalar nie oznacza braku szkody

Proxy wraz z Bobem może obliczyć $b_2^{-1}\cdot rk_{A\to B}=a_1\cdot P_2$. Nie jest to sam skalar $a_1$, ale wystarcza do obliczania $e(R,a_1\cdot P_2)$ i odczytu szyfrogramów drugiego poziomu Alicji. Ochrona sekretu głównego i nieprzekazywalność prawa odczytu są różnymi własnościami. Tego pomocniczego punktu nie wolno traktować jako obojętnej dodatkowej części publicznego klucza.

Omawiany rachunek nie daje automatycznie delegacji ograniczonej do jednego dokumentu, ochrony CCA ani odwołania dostępu do już ujawnionych danych. Szyfrowanie elementu grupy nie jest też gotowym formatem szyfrowania plików. Realne zastosowanie wymaga odpowiedniej konstrukcji hybrydowej i modelu integralności zgodnego z dozwoloną transformacją.

W teście niewłaściwego klucza porównujemy wynik z wiadomością znaną demonstratorowi. Sam odbiorca nie zawsze dostałby błąd. W surowym szyfrowaniu grupowym może otrzymać inny poprawny element grupy. To kolejna różnica między poprawnością, poufnością i uwierzytelnionym odczytem.

Powiązania: zadania o typach i koluzji, laboratorium przekształceń, homomorfizm. Ta sama algebra może służyć innej funkcjonalności, ale nie przenosi automatycznie jej gwarancji.

W14b. Sieci miksujące: ukryć przyporządkowanie

Poufność ukrywa treść. Czasem równie istotne jest pytanie który szyfrogram wyjściowy odpowiada któremu wejściu. Przykładem jest partia zaszyfrowanych kart do głosowania lub wiadomości, których kolejność ujawniałaby nadawców. Mix przyjmuje całą partię, zmienia kolejność i przekształca szyfrogramy.

Dlaczego potrzebne są dwie operacje

• Samo tasowanie: zmieniamy kolejność, ale bajty szyfrogramów pozostają te same. Obserwator porównuje wejścia i wyjścia i odtwarza permutację.
• Sama rerandomizacja: zmieniają się bajty, ale zachowanie kolejności ujawnia przyporządkowanie pozycji.
• Obie operacje: tajna permutacja usuwa powiązanie pozycyjne, a niezależna rerandomizacja usuwa proste rozpoznawanie po równości szyfrogramów. Dalszy argument prywatności wymaga właściwego modelu i założeń kryptograficznych.

Dla $n$ szyfrogramów pod wspólnym kluczem $A$ mix wybiera tajną permutację $\pi$ zbioru $\{1,\ldots,n\}$ i niezależne $t_1,\ldots,t_n\in\mathbb Z_q$. Publikuje:

Kolejny mix wykonuje ten sam rodzaj operacji na nowej partii. W demonstracji wszystkie etapy pozostają widoczne, ale przypisanie wiadomości do pozycji jest ukryte do chwili odszyfrowania. Opcjonalne oznaczenie pochodzenia pokazuje wiedzę administracyjną demonstratora, a nie dane wysyłane przez prawdziwy mix. Losowa permutacja może pozostawić niektóre pozycje, a nawet całą kolejność bez zmian. Jedna taka próba nie jest błędem losowania.

Co trzeba udowodnić, zanim zaufamy partii

Złośliwy mix mógłby usunąć kartę, powielić inną albo podmienić wiadomość. Samo poprawne odszyfrowanie każdej pozycji tego nie wykrywa. Potrzebujemy dowodu, że nowa partia zawiera ten sam multizbiór wiadomości, przy ukrytym przyporządkowaniu. Świadkiem są permutacja i losowości. Publiczne dane to klucz oraz obie partie:

$S_n$ oznacza zbiór wszystkich permutacji $n$ pozycji. Dowód z wiedzą zerową tej relacji ma przekonać odbiorcę o poprawności przetasowania bez pokazania $\pi$. Równość iloczynów wszystkich szyfrogramów nie wystarcza, bo kompensujące się zmiany mogą zachować iloczyn, a zmienić wiadomości. Przykładem właściwych rozwiązań są weryfikowalne przetasowania Neffa. Demonstracja oblicza szyfrowanie, tasowanie i rerandomizację, ale nie implementuje tego dowodu.

Historia, model i granice anonimowości

Historyczny mix Chauma usuwa warstwy szyfrowania i przestawia wiadomości. Nie jest identyczny z pokazanym tu miksem rerandomizującym ElGamala. Łączy je cel: utrudnić powiązanie wejścia z wyjściem. Różnią je formaty komunikatów, operacje i sposób uzasadnienia bezpieczeństwa.

W modelu miksów rerandomizujących niepowiązywalność wejść i wyjść partii może opierać się na co najmniej jednym uczciwym miksie, który zachowa tajną permutację i losowość. To wymaga również poufności szyfrowania, właściwego postępowania z błędnymi szyfrogramami i nieprzekroczonego progu kompromitacji klucza deszyfrującego. Samo dodanie jednego serwera nie dowodzi anonimowości wobec aktywnego przeciwnika.

Odszyfrowanie można rozdzielić progowo między uczestników. Chroni to przed samotnym posiadaczem całego klucza, lecz wymaga bezpiecznego generowania udziałów i sprawdzania częściowych deszyfrowań. Nawet prawidłowy shuffle nie ukryje tożsamości wpisanej w treść, nie usunie korelacji długości i czasu poza modelem partii ani nie zmusi serwera do odpowiedzi. Weryfikowalność, anonimowość i dostępność trzeba rozpatrywać osobno.

Powiązania: wiedza zerowa, próg, ćwiczenia, laboratorium partii.