Kryptografia II stopień

W13. Współdzielenie sekretu i wykluczanie odbiorców

Interfejs współdzielenia

Schemat $\Pi_{\mathrm{SS}}=(\mathsf{Setup},\mathsf{Share},\mathsf{Recover})$ nie jest szyfrowaniem z osobnym kluczem odszyfrowującym. Setup ustala ciało, liczbę uczestników i próg. Rozdający wywołuje $(s_1,\ldots,s_n)\leftarrow\mathsf{Share}(pp,s)$ dla sekretu $s$. Uczestnik $i$ otrzymuje prywatnie tylko swój udział $s_i$. Procedura $\mathsf{Recover}(pp,\{(i,s_i):i\in I\})$ odtwarza sekret z odpowiedniego zbioru $I$ udziałów.

Poprawność dotyczy wystarczającej liczby prawidłowych udziałów. Prywatność dotyczy informacji w mniejszej koalicji. Kontrola formatu nie wykrywa automatycznie udziału, który ma poprawny typ, lecz złą wartość. Po określeniu tego interfejsu możemy wybrać jako jego realizację wielomian Shamira.

Sekret $s$ ma być odtwarzalny z $t$ udziałów, lecz ukryty przed mniejszą koalicją. Liczbę uczestników oznaczymy przez $n$, a próg przez $t$, gdzie $1\le t\le n<q$. W schemacie Shamira pracujemy nad ciałem $\mathbb Z_q$ dla pierwszego $q$. Losujemy niezależnie $t-1$ współczynników $a_1,\ldots,a_{t-1}$ z całego ciała i budujemy wielomian:

Sekret to $f(0)$. Udział ma postać $(i,f(i))$ dla różnych niezerowych $i$. Współczynniki są niezależne i jednostajne. Stopień wynosi co najwyżej $t-1$.

Dwa rachunki: odtworzenie i tajność

Interpolacja odtwarza wielomian z jego wartości w różnych punktach. Wielomian stopnia co najwyżej $t-1$ jest jednoznacznie określony przez $t$ takich wartości. Do odzyskania sekretu potrzebujemy tylko jego wartości w zerze. Wzór Lagrange'a wyznacza ją jako sumę udziałów pomnożonych przez wagi. Każda waga zależy wyłącznie od publicznych identyfikatorów uczestników. Ułamki poniżej oznaczają mnożenie przez odwrotności w ciele, nie dzielenie zmiennoprzecinkowe.

Dla $t$ identyfikatorów w zbiorze $I$:

Mianowniki są niezerowe. Dla mniej niż $t$ udziałów każdy sekret ma tyle samo zgodnych uzupełnień współczynników. Dlatego obserwacja jest niezależna od sekretu. Interpolacja dowodzi poprawności. Liczenie uzupełnień dowodzi prywatności.

Shamir nie uwierzytelnia udziałów. Fałszywy udział może zniszczyć wynik. Weryfikowalne współdzielenie wymaga dodatkowych mechanizmów.

Rozgłaszanie z wykluczaniem

Punkt odniesienia: każdy odbiorca ma własny klucz, a nadawca szyfruje klucz treści oddzielnie dla niewykluczonych. Koszt jest liniowy. Drzewiaste pokrycie wybiera poddrzewa bez wykluczonych liści i szyfruje klucz treści pod kluczami tych węzłów. Trzeba dowieść, że koalicja wykluczonych nie zna żadnego użytego klucza.

Powiązania: C11, Shamir.

Przykład: w pełnym drzewie o ośmiu liściach, po wykluczeniu liścia 1, można pokryć odbiorców poddrzewami $\{2\}$, $\{3,4\}$ i $\{5,6,7,8\}$. Odbiorca posiada klucze węzłów na własnej ścieżce do korzenia. Nie używamy klucza korzenia, bo zna go również wykluczony odbiorca. Dla każdej części pokrycia wystarczy jedna chroniona kopia świeżego klucza treści.

To przykład complete subtree z niezależnymi kluczami węzłów. Gdy odwołano więcej osób, trzeba policzyć nowe pokrycie. Klucz treści musi się zmienić. Odwołanie nie usuwa wiadomości ani dawnych kluczy, które odbiorca już poznał.

Źródło konstrukcji i modelu odbiorców: Naor–Naor–Lotspiech, Revocation and Tracing Schemes for Stateless Receivers.

W13a. Identyfikacja i podpis bez odtwarzania sekretu

Funkcjonalność progowa oznacza, że co najmniej $t$ z $n$ uczestników wspólnie używa jednego klucza. Zwykłe zebranie udziałów Shamira u koordynatora odtwarza cały sekret. Chcemy zamiast tego połączyć odpowiedzi protokołu, nie ujawniając koordynatorowi udziałów. Najpierw pokazujemy algebrę z zaufanym dealerem i uczciwymi uczestnikami, potem wskazujemy dodatkowe obowiązki modelu złośliwego.

Interpolacja odpowiedzi Schnorra

Najpierw potęgi i udziały. Dla wielomianu $f$ stopnia co najwyżej $t-1$ sekret to $a=f(0)$, a udziały to $a_i=f(i)$ dla różnych niezerowych indeksów $i\in\mathbb Z_q$. Niech $I$ będzie ustalonym zbiorem co najmniej $t$ uczestników, a wagi interpolacji $\lambda_i$ spełniają $\sum_{i\in I}\lambda_i\cdot a_i=a$. Ich wzór podamy poniżej. Publiczne klucze zapisujemy jako $A=g^a$ i $A_i=g^{a_i}$.

Uczestnik wysyła $X_i=g^{u_i}$ dla świeżego nonce $u_i$. Zobowiązania mnożymy, lecz odpowiedzi skalarne dodajemy:

Dla wspólnego wyzwania $c$ częściowa kontrola to $g^{s_i}=X_i\cdot A_i^{c\cdot\lambda_i}$. Po pomnożeniu równań uzyskujemy:

Weryfikator widzi zatem zwykłe równanie Schnorra. Sposób przygotowania odpowiedzi jest rozproszony. Realizacja na krzywej. Poniżej zapisujemy dokładnie ten rachunek addytywnie, aby wyjaśnić operacje MCL.

Dealer losuje wielomian $f$ stopnia co najwyżej $t-1$, z sekretem $a=f(0)$. Uczestnik $i$ otrzymuje $a_i=f(i)$. Publiczne są $A=a\cdot P_2$ i klucze weryfikacyjne udziałów $A_i=a_i\cdot P_2$. Dla ustalonego zbioru uczestników $I$, o liczności co najmniej $t$, definiujemy współczynniki:

Każdy uczestnik losuje świeże $u_i$ i przekazuje $X_i=u_i\cdot P_2$. Po zebraniu zobowiązań powstaje $X=\sum_{i\in I}X_i$. Weryfikator losuje jedno wspólne wyzwanie $c$. Uczestnicy odpowiadają:

Koordynator sprawdza częściowe równania $s_i\cdot P_2=X_i+c\cdot\lambda_i\cdot A_i$. Weryfikator końcowy sprawdza zwykłe równanie Schnorra:

Co wynika z tych równań, a co jeszcze nie

Poprawność wynika z liniowości i interpolacji. HVZK końcowego transkryptu otrzymujemy jak dla Schnorra: losujemy $c,s$ i obliczamy $X=s\cdot P_2-c\cdot A$. Suma niezależnych, jednostajnych nonce jest jednostajna. Dotyczy to widoku zewnętrznego weryfikatora, nie pełnego widoku złośliwej koalicji uczestników.

Szczególna rzetelność, jak w W7: z dwóch akceptujących transkryptów z tym samym $X$ i różnymi wyzwaniami otrzymujemy $a=(s-s')\cdot(c-c')^{-1}$. Dwa przebiegi z tym samym częściowym $X_i$ mogą również ujawnić udział:

Dlatego nonce uczestnika jest jednorazowy, nawet gdy sesja została przerwana. Lista $I$ musi być ustalona i uwierzytelniona. Zmiana listy zmienia wagi. Klucze $A_i$ ujawniają obrazy udziałów, więc bezwarunkowy dowód prywatności samych udziałów Shamira nie jest już pełnym dowodem dla publicznego transkryptu tego systemu.

Pełny protokół progowy wymaga ponadto poprawnej dystrybucji klucza, kontroli złośliwych udziałów, związania zobowiązań z sesją, ochrony przed adaptacyjnym wyborem nonce i analizy współbieżności. FROST używa dwóch nonce i współczynników wiążących. Nie jest tylko powyższym równaniem z wyzwaniem zastąpionym haszem. RFC 9591 opisuje konkretny dwurundowy protokół podpisu i wymagania implementacyjne. Nasza animacja pokazuje prostszy interaktywny protokół dla ustalonej sesji, a nie implementację FROST.

Te same udziały, inna funkcjonalność: progowy BLS

Cel: uczestnicy tworzą podpis jednej wiadomości $m$ pod wspólnym kluczem, nie odtwarzając sekretu $a$. Zachowujemy udziały $a_i$, zbiór $I$ i wagi $\lambda_i$ z poprzedniej konstrukcji. Zmieniają się algorytm odpowiedzi i sposób łączenia wyników.

W zapisie potęgowym uczestnik tworzy $\sigma_i=\mathcal H_{G_1}(m)^{a_i}$. Interpolacja w wykładniku daje $\sigma=\prod_{i\in I}\sigma_i^{\lambda_i}=\mathcal H_{G_1}(m)^a$. Nie odtwarzamy jawnie $a$. Odpowiednie obrazy udziałów łączą się w podpis tego samego klucza $A$. W zapisie punktowym iloczyn elementów zastępujemy sumą punktów:

Dla wiadomości $m$ każdy wybrany uczestnik oblicza $\sigma_i=a_i\cdot\mathcal H_{G_1}(m)$. Sprawdzamy $e(\sigma_i,P_2)=e(\mathcal H_{G_1}(m),A_i)$ i składamy:

Końcowy podpis odpowiada jednemu kluczowi publicznemu $A$. Nie ujawnia sam przez się, który dopuszczalny podzbiór uczestniczył. Wielomian definiuje próg, a pairing weryfikuje udziały i podpis. Własności kompletnego schematu zależą od generowania klucza, walidacji punktów, definicji przeciwnika i założeń BLS. Interpolacja sama nie jest dowodem niepodrabialności. Źródło tej rodziny: Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme.

Powiązania: C13, L7.