Kryptografia II stopień

Od definicji bezpieczeństwa do konstrukcji, redukcji i publikacji naukowych.

W17. Od funkcjonalności podpisu do kosztu obliczeń

Liczenie kosztu pojedynczego potęgowania rozpocznij od square-and-multiply i drabinki. Tam podano dokładny wariant obu algorytmów, niezmiennik i liczniki działań potrzebne w C15.6 oraz L9.6. Poniżej traktujemy takie operacje jako składniki kosztu całego schematu.

Najpierw cel, potem narzędzie. Podpis indywidualny, wspólny podpis wielu osób, użycie jednego klucza przez próg osób i ukrycie podpisującego w pierścieniu nie są kolejnymi nazwami tej samej funkcji. Pairingi dają zwięzłe równania weryfikacji, ale nie zastępują definicji tego, co weryfikator ma stwierdzić.

Próg dotyczy współpracy. Pierścień dotyczy anonimowości podpisującego. Agregacja oszczędza reprezentację, lecz wymaga kontroli kluczy i własnego modelu bezpieczeństwa.

Agregacja nie zastępuje kontroli kluczy

W zapisie potęgowym niezależni podpisujący mają $A_i=g_2^{a_i}$ i $\sigma_i=\mathcal H_{G_1}(m)^{a_i}$ . Dla tej samej wiadomości łączymy podpisy przez iloczyn $\sigma=\prod_i\sigma_i$ . Odpowiada mu iloczyn kluczy, a kontrola ma postać $e(\sigma,g_2)=e(\mathcal H_{G_1}(m),\prod_i A_i)$ . To równanie poprawności, jeszcze nie gwarancja niepodrabialności. Przy przejściu do punktów iloczyny w grupach źródłowych stają się sumami:

Dla kluczy $A_i=a_i\cdot P_2$ podpisy BLS na tej samej wiadomości sumują się do $\sigma=\sum_i\sigma_i$ . Formalnie

e(\sigma,P_2)=e\left(\mathcal H_{G_1}(m),\sum_i A_i\right).

Bez kontroli kluczy napastnik może dobrać $A_2=b\cdot P_2-A_1$ i przedstawić $b\cdot\mathcal H_{G_1}(m)$ jako rzekomy podpis obu osób. To rogue-key attack, a nie rozwiązanie logarytmu dyskretnego. Potrzebna jest właściwa rejestracja i dowód posiadania klucza albo inny udowodniony wariant wiążący klucze z podpisywanym tekstem. Dla różnych wiadomości podstawowe równanie ma postać $e(\sigma,P_2)=\prod_i e(\mathcal H_{G_1}(m_i),A_i)$ , z wymaganiami konkretnego wariantu, w tym odrębności wiadomości tam, gdzie zakłada ją dowód. Źródło agregacji: Boneh–Gentry–Lynn–Shacham.

Podpis pierścieniowy ma inny cel: jeden uczestnik podpisuje, a jego indeks pozostaje ukryty w zadanym modelu. Dowód OR z W11 realizuje tę intuicję bez pairingu. Istnieją również podpisy pierścieniowe oparte na pairingach, np. konstrukcja identity-based Zhanga i Kima, ale sama zamiana równań na pairingowe nie daje anonimowości. Trzeba sprawdzić rozkład podpisu i jego zależność od rzeczywistej gałęzi. W wariancie identity-based występuje dodatkowo podmiot wydający klucze, co zmienia model zaufania.

Liczymy rodzaje operacji, nie tylko znaki we wzorze

Niech $M_1,M_2$ oznaczają koszt mnożenia zmiennej bazy przez skalar w $G_1,G_2$ , $P$ koszt pełnego pairingu, $H_1$ koszt hash-to- $G_1$ , a $A_1,A_2$ koszt dodawania punktów. To koszty dla ustalonej biblioteki, parametrów i sprzętu. Przykładowy rachunek ma postać

T\approx n_1\cdot M_1+n_2\cdot M_2+n_P\cdot P+n_H\cdot H_1 +n_{A_1}\cdot A_1+n_{A_2}\cdot A_2+T_{\mathrm{inne}}.

$T$ oznacza łączny czas, współczynniki $n$ liczą wykonane operacje odpowiednich typów, a $T_{\mathrm{inne}}$ zbiera pozostałe koszty, np. losowanie, kodowanie i obsługę pamięci. Litera $P$ w tym rachunku oznacza koszt pairingu, nie generator z równań grupowych.

Operacja protokołu	Prosty rachunek, bez optymalizacji	Co jeszcze uwzględnić
Podpis BLS	$H_1+M_1$	Kodowanie wiadomości i domeny
Weryfikacja BLS	$H_1+2\cdot P$	Walidacja klucza i podpisu
Weryfikacja Schnorra w $G_2$	$2\cdot M_2+A_2$	Wyzwanie, format i walidacja
Weryfikacja dowodu OR z $n$ gałęziami	$2\cdot n\cdot M_2+n\cdot A_2$	Sprawdzenie sumy wyzwań
Iloczyn szyfrogramów z W16	$4\cdot P$	Odczyt i kodowanie są osobno

To liczby operacji przy bezpośredniej realizacji wzorów. Implementacja może połączyć mnożenia w MSM. Iloczyn pairingów może współdzielić końcowe potęgowanie po pętlach Millera. Prekomputacja stałej bazy zmienia koszt. Dlatego „dwa pairingi” nie muszą kosztować dwukrotności każdego możliwego wywołania biblioteki.

MSM: Multi-Scalar Multiplication. Obliczenie sumy punktów pomnożonych przez zadane skalary.

Koszt operacji · pomiar na tym urządzeniu

5 partii po 20 operacji, po rozgrzewce. Mediana średnich czasów. Milisekundy na operację.

Operacja	Mediana · ms/op.	Minimum · ms/op.	Maksimum · ms/op.
Brak pomiaru. Wyniki nie są wczytywane z gotowej tabeli.

Gotowe do rozpoczęcia.

Pomiar dotyczy bieżącej przeglądarki, lokalnego MCL i BLS12-381. Wykonuje rozgrzewkę, następnie kilka partii i podaje medianę średniego czasu operacji w partii. Nie mierzy sieci, stałoczasowości ani poziomu bezpieczeństwa. Haszujemy do grupy przez API MCL, nie przypisujemy temu automatycznie zgodności z konkretną standardową ciphersuite. Otwarta konsola, oszczędzanie energii i inne zadania zmieniają wyniki.

Parametr bezpieczeństwa, rozmiar instancji i komunikacja

Rozróżniaj trzy osie. Parametr bezpieczeństwa steruje wielkością grup i kosztami podstawowych działań. Rozmiar zadania to np. liczba podpisujących lub bramek. Komunikacja obejmuje liczbę bajtów i rund, więc opóźnienie sieci może dominować mimo szybkiej lokalnej algebry. Liniowość liczby pairingów względem liczby uczestników nie oznacza liniowości względem długości bitowej modułu.

W dowodzie również liczymy koszt. Jeśli redukcja powtarza przeciwnika, jej czas obejmuje wszystkie uruchomienia i obsługę wyroczni. Strata sukcesu $\varepsilon$ do wartości rzędu $\varepsilon^2/Q$ może mieć znaczenie dla parametrów, nawet gdy równania ekstrakcji są krótkie. Konkretne stałe należy brać z twierdzenia dla danego schematu. Nie utożsamiaj kosztu redukcji z czasem podpisywania.

Powiązania: C15, L9.

W18. SNARK: krótki argument nie oznacza taniego dowodzenia

SNARK: Succinct Non-interactive Argument of Knowledge. Zwięzły nieinteraktywny argument wiedzy.

SNARK to zwięzły, nieinteraktywny argument wiedzy. Dla publicznego stwierdzenia $x$ i ukrytego świadka $w$ określamy efektywnie sprawdzalną relację $R(x,w)=1$ . Dowodzący ma przekonać weryfikatora, że zna odpowiedni $w$ . Słowo „argument” wskazuje na bezpieczeństwo wobec obliczeniowo ograniczonego przeciwnika. Wiedzę formalizuje odpowiedni ekstraktor, nie samo istnienie świadka. Zero knowledge jest dodatkową własnością, nie konsekwencją samego słowa „zwięzły”. Konstrukcje zk-SNARK realizują oba cele.

zk-SNARK: zero-knowledge Succinct Non-interactive Argument of Knowledge. Zwięzły nieinteraktywny argument wiedzy z własnością zerowej wiedzy.

Krótki dowód nie usuwa kosztu budowy świadka i dowodzenia. Relacja musi wiązać dane z deklarowanym zadaniem. Diagram pomija parametry setupu w argumentach wywołań, nie w modelu bezpieczeństwa.

Przykład: $x$ zawiera zobowiązanie do danych i ogłoszony wynik, a $w$ zawiera dane i otwarcie zobowiązania. Relacja sprawdza zgodność otwarcia oraz wykonanie zdefiniowanej funkcji. Samo równanie $z=u\cdot v$ nie wiąże wyniku z konkretnymi danymi, jeśli nic nie określa ich tożsamości. Najtrudniejszy błąd bywa więc nie w pairingu, lecz w zbyt słabym opisie relacji.

W Groth16 dowód ma trzy elementy grup, a sprawdzenie korzysta z równania pairingowego. Koszt weryfikacji obejmuje także przetwarzanie publicznego wejścia. Dowodzący musi wyznaczyć świadka i wykonać kosztowne operacje zależne od rozmiaru obwodu. Przygotowanie parametrów jest związane z obwodem i wymaga właściwego modelu zaufania. Publikacja: Groth, On the Size of Pairing-Based Non-interactive Arguments.

Implementacje działają. Przykładem jest snarkjs, z obliczeniami JavaScript/WebAssembly i kompletną ścieżką tworzenia oraz weryfikowania dowodów. Nie oznacza to, że ogólny SNARK jest najprostszą metodą dla każdego równania. Dla małej, dobrze określonej relacji dedykowany dowód Schnorra lub równanie pairingowe może być znacznie prostsze do implementacji i audytu.

Przed wyborem porównaj czas tworzenia świadka, czas dowodzenia, szczytową pamięć, rozmiar parametrów, rozmiar dowodu i czas weryfikacji. Osobno sprawdź założenia, zaufany setup i ewentualną odporność postkwantową. Klasyczny pairingowy Groth16 nie staje się postkwantowy przez to, że jest SNARK-iem. Systemy transparentne mogą unikać tajnej konfiguracji, lecz mają własne założenia i kompromisy. W tym miejscu poznajemy kontrakt i koszty, nie deklarujemy implementacji pełnego SNARK-a na stronie.