Teoria informacji/TI Ćwiczenia 6

From Studia Informatyczne

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 t z nich da się odtworzyć s, a dowolne t-1 z nich nie daje żadnych informacji o s. Taki podział nazywa się (t,n)-progowy.


Problem ten można rozwiązać przy użyciu protokołu Shamira. Dla uproszczenia dowodów załóżmy, że S jest jednostajnym rozkładem na \{0, \ldots, p-1\}, gdzie p jest liczbą pierwszą (a więc H(S)=\log p). Protokół wygląda następująco:

Protokół podziału sekretu
1. Losujemy t-1 liczb naturalnych x_1, \ldots, x_{t-1} \in \{0, \ldots, p-1\} (z rozkładu jednostajnego).
2. Wyliczamy wielomian P stopnia t-1 w ciele Z_p o wartościach:
P(0)=s, P(i)=x_i dla i=1, \ldots, t-1.
3. Przekazujemy uczestnikom fragmenty sekretu. Dla i \in \{1, \ldots, n\}. 
i-tym fragmentem sekretu jest s_i = P(i).


Ćwiczenie 1 [Poprawność]

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

Rozwiązanie

Przez t punktów przechodzi tylko jeden wielomian stopnia t-1. Przeprowadzenie zwykłej interpolacji pozwala odtworzyć postać wielomianu P, a więc też jego wartość w zerze - czyli sekret.


Ćwiczenie 2 [Tajność]

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

I(S;(S_{i_1}, \ldots, S_{i_t-1}))=0

Rozwiązanie

Przepiszmy to w następujący sposób

I(S;(S_{i_1}, \ldots, S_{i_t-1}))=H(S)-H(S|S_{i_1}, \ldots, S_{i_t-1})

Znając t-1 wartości wielomianu, możemy dla dowolnego x \in \{0, \ldots, p-1\} założyć, że P(0)=x i przeprowadzić interpolację, uzyskując wielomian stopnia t-1. Tym samym żadna wartość sekretu nie jest wykluczona ani preferowana, entropia warunkowa sekretu wynosi zaś \log p.

H(S)-H(S|S_{i_1}, \ldots, S_{i_t-1})=\log p - \log p = 0


Ćwiczenie 3 [Optymalność]

W protokole Shamira H(S_i)=\log p. Udowodnij, że jest to wartość optymalna, tzn. dla każdego protokołu podziału sekretu \forall_i H(S_i)\ge H(S).

Rozwiązanie

Z poprzednich dwóch ćwiczeń wiemy, że dla dowolnego zestawu i_1, \ldots, i_t \in \{1, \ldots, n\}

H(S|S_{i_1}, \ldots, S_{i_t-1})=H(S)

oraz

H(S|S_{i_1}, \ldots, S_{i_t})=0

Odejmując stronami po lewej stronie, dostaniemy dokładnie informację wzajemną S i S_{i_t} warunkowaną przez S_{i_1}, \ldots, S_{i_t-1}:

H(S) = H(S|S_{i_1}, \ldots, S_{i_t-1})-H(S|S_{i_1}, \ldots, S_{i_t}) = I(S,S_{i_t}|S_{i_1}, \ldots, S_{i_t-1})

Informacja wzajemna nie może być większa niż entropia żadnego ze składników, a więc

H(S_{i_t}) \ge I(S,S_{i_t}|S_{i_1}, \ldots, S_{i_t-1})

i ostatecznie

H(S_{i_t}) \ge H(S)


Ćwiczenie 4 [Dodawanie sekretów]

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

Rozwiązanie

Wystarczy że każdy uczestnik doda do siebie posiadane sekrety.