Teoria informacji/TI Ćwiczenia 6: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
następna edycja →
WizualnieWikikod
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
 
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
Linia 8: Linia 8:


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


  '''Protokół podziału sekretu'''
  '''Protokół podziału sekretu'''
  1. Losujemy <math>t-1</math> liczb naturalnych <math>x_1, \ldots, x_{t-1} \in \{1, \ldots, p\}</math> (z rozkładu jednostajnego).
  1. Losujemy <math>t-1</math> liczb naturalnych <math>x_1, \ldots, x_{t-1} \in \{0, \ldots, p-1\}</math> (z rozkładu jednostajnego).
  2. Wyliczamy wielomian <math>P</math> stopnia <math>t-1</math> w ciele <math>Z_p</math> o wartościach:
  2. Wyliczamy wielomian <math>P</math> stopnia <math>t-1</math> w ciele <math>Z_p</math> o wartościach:
  <math>P(0)=s</math>, <math>P(i)=x_i</math> dla <math>i=1, \ldots, t-1</math>.
  <math>P(0)=s</math>, <math>P(i)=x_i</math> dla <math>i=1, \ldots, t-1</math>.
Linia 42: Linia 42:
<center><math>I(S;(S_{i_1}, \ldots, S_{i_t-1}))=H(S)-H(S|S_{i_1}, \ldots, S_{i_t-1})</math></center>
<center><math>I(S;(S_{i_1}, \ldots, S_{i_t-1}))=H(S)-H(S|S_{i_1}, \ldots, S_{i_t-1})</math></center>


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


Informacja wzajemna nie może być mniejsza niż entropia żadnego ze składników, a więc
Informacja wzajemna nie może być większa niż entropia żadnego ze składników, a więc
<center><math>H(S_{i_t}) \ge I(S,S_{i_t}|S_{i_1}, \ldots, S_{i_t-1}) </math></center>
<center><math>H(S_{i_t}) \ge I(S,S_{i_t}|S_{i_1}, \ldots, S_{i_t-1}) </math></center>


Wersja z 08:49, 18 sie 2006

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,…,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 x1,…,xt−1∈{0,…,p−1} (z rozkładu jednostajnego).
2. Wyliczamy wielomian P stopnia t−1 w ciele Zp o wartościach:
P(0)=s, P(i)=xi dla i=1,…,t−1.
3. Przekazujemy uczestnikom fragmenty sekretu. Dla i∈{1,…,n}. 
i-tym fragmentem sekretu jest si=P(i).


Ćwiczenie 1 [Poprawność]

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

Rozwiązanie

{{{3}}}


Ćwiczenie 2 [Tajność]

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

I(S;(Si1,…,Sit−1))=0

Rozwiązanie

{{{3}}}


Ćwiczenie 3 [Optymalność]

W protokole Shamira H(Si)=log⁡p. Udowodnij że jest to wartość optymalna, tzn. dla każdego protokołu podziału sekretu ∀iH(Si)≥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}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_6&oldid=20223”