Teoria informacji/TI Ćwiczenia 6

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Protokół Shamira podziału sekretu

Problem podziału sekretu jest zdefiniowany następująco: pewną wiadomość s (sekret) pochodzącą z rozkładu S należy zaszyfrować w postaci n „fragmentów” w taki sposób, że przy użyciu dowolnych z nich da się odtworzyć s, a dowolne z nich nie daje żadnych informacji o s. Taki podział nazywa się -progowy.


Problem ten można rozwiązać przy użyciu protokołu Shamira. Dla uproszczenia dowodów załóżmy, że jest jednostajnym rozkładem na , gdzie jest liczbą pierwszą (a więc ). Protokół wygląda następująco:

Protokół podziału sekretu
1. Losujemy  liczb naturalnych  (z rozkładu jednostajnego).
2. Wyliczamy wielomian  stopnia  w ciele  o wartościach:
,  dla .
3. Przekazujemy uczestnikom fragmenty sekretu. Dla . 
i-tym fragmentem sekretu jest .


Ćwiczenie 1 [Poprawność]

Udowodnij, że dowolne fragmentów pozwala odtworzyć sekret .

Rozwiązanie


Ćwiczenie 2 [Tajność]

Niech będą zmiennymi losowymi określającymi rozkłady prawdopodobieństwa fragmentów . Udowodnij, że dowolne t-1 fragmentów nie daje żadnych informacji o s, czyli

Rozwiązanie


Ćwiczenie 3 [Optymalność]

W protokole Shamira . Udowodnij, że jest to wartość optymalna, tzn. dla każdego protokołu podziału sekretu .

Rozwiązanie


Ćwiczenie 4 [Dodawanie sekretów]

Załóżmy, że gracz A przeprowadził podział sekretu dla wiadomości , a gracz B podział sekretu dla wiadomości . Pokaż jak posiadacze fragmentów mogą uzyskać podział sumarycznej wiadomości , nie odtwarzając w tym celu i nie ujawniając nikomu żadnego z sekretów.

Rozwiązanie