Wizualne współdzielenie sekretu i schematy addytywne

Wizualne współdzielenie sekretu (Naor i Shamir, 1994) dzieli obraz na n przezroczy w taki sposób, że nałożenie k przezroczy ujawnia tajny obraz, podczas gdy mniejsza liczba nie ujawnia niczego — nawet przeciwnikowi dysponującemu nieograniczoną mocą obliczeniową.

Każdy piksel sekretu jest rozwijany do bloku 2x2. Dla czarnego piksela oba udziały otrzymują komplementarne wzorce (po nałożeniu cały blok jest czarny). Dla białego piksela oba udziały otrzymują ten sam wzorzec (po nałożeniu 50% czerni = szarość). Oko dostrzega różnicę.

Dla ciągów bitów: podziel sekret S, generując losowe R_1, R_2, ..., R_{n-1}. Ustaw R_n = S XOR R_1 XOR ... XOR R_{n-1}. Wykonanie operacji XOR na wszystkich n udziałach daje S. Dowolny podzbiór n-1 udziałów jest jednostajnie losowy — nie ujawnia niczego o S.

Współdzielenie z użyciem XOR lub addytywne jest schematem n-of-n (wymaga wszystkich udziałów). SSS Shamira jest schematem k-of-n (wystarczy dowolne k udziałów). Współdzielenie addytywne jest prostsze i szybsze, natomiast Shamir obsługuje dowolne progi. Protokoły MPC często wykorzystują współdzielenie addytywne do operacji arytmetycznych.

Dla sekretów będących liczbami całkowitymi: podziel S jako S = s_1 + s_2 + ... + s_n (mod p). Każde s_i jest losowym elementem Z_p. Aby dodać dwie współdzielone wartości A+B, każda strona lokalnie dodaje swoje udziały: (a_i + b_i) mod p. Dodawanie nie wymaga komunikacji.

Mnożenie współdzielonych wartości wymaga interakcji. Klasyczna metoda potrójnego elementu Beaver polega na wstępnym obliczeniu współdzielonej losowej trójki (a, b, c=ab). Aby obliczyć x*y, ujawnij (x-a) i (y-b) wszystkim stronom (nie ujawniają one niczego o x ani y), a następnie oblicz x*y z użyciem trójki.

Liniowy schemat współdzielenia sekretu (LSSS) realizuje dowolną monotoniczną strukturę dostępu. Shamir jest schematem LSSS. Schematy LSSS stanowią podstawę szyfrowania opartego na atrybutach (ABE) oraz systemów kontroli dostępu z wieloma uprawnionymi podmiotami.

Pakowany Shamir pozwala współdzielić wiele sekretów w jednym wielomianie: koduje k sekretów jako współczynniki wielomianu stopnia (n-k). Umożliwia amortyzację kosztu komunikacji w protokołach MPC, gdy wiele wartości musi zostać współdzielonych jednocześnie.

Podstawowe schematy współdzielenia nie chronią przed złośliwymi posiadaczami udziałów przesyłającymi nieprawidłowe udziały. Weryfikowalne współdzielenie sekretu (VSS) dodaje zobowiązania, a odporne współdzielenie sekretu dodaje korekcję błędów, dzięki czemu rekonstrukcja powiedzie się nawet przy t nieprawidłowych udziałach.

Kryptografia wizualna: uwierzytelnianie drukowanych dokumentów, bezpieczne karty do głosowania. Współdzielenie addytywne: SPDZ MPC, bezpieczna agregacja w federacyjnym uczeniu maszynowym (Google). Schematy progowe: tworzenie kopii zapasowych ziarna portfeli sprzętowych, zarządzanie kluczami w przedsiębiorstwach.

Schemat rampowy (k,n) jest słabszy: mniej niż k-d udziałów ujawnia częściową informację (d poziomów tajności). Stosuje się go, gdy doskonała tajność częściowych udziałów nie jest wymagana, ale kluczowa jest efektywność przechowywania. Umożliwia tworzenie krótszych udziałów niż w schemacie Shamira.

W addytywnym współdzieleniu n-of-n z użyciem XOR ile udziałów jest potrzebnych do odtworzenia sekretu?

Kryptografia wizualna dzieli obrazy na przezrocza, współdzielenie addytywne wykorzystuje XOR w schematach n-of-n, a Shamir obsługuje schematy k-of-n. MPC wykorzystuje współdzielenie addytywne i trójki Beaver do mnożenia. Dalej: podpisy progowe i zastosowania w praktyce.