Šamirovo sdílení tajemství

Šamirovo schéma pro sdílení tajemství je kryptografický algoritmus. Je to forma sdílení tajné informace, kdy je tato informace rozdělena do částí (každému účastníku je přidělena jedinečná část) a pro rekonstrukci původní informace je třeba alespoň určitý počet z dílčích částí. Izraelský matematik Adi Šamir jej formuloval v roce 1979

Našim cílem je rozdělit nějaká data ${\displaystyle D}$ do ${\displaystyle n\,\!}$ částí${\displaystyle D_{1},\ldots ,D_{n}\,\!}$ tak, že:

1. Znalost některých ${\displaystyle k\,\!}$ nebo více ${\displaystyle D_{i}\,\!}$ částí zajistí snadné zjištění ${\displaystyle D\,\!}$ .
2. Znalost některých ${\displaystyle k-1\,\!}$ nebo méně ${\displaystyle D_{i}\,\!}$ částí ponechá ${\displaystyle D\,\!}$ zcela neurčená (ve smyslu, že všechny hodnoty jsou stejně možné).

Toto schéma nazýváme ${\displaystyle \left(k,n\right)\,\!}$ prahové schéma. Pokud ${\displaystyle k=n\,\!}$, všichni účastníci jsou třeba k rekonstrukci tajemství.

Předpokládejme, že chceme užít ${\displaystyle \left(k,n\right)\,\!}$ prahové schéma pro sdílení tajemství ${\displaystyle S\!}$. Bez újmy na obecnosti předpokládejme, že ${\displaystyle S\!}$ je prvkem konečného tělesa ${\displaystyle F\!}$ velikosti ${\displaystyle P}$ kde ${\displaystyle 0<k\leq n<P;S<P}$ a zároveň je ${\displaystyle P}$ prvočíslo.

Náhodně vybereme ${\displaystyle k-1\!}$ koeficientů ${\displaystyle a_{1},\ldots ,a_{k-1}\in F\!}$. Dále ${\displaystyle a_{0}=S.\!}$ Sestavíme polynom ${\displaystyle f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!}$. Dále vypočítáme souřadnice ${\displaystyle n\,\!}$ bodů tohoto polynomu. Například pro ${\displaystyle i=1,\ldots ,n\!}$ získáme ${\displaystyle n\!}$ bodů ve tvaru ${\displaystyle \left[i,f\left(i\right)\right].\!}$

Tyto souřadnice jsou rozděleny mezi ${\displaystyle n,\!}$ účastníků. Jelikož je polynom stupně ${\displaystyle k-1\!}$ určen jednoznačně ${\displaystyle k\!}$ body, z jakékoliv ${\displaystyle k\!}$-prvkové podmnožiny bodů lze jednoznačně pomocí interpolace určit koeficienty polynomu ${\displaystyle f,\!}$ a tedy i tajemství ${\displaystyle S=a_{0}.\!}$

• SHAMIR, Adi. How to share a secret. Communications of the ACM. 1979, roč. 22, čís. 11, s. 612–613. 

V tomto článku byl použit překlad textu z článku Shamir's Secret Sharing na anglické Wikipedii.