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

{{{3}}}

Ć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

{{{3}}}

Ć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

{{{3}}}