SecretSharing PetrVeselý M0170 Kryptografie (454919) 13. 5. 2016 Osnova • Motivace • Sdílení mezi dvěma účastníky • Shamirovo (k, n)-prahové schéma • Blakleyho (k, n)-prahové schéma • Definice • Vlastnosti schémat • Hierarchická schémata • Tassovo schéma • Shrnutí Motivace Sdílení mezi dvěma účastníky  Tajemství S  𝑆 = 0100101011001011 0101001010100111  Naivní metoda  𝑇1 = 0100101011001011  𝑇2 = 0101001010100111 Sdílení mezi dvěma účastníky  Tajemství S  𝑆 = 0100101011001011 0101001010100111  Naivní metoda  𝑇1 = 0100101011001011  𝑇2 = 0101001010100111  Bezpečná metoda  𝑅 = 1101001011010100 1011010010010010  𝑇1 = R  𝑇2 = S ⊕ 𝑅  Zobecnění pro více účastníků... Shamirovo (k, n)- prahové schéma (1979) 0 1 2 3 4 0 1 2 3 4  Náhodný polynom st. k-1, konst. člen je tajemství  𝑓(𝑥) = 𝑎 𝑘−1 𝑥 𝑘−1 + ⋯ + 𝑎1 𝑥 + 𝑆  n účastníků dostane hodnoty 𝑓 1 , … 𝑓 𝑛  k hodnot jednoznačně určí polynom  V praxi se používá polynom nad 𝐺𝐹 𝑝 , 𝑝 > 𝑆.  Lagrangeova interpolace: Blakleyho (k, n)- prahové schéma (1979)  Bod A v k-rozměrném prostoru, jeho první souřadnice je tajemství S  𝐴 𝑆, 𝑎1, … , 𝑎 𝑘−1  n účastníků dostane n rovnic (vhodně vybraných) nadrovin, v jejichž průsečíku A leží  k nadrovin se protne v boduA Wikipedia Formální definice  Přístupová struktura (access structure)  Γ ⊆ 2 𝑃 , kde 𝑃 = 𝑝1, 𝑝2, … , 𝑝 𝑛  množina všech množin účastníků, které jsou schopné určit tajemství S  Monotónní přístupová struktura  𝐵 ⊆ C ∧ 𝐵 ∈ Γ ⇒ 𝐶 ∈ Γ  (k, n)-prahové schéma  Γ = 𝑀 ∈ 2 𝑃 ; 𝑀 ≥ 𝑘 Vlastnosti schémat sdílení tajemství  Perfektní bezpečnost (perfect secrecy)  P 𝑆 𝐵 ∉ Γ = P(𝑆)  Informační poměr (information rate)  𝜌 = log 𝑇 / log 𝑆  Ideální schéma (ideal scheme)  𝜌 = 1 Hierarchická schémata All animals are equal, but some are more equal than the others Prezident, dva ze tří generálů, tři z šesti plukovníků  (6, 10)-prahové schéma? Hierarchická schémata All animals are equal, but some are more equal than the others Prezident, dva ze tří generálů, tři z šesti plukovníků  Hierarchické prahové schéma  účastníci rozděleni do l disjunktních podskupin (úrovní), 𝑃 = 𝑖=1 𝑙 𝑈𝑖  je definována monotónní posloupnost prahů 0 < 𝑘1 < 𝑘2 < ⋯ < 𝑘𝑙.  Přístupová struktura je tvořena všemi množinami účastníků, v nichž je alespoň 𝑘𝑗 účastníků z 𝑖=1 𝑗 𝑈𝑖 pro každé 1 ≤ 𝑗 ≤ 𝑙, tedy 𝛤 = 𝑉 ⊆ 𝑃; 𝑉 ∩ ( 𝑗=1 𝑖 𝑈𝑗) ≥ 𝑘𝑖 ∀𝑖 ∈ {1, … , 𝑙 . Hierarchická schémata - naivní přístup All animals are equal, but some are more equal than the others Prezident, dva ze tří generálů, tři z šesti plukovníků Prezident 28 Generál 7 Plukovník 1  (45, 55)-prahové schéma?  Ito, Saito, Nishizeki [ISN89]: Pro každou monotónní přístupovou strukturu existuje takové rozdělení počtů podílů mezi účastníky, že počet podílů držených množinou účastníků dosáhne prahu pouze tehdy, je-li množina prvkem přístupové struktury Tassovo schéma  Hierarchické schéma podobné Shamirovu schématu  𝑓(𝑥) = 𝑎 𝑘−1 𝑥 𝑘−1 + ⋯ + 𝑎1 𝑥 + 𝑆 nad GF(p)  𝑈0, … , 𝑈 𝑚 hierarchie účastníků (disj. množiny)  0 < 𝑘0 < 𝑘2 < ⋯ < 𝑘 𝑚 = 𝑘 příslušné prahy  V každé úrovni 𝑈𝑖 dostane účastník 𝑢 podíl počítaný jako 𝑷(𝒌𝒊−𝟏) 𝒖 , kde 𝑃(𝑘𝑖−1) je 𝒌𝒊−𝟏-tá derivace  Příklad: 𝑘0 = 2, 𝑘1 = 4, 𝑘2 = 6  𝑈0 P(𝑢)  𝑈1 𝑃(2) (𝑢)  𝑈2 𝑃(4) (𝑢) Tassovo schéma – rekonstrukce tajemství  Birkhoffova interpolace  Definujme vektor... 𝒓 = (1; 𝑥, 𝑥2 , … , 𝑥 𝑘−1 )  ...a vektor koeficientů polynomu 𝑃 𝑥 𝒂 = 𝑆, 𝑎1, 𝑎2, … , 𝑎 𝑘−1  Podíl tajemství 𝑃(𝑘𝑖−1) 𝑢 je skalárním součinem vektoru 𝐫(𝑘𝑖−1) 𝑢 , který známe, a vektoru 𝐚, který chceme zjistit  To vede k řešení soustavy lineárních rovnic  Příklad: 𝑘0 = 2, 𝑘1 = 4, 𝑘2 = 6  𝒓 = (1; 𝑥, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 )  𝒓(𝟐) = (0, 0, 2, 6𝑥, 12𝑥2 , 20𝑥3 )  𝒓(𝟒) = (0, 0, 0, 0, 24, 120𝑥) Shrnutí  Existuje řada efektivních schémat sdílení tajemství  Prahová schémata, hierarchická schémata  Perfektní bezpečnost Zdroje  [Sha79] Adi Shamir. How to share a secret. In Commun. ACM, 22(11):612-613, 1979.  [Bla79] G R Blakley. Safeguarding cryptographic keys. In National Computer Conference Proceedings, vol 48, pages 313-317.AFIPS, 1979.  [ISN89] M. Ito, et al., Secret sharing scheme realizing general access structure. In Electronics and Communications inJapan (Part III: Fundamental Electronic Science), vol. 72, pp. 56-64, 1989.  [Tas07]TamirTassa. Hierarchical threshold secret sharing. In Journal of Cryptology, 20(2):237-264, 2007.