Teoria informacji/TI Ćwiczenia 6

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,\dots ,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,\dots ,x_{t-1}\in \{0,\dots ,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,\dots ,t-1$.
3. Przekazujemy uczestnikom fragmenty sekretu. Dla $i\in \{1,\dots ,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},\dots ,S_{i_t-1}))=0$

Rozwiązanie

Przepiszmy to w następujący sposób

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

Znając $t-1$ wartości wielomianu, możemy dla dowolnego $x\in \{0,\dots ,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},\dots ,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 ${\mathrm{\forall }}_{i}H(S_i)\ge H(S)$.

Rozwiązanie

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

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

oraz

$H(S|S_{i_1},\dots ,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},\dots ,S_{i_t-1}$:

$H(S)=H(S|S_{i_1},\dots ,S_{i_t-1})-H(S|S_{i_1},\dots ,S_{i_t})=I(S,S_{i_t}|S_{i_1},\dots ,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},\dots ,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.