Dzielenie sekretu

Dzielenie sekretu (współdzielenie tajemnicy) – protokół kryptograficzny, w której pewien sekret jest dzielony na fragmenty i rozdawany uczestnikom w taki sposób, że odtworzyć go może jedynie określona podgrupa użytkowników.

Celem protokołu jest ochrona wiadomości przed utratą zabezpieczającego ją klucza. Wykonanie większej ilości kopii klucza zmniejszałoby bezpieczeństwo systemu, a mniejsza liczba kopii klucza zwiększałaby ryzyko zgubienia ich wszystkich. Protokoły współdzielenia tajemnicy realizują pierwszy przypadek, poprawiając niezawodność systemu, jednak bez zwiększania ryzyka.

Formalnie, w protokole uczestniczy osoba dzieląca, która przygotowuje fragmenty, i gracze którzy je przechowują. Protokół określamy jako ${\displaystyle (t,n)}$-progowy, jeśli fragmentów jest ${\displaystyle n,}$ a do odtworzenia sekretu trzeba zebrać ich ${\displaystyle t.}$ Dowolny zbiór ${\displaystyle t-1}$ fragmentów powinien być całkowicie losowy i nie pozwalać na odtworzenie nawet części sekretu.

Dzielenie sekretu zostało opracowane niezależnie przez Adi Szamira i George Blakleya w 1979 roku.

Ograniczenia na dzielenie sekretu

Protokoły dzielenia sekretu zaprojektowane przez Adi Szamira i George Blakleya są bezpieczne teorio-informacyjnie, co oznacza że nawet przeciwnik dysponujący nieograniczoną mocą obliczeniową nie jest w stanie ich oszukać.

Wynikają z tego pewne ograniczenia, które musi spełniać każdy taki protokół:

• Każdy fragment sekretu musi mieć długość co najmniej równą długości sekretu. Formalnie można to udowodnić w terminach teorii informacji, ale ma to też intuicyjne wyjaśnienie: Skoro ${\displaystyle t-1}$ fragmentów nie pozwala odtworzyć ani jednego bitu informacji, a ${\displaystyle t}$ pozwala odtworzyć wszystkie, ostatni fragment musi zawierać wystarczającą liczbę bitów.
• Protokół musi używać losowych bitów. Każdy bit tajnej informacji podzielonej w sposób ${\displaystyle (t,n)}$-progowy wymaga użycia ${\displaystyle t-1}$ losowych bitów. Intuicyjnie wynika to z faktu że do uzyskania podziału potrzebnych jest ${\displaystyle t-1}$ losowych fragmentów o wielkości równej wielkości sekretu.

Trywialne dzielenie sekretu

Dzielenie ${\displaystyle (n,n)}$-progowe jest trywialne do uzyskania: Zapisujemy sekret jako liczbę ${\displaystyle s}$ z jakiegoś przedziału, np. od ${\displaystyle 0}$ do ${\displaystyle k-1.}$ Generujemy ${\displaystyle n-1}$ fragmentów z losowych liczb mniejszych od ${\displaystyle k.}$ ${\displaystyle s_{1},s_{2},\dots ,s_{n-1}.}$ Ostatni fragment wyliczamy: ${\displaystyle s_{n}=s-s_{1}-s_{2}-\dots -s_{n-1}{\bmod {k}}.}$ Mając wszystkie fragmenty, możemy wyliczyć ich sumę mod ${\displaystyle k,}$ otrzymując ${\displaystyle s.}$ Każdy mniejszy zbiór fragmentów generuje losowy wynik.

Przykład: Sekret ${\displaystyle s}$ to liczba od 0 do 9999, załóżmy że wynosi 1410,

• losujemy ${\displaystyle s_{1},}$ powiedzmy 915,
• losujemy ${\displaystyle s_{2},}$ powiedzmy 6321,
• losujemy ${\displaystyle s_{3},}$ powiedzmy 4530,
• obliczamy ${\displaystyle s_{4}=(1410-915-6321-4530){\bmod {1}}0\ 000=-356{\bmod {1}}0\ 000=9644.}$

Jeśli wszyscy uczestnicy będą chcieli poznać sekret, dodają swoje fragmenty i otrzymają:

${\displaystyle (s_{1}+s_{2}+s_{3}+s_{4}){\bmod {1}}0\ 000=11\ 410{\bmod {1}}0\ 000=1410.}$

Jeśli nie mamy ograniczeń pamięciowych, możemy użyć tej metody do wygenerowania dowolnego schematu dzielenia sekretu. Dla dowolnego zbioru graczy który ma mieć możliwość odtworzenia sekretu generujemy wtedy osobny podział. Przykładowo jeśli chcemy żeby z trzech graczy każdych dwóch mogło odtworzyć sekret, generujemy trzy niezależne podziały ${\displaystyle (2,2)}$-progowe. Takie podejście szybko staje się niepraktyczne: przykładowo gdy każdych 10 z 20 graczy ma móc odtworzyć sekret, musielibyśmy stworzyć ponad 180 tysięcy podziałów. Dlatego wykorzystuje się bardziej zaawansowane protokoły podziału.

Protokół Shamira

Dwa punkty wyznaczają jednoznacznie prostą, trzy punkty wyznaczają parabolę, i ogólnie ${\displaystyle n}$ punktów wyznacza jednoznacznie wielomian stopnia ${\displaystyle n-1.}$ W protokole Shamira osoba dzieląca wybiera wielomian stopnia ${\displaystyle t-1,}$ którego wartość np. w zerze jest równa sekretowi. Jako fragmenty sekretu udostępniane są wartości tego wielomianu w różnych punktach. Zebranie ${\displaystyle t}$ punktów pozwala dokonać interpolacji wielomianu i wyznaczyć jego wartość w zerze.

Operowanie zwykłymi wielomianami jest niepraktyczne – przy dużej losowości jego współczynników wartości w różnych punktach mogą zajmować sporo miejsca. Dlatego zwykle dla oszczędności definiuje się te wielomiany nad ciałami skończonymi, takimi jak np. liczby całkowite modulo p.

W ten sposób każdy fragment zajmuje tyle miejsca ile sekret, gdyż współrzędne ${\displaystyle x}$ dla kolejnych graczy mogą być jawne. Ilość losowych bitów potrzebnych do wygenerowania wielomianu również jest minimalna.

Protokół Blakleya

Dwie nierównoległe proste na płaszczyźnie przecinają się w jednym punkcie. Trzy płaszczyzny w przestrzeni również przecinają się w jednym punkcie. Ogólnie ${\displaystyle n}$ podprzestrzeni o kowymiarze ${\displaystyle 1}$ w ${\displaystyle n}$-wymiarowej przestrzeni wyznacza jeden punkt. Tajna informacja może zostać zakodowana jako jedna ze współrzędnych tego punktu. Jeśli byłaby zakodowana we wszystkich współrzędnych, wtedy posiadanie części fragmentów pozwalałoby wyznaczyć pewne zależności pomiędzy nimi, co oznaczałoby że protokół nie jest całkowicie bezpieczny.

Protokół Blakleya w trzech wymiarach. Każdy fragment jest płaszczyzną, tajna informacja jest ukryta w położeniu wspólnego punktu. Dwa fragmenty nie wystarczają do jego określenia, mogą jednak powiedzieć jak się mają do siebie współrzędne tego punktu (wyznaczają prostą na której on leży).

Protokół Blakleya w tej postaci zużywa więcej pamięci na przechowywanie sekretów niż protokół Shamira. Można jednak nałożyć dodatkowe warunki na postać fragmentów, uzyskując protokół równie efektywny do tamtego.

Rozwinięcia protokołu

Dając uczestnikom różne liczby fragmentów, możemy manipulować grupami które mogą odtworzyć sekret (przykładowo może to być dowolny zestaw akcjonariuszy posiadający 51% akcji). Bardziej skomplikowane podziały można uzyskać przez dzielenie fragmentów sekretu na kolejne sekrety.

Dzielenie sekretu często umożliwia łatwe dodawanie do siebie sekretów bez ich ujawniania, a przy dodatkowej wymianie informacji również ich mnożenie. Przy zastosowaniu weryfikowalnego dzielenia sekretu (VSS) stanowi to podstawę obliczeń wielopodmiotowych.