Titkos megosztási sémák önkényes hozzáférési struktúrákhoz

Titkos megosztási sémák tetszőleges hozzáférési struktúrákhoz ( titkos megosztás általánosított hozzáférési struktúrával ) - titkos megosztási sémák , amelyek lehetővé teszik a résztvevők egy tetszőleges készletének megadását (minősített részhalmazok), amelyek képesek visszaállítani a titkot (hozzáférési struktúra).

Történelem

1979-ben Adi Shamir izraeli kriptoanalitikus egy titkos küszöbérték - megosztási rendszert javasolt a felek között, amely a következő tulajdonságokkal rendelkezik: $n$

A titok helyreállításához több oldal is elég. $k$
Egyetlen és kevesebb párt kaphat majd információt a titokról. [egy] $k-1$

Ez a megközelítés számos alkalmazást talált. Például többfelhasználós engedélyezéshez nyilvános kulcsú infrastruktúrában , digitális szteganográfiában digitális képekben lévő információk rejtett továbbítására, oldalcsatornás támadások elleni küzdelemre az AES algoritmus alkalmazásakor .

Az összetettebb alkalmazások azonban, ahol a résztvevők bizonyos csoportjai hozzáférhetnek, mások nem, nem férnek bele a küszöbséma modellbe. A probléma megoldására titkos megosztási sémákat fejlesztettek ki tetszőleges hozzáférési struktúrákhoz.

Mitsuro Ito, Akiro Saito és Takao Nishizeki japán tudósok voltak az elsők, akik az önkényes hozzáférési struktúrák titkos megosztását tanulmányozták, és 1987-ben javasolták a rendszerüket. [2] Gondolataikat Josh Benalo és Jerry Leichter dolgozta ki, akik 1988-ban egy elválasztási sémát javasoltak monoton szerkezetekre. [3] 1989-ben Ernest Brickell egy olyan sémát javasolt, amelyben a résztvevők nem részesedést kapnak a titokból, hanem azok lineáris kombinációit. [négy]

A használt kifejezések meghatározása

A kereskedő egy eljárás (protokoll) résztvevője, aki a titok ismeretében kiszámítja a titok részesedését, és ezeket a részesedéseket szétosztja a többi résztvevő között.

A minősített részhalmaz azon csoporttagok halmaza, amelyek számára engedélyezett a titkos helyreállítás.

A minősített részhalmazok megjelenését illusztráló példa egy titok megosztása a vezetők között. Abban az esetben, ha a titkot mindhárom ügyvezető, vagy bármely ügyvezető és bármely alelnök, vagy egyedül az elnök vissza tudja szerezni, [1] a minősített részhalmazok az elnök, az alelnök és az ügyvezető, vagy bármely három. vezetők.

A hozzáférési struktúra minősített és minősítetlen részhalmazok felsorolása.

Legyen a csoporttagok halmaza, a csoporttagok száma, és egy halmaz, amely a csoporttagok összes lehetséges részhalmazából áll. Legyen egy halmaz a résztvevők részhalmazaiból, akik jogosultak a titkot visszaállítani (a résztvevők minősített halmazai), a résztvevők részhalmazaiból álló halmaz, amely nem tudja visszaállítani a titkot. Egy hozzáférési struktúra jelölése ( , ) . $A$ $n$ $2^{[n]}$ $\Gamma$ $\Delta$ $\Gamma$ $\Delta$

Egy hozzáférési struktúrát monotonnak mondunk , ha a minősített részhalmazok összes szuperhalmazát is tartalmazza , azaz. $\Gamma$ $A\in \Gamma ,A\subseteq B\subseteq P\Rightarrow B\in \Gamma$

Tegyük fel , hogy ( , ) $\Gamma$ $\Delta$ egy hozzáférési struktúra a következőn . minimum minősített részhalmazának nevezzük , ha mindig, amikor . A minimális minősített részhalmazok halmazát bázisnak nevezzük és nevezzük . A minimális minősített részhalmaz egyedileg határozza meg a hozzáférési struktúrát. $A$ $B\in \Gamma$ $C\not \in \Gamma$ $C\subset B$ $\Gamma$ $\Gamma _{min}$ $\Gamma$

Benalo-Leichter séma

Legyen adott egy monoton hozzáférési struktúra, és legyen a -nek megfelelő minimális minősített részhalmazok halmaza . Hadd . Mindegyik esetében a rendszer kiszámítja a titkos megosztásokat ennek az alhalmaznak a tagjai számára a tetszőleges küszöbű titkos megosztási séma használatával. $A$ $\Gamma _{min}$ $A$ $\Gamma _{min}=\{A_{1},A_{2},...,A_{m}\}$ $A_{i}$ $s_{i1},s_{i2},...,s_{i|A|}$ $(|A_{i}|,|A_{i}|)$

A titok része a megfelelő résztvevőnek kerül átadásra. Ennek eredményeként minden résztvevő titkos megosztásokat kap. A titok visszaállítása a kiválasztott (n, n) - küszöb séma szerint történik . [3] $s_{i,j}$

Példa:

${\displaystyle \Gamma _{min}=\{\{1,2,3\},\{1,4\},\{2,4\},\{3,4\}\))$

$A_{1}=\{1,2,3\}\ \ \ \ \ \ A_{2}=\{1,4\}\ \ \ \ \ A_{3}=\{2,4\ }\ \ \ \ \ A_{4}=\{3,4\}$

Itt van például a második a -ban , tehát megkapja a titok megosztásait $P_{4}$ ${\displaystyle A_{2},A_{3},A_{4))$ ${\displaystyle s_{2,2},s_{3,2},s_{4,2))$

Hasonlóképpen a többi résztvevő esetében is

$P_{1}\leftarrow s_{1,1},s_{2,1}\ \ P_{2}\leftarrow s_{1,2},s_{3,1}\ \ P_{3}\ balra nyíl s_{1,3},s_{4,1}\ \$

Ennek a sémának az a hátránya, hogy az egyes résztvevők számára növekvő titkos megosztások mennyisége növekszik [5] [6] . $\Gamma _{min}$

Ito-Saito-Nishizeki séma

Ito, Saito, Nishizeki bevezette az úgynevezett kumulatív tömb technikát a monoton hozzáférési struktúrához. [2]

Legyen egy monoton méretű hozzáférési struktúra, és legyen az ennek megfelelő résztvevők maximális minősíthetetlen részhalmazai. $A$ $n$ ${\displaystyle A_{1},...,A_{m))$

A hozzáférési struktúra kumulatív tömbje egy dimenziók mátrixa , ahol és jelölése . Vagyis a mátrix oszlopai minősítetlen részhalmazoknak felelnek meg, és az oszlopon belüli sorok értéke egy lesz, ha az elem nem szerepel ebben a részhalmazban. $A$ $n\szer m$ ${\displaystyle (C_{i,j}^{A})_{1\leq i\leq n,1\leq j\leq m))$ $C_{i,j}^{A}={\begin{cases}0,&{\text{if }}i\in A_{j}\\1,&{\text{if }}i \nem \in A_{j}\end{cases}}$ $C^{A}$

Ebben a sémában bármilyen - küszöbértékű titkos megosztási sémát használhat egy titokkal és a megfelelő megosztásokkal ${\megjelenítési stílus (m, m)}$ $S$ ${\displaystyle s_{1},...,s_{m))$

A titoknak megfelelő megosztások egy halmazként lesznek meghatározva : $I_{1},...,I_{n}$ $S$ $s_{j}$ ${\displaystyle I_{i}=\{s_{j}|C_{i,j}^{A}=1\))$

A titok visszaállítása a kiválasztott küszöbséma szerint történik . ${\megjelenítési stílus (m, m)}$

E rendszer végrehajtásának 2016-ban elért összetettsége . [7] $Tovább)$

Példa:

Hagyjuk , . $n=4$ $\Gamma =\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3, 4\},\{2,3,4\}\}$

A minimális minősített részhalmazok megfelelő halmaza $A$ ${\displaystyle \Gamma _{min}=\{\{1,2\},\{3,4\}\))$

Ebben az esetben és . ${\displaystyle \Delta _{max}=\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\))$ $m=4$

A hozzáférési struktúra kumulatív tömbjének alakja van $A$ $C^{A}={\begin{pmatrix}0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\end{pmatrix}}$

A résztvevők titkának megosztása egyenlő $I_{1}=\{s_{3},s_{4}\};\ \ I_{2}=\{s_{1},s_{2}\};\ \ I_{3}= \{s_{2},s_{4}\};\ \ I_{4}=\{s_{1},s_{3}\}$

A titkos helyreállítás hasonló a titkos helyreállításhoz Shamir küszöbrendszerében. $(4,4)$

Brickell lineáris diagramja a titkos megosztásról

A hozzáférési struktúrához és a tagkészlethez méretmátrix készül , amelyben a hosszúságú karakterlánc hozzá van rendelve a taghoz . A résztvevők azon részhalmazára , amely megfelel a mátrix- sorok halmazának, teljesülnie kell annak a feltételnek, hogy a vektor a - kal átívelt lineáris tartományhoz tartozik . $A$ $P=\{P_{1},...,P_{n}\}$ $M$ $n\szer m$ $M[i]$ $m$ $én$ $x\subset \Gamma$ $M$ $M_{x}$ $(1,0,...,0)$ $M_{x}$

Az osztó kiválaszt egy vektort, ahol a megosztott titok van . A résztvevő titkos megosztása : $r=(r_{0},...,r_{m})$ ${\displaystyle s=r_{0))$ $én$ $s_{i}=M[i]r$

Titkos gyógyulás.

Ki kell választani egy vektort, amelynek hossza , — a résztvevők halmazának megfelelő koordinátákból álló vektor . $\alpha$ $m$ $\alpha _{x}$ $\alpha$ $x\subset \Gamma$

Minden feltételnek teljesülnie kell: . Ezután a titok visszaállítható a következő képlettel: $x\subset \Gamma$ $\alpha _{x}M_{x}=(1,0,....,0)$

$\sum _{i\in x}s_{i}\alpha _{i}=\sum _{i\in x}(M[i]r)\alpha _{i}=(\sum _ {i\in x}\alpha _{i}M[i])r=(1,0,...,0)r=s$ [négy]

Példa:

A minimális minősített részhalmazok halmaza . $\Gamma =\{\{1,2,3\},\{1,4\}\}$

Megfelelő mátrix:

${\begin{pmatrix}0&1&0\\1&0&1\\0&1&-1\\1&1&0\end{pmatrix}}$

$M$ kielégíti a sémakövetelményt:

számára : $\{1, 2, 3\}$ $(1,0,0)=-(0,1,0)+(1,0,1)+(0,1,-1)$

számára : $\{1,4\}$ $(1,0,0)=-(0,1,0)+(1,1,0)$

Minden résztvevő megosztja a titkot:

$P_{1}\leftarrow r_{1};\qquad P_{2}\leftarrow s+r_{2};\qquad P_{3}\leftarrow r_{1}-r_{2};\qquad P_ {4}\leftarrow s+r_{1}\qquad$

Titkos helyreállítás:

A titok visszaállításához válassza a lehetőséget $\alpha =(-1,1,1,1)$

Akkor ehhez : $x=\{1,2,3\}$ $\alpha _{x}=(-1,1,1)$

$(-1,1,1){\begin{pmatrix}0&1&0\\1&0&1\\0&1&-1\end{pmatrix}}=(1,0,0)$

És ehhez : $x=\{1,4\}$ $\alpha _{x}=(-1,1)$

$(-1,1){\begin{pmatrix}0&1&0\\1&1&0\end{pmatrix}}=(1,0,0)$

Alkalmazás

Ezeket a sémákat feltételes titkosítási (CDS) protokollokban [8] , biztonságos elosztott számítástechnikában [9] [10] [11] , kulcselosztási problémákban [12] és többszörös vevő hitelesítési sémákban [13] használják .

Jegyzetek

↑ 1 2 Shamir A. Hogyan osszunk meg egy titkot // Commun. ACM – NYC, USA. - 1979. - T. 22 . - S. 612-613 .
↑ 1 2 Ito M., Saito A., Nishizeki T. Az általános hozzáférési struktúrát megvalósító titkos megosztási séma // Electronics and Communications in Japan (III. rész: Fundamental Electronic Science). - 1987. Archiválva : 2021. április 23.
↑ 1 2 Benaloh J., Leichter J. Generalized Secret Sharing and Monotone Functions // Advances in Cryptology - CRYPTO' 88. - 1988. - S. 27-35 .
↑ 1 2 Brickell EF Néhány ideális titkos megosztási séma // Journal of Combin. Math. és kombináljuk. Comput. nem. 9. - 1989. - S. 105-113 .
↑ Sreekumar A., Babusundar S. Titkos megosztási sémák vizuális kriptográfiával // Cochin Tudományos és Technológiai Egyetem. – 2009.
↑ Kouya TOCHIKUBO. Titkos megosztási sémák felépítési módszere engedélyezett részhalmazokon // Nemzetközi információelmélet és alkalmazásai szimpózium. – 2008.
↑ Lein Harna, Hsu Chingfang, Zhang Mingwua, He Tingtingc, Zhang Maoyuanc. Titkos megosztás megvalósítása általános hozzáférési struktúrával // Information Sciences. - 2016. - 367–368. sz . - S. 209-220 .
↑ Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T. Adatvédelem védelme privát információkeresési sémákban // Journal of Computer and System Sciences. - 2000. - 60. (3) bek . – S. 592–629 .
↑ Ben-Or, M., Goldwasser, S., Wigderson, A. Teljességi tételek nem titkosított hibatűrő elosztott számításokhoz. In: Proceedings of the 20th year ACM symposium on Theory of Computing // ACM Press. - 1998. - S. 1-10 .
↑ Cramer, R., Damg˚ard, I., Maurer, U. General biztonságos többpárti számítást bármilyen lineáris titokmegosztási sémából. // Preneel, B. (szerk.) EUROCRYPT 2000. - T. 1807 . – S. 316–334 .
↑ Cramer, R., Damg˚ard, I., Nielsen, J.B. Secure Multiparty Computation and Secret Sharing: An Information Theoretic Approach. . (nem elérhető link)
↑ Lee, C.-Y., Wang, Z.-H., Harn, L., Chang, C.-C. Biztonságos kulcsátviteli protokoll titkos megosztáson alapuló csoportos kommunikációhoz // IEICE Trans. inf. és Syst.. - 2011. - S. 2069–2076 .
↑ Zhang, J., Li, X., Fu, F.-W. Multi-receiver autentikációs séma több üzenethez lineáris kódok alapján // Huang, X., Zhou, J. (eds.) ISPEC 2014. LNCS. - 2014. - T. 8434 . – S. 287–301 .