Salaiset jakamisjärjestelmät mielivaltaisille pääsyrakenteille

Salaiset jakamisjärjestelmät mielivaltaisille pääsyrakenteille (esim. Salainen jakaminen yleisellä käyttöoikeusrakenteella ) - salainen jakamisjärjestelmä, jonka avulla voit määrittää mielivaltaisen joukon osallistujaryhmiä (hyväksytyt osajoukot), joilla on mahdollisuus palauttaa salaisuus (käyttöoikeusrakenne).

Historia

Vuonna 1979 israelilainen kryptanalyytikko Adi Shamir ehdotti osapuolten välistä kynnyksen salaista jakamisjärjestelmää, jolla on seuraavat ominaisuudet: $n$

Salaisuuden palauttamiseksi riittää useampi kuin yksi puoli. $k$
Yksikään ja harvempi osapuoli voi saada mitään tietoa salaisuudesta. [yksi] $k-1$

Tämä lähestymistapa on löytänyt monia sovelluksia. Esimerkiksi usean käyttäjän valtuutus julkisen avaimen infrastruktuurissa , digitaalisessa steganografiassa digitaalisten kuvien salaiseen siirtämiseen, sivukanavahyökkäysten torjumiseksi AES - algoritmia toteutettaessa .

Monimutkaisemmat sovellukset, joihin tietyt osallistujaryhmät voivat päästä ja toiset eivät, eivät kuitenkaan sovi kynnysmalliin. Tämän ongelman ratkaisemiseksi on kehitetty salaisia jakamisjärjestelmiä mielivaltaisille pääsyrakenteille.

Japanilaiset tiedemiehet Mitsuro Ito, Akiro Saito ja Takao Nishizeki olivat ensimmäisiä, jotka tutkivat mielivaltaisten pääsyrakenteiden salaista jakamista ja ehdottivat vuonna 1987 heidän suunnitelmaansa. [2] Heidän ajatuksensa kehittivät Josh Benalo ja Jerry Leichter, jotka ehdottivat vuonna 1988 erottelujärjestelmää monotonisille rakenteille. [3] Vuonna 1989 Ernest Brickell ehdotti järjestelmää, jossa osallistujille ei anneta salaisuuden osuuksia, vaan niiden lineaariset yhdistelmät. [neljä]

Käytettyjen termien määritelmä

Jälleenmyyjä on menettelyn (protokollan) osallistuja, joka salaisuuden tunteessaan laskee salaisuuden osuudet ja jakaa nämä osuudet muille osallistujille.

Hyväksytty osajoukko on joukko ryhmän jäseniä, joille salainen palautus on sallittu.

Esimerkki pätevien osajoukkojen syntymisestä on salaisuuden jakaminen johtajien kesken. Jos salaisuuden voivat palauttaa joko kaikki kolme johtajaa tai mikä tahansa johtaja ja mikä tahansa varapresidentti tai presidentti yksin [1] , päteviä osajoukkoja ovat presidentti, varapresidentti ja johtaja tai mitkä tahansa kolme johtajat.

Käyttöoikeusrakenne on luettelo hyväksytyistä ja määrittelemättömistä osajoukoista.

Antaa olla joukko ryhmän jäseniä, olla ryhmän jäsenten lukumäärä ja olla joukko, joka koostuu kaikista mahdollisista ryhmän jäsenten osajoukoista. Olkoon joukko, joka koostuu osallistujien osajoukoista, jotka saavat palauttaa salaisuuden (osallistujien hyväksytyt joukot), joukko, joka koostuu osallistujien osajoukoista, jotka eivät voi palauttaa salaisuutta. Käyttöoikeusrakenne on merkitty ( , ) . $A$ $n$ $2^{[n]}$ $\Gamma$ $\Delta$ $\Gamma$ $\Delta$

Pääsyrakenteen sanotaan olevan monotoninen , jos kaikki hyväksyttyjen osajoukkojen superjoukot ovat myös mukana , ts. $\Gamma$ $A\in \Gamma ,A\subseteq B\subseteq P\Rightarrow B\in \Gamma$

Oletetaan ( , ) on $\Gamma$ $\Delta$ käyttöoikeusrakenne . kutsutaan vähimmäishyväksytyksi osajoukoksi , jos aina, milloin . Vähimmäishyväksyttyjen osajoukkojen joukkoa kutsutaan ja sitä kutsutaan perustaksi . Vähimmäishyväksytty osajoukko määrittää käyttöoikeusrakenteen yksilöllisesti. $A$ $B\in \Gamma$ $C\not \in \Gamma$ $C\subset B$ $\Gamma$ $\Gamma _{min}$ $\Gamma$

Scheme of Benalo-Leichter

Olkoon monotoninen pääsyrakenne annettu ja se on joukko vähimmäiskelpoisia osajoukkoja, jotka vastaavat . Anna . Jokaiselle :lle lasketaan salaiset osuudet tämän osajoukon jäsenille käyttämällä minkä tahansa kynnyksen salaista jakamisjärjestelmää. $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}|)$

Osuus salaisuudesta siirretään asianmukaiselle osallistujalle. Tämän seurauksena jokainen osallistuja saa joukon salaisia osuuksia. Salaisuus palautetaan valitun (n, n) - kynnyskaavion mukaisesti . [3] ${\näyttötyyli s_{i,j))$

Esimerkki:

${\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\}$

Tässä on esimerkiksi toinen , joten se saa osuudet salaisuudesta $P_{4}$ ${\displaystyle A_{2},A_{3},A_{4))$ ${\displaystyle s_{2,2},s_{3,2},s_{4,2))$

Samoin muille osallistujille

$P_{1}\leftarrow s_{1,1},s_{2,1}\ \ P_{2}\leftarrow s_{1,2},s_{3,1}\ \ P_{3}\ vasen nuoli s_{1,3},s_{4,1}\ \$

Tämän järjestelmän haittana on, että salaisten osuuksien määrä lisääntyy jokaiselle osallistujalle [5] [6] . $\Gamma _{min}$

Ito-Saito-Nishizekin kaava

Ito, Saito, Nishizeki esitteli niin sanotun kumulatiivisen matriisitekniikan monotoniselle pääsyrakenteelle. [2]

Antaa olla monotoninen pääsyrakenne kooltaan ja antaa olla sitä vastaavien osallistujien enimmäismäärät. $A$ $n$ ${\displaystyle A_{1},...,A_{m))$

Käyttöoikeusrakenteen kumulatiivinen matriisi on dimensioiden matriisi , jossa ja on merkitty muodossa . Toisin sanoen matriisin sarakkeet vastaavat määrittelemättömiä osajoukkoja, ja sarakkeen sisällä olevien rivien arvo on yksi, jos elementti ei sisälly tähän osajoukkoon. $A$ $n\ kertaa m$ ${\näyttötyyli (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 \not \in A_{j}\end{cases}}$ $C^{A}$

Tässä järjestelmässä voit käyttää mitä tahansa - kynnyksen salaista jakamisjärjestelmää salaisuuden ja sitä vastaavien osuuksien kanssa ${\näyttötyyli (m, m)}$ $S$ ${\displaystyle s_{1},...,s_{m))$

Salaisuutta vastaavat osuudet määritellään sarjaksi : $I_{1},...,I_{n}$ $S$ $s_{j}$ ${\displaystyle I_{i}=\{s_{j}|C_{i,j}^{A}=1\))$

Salaisuus palautetaan valitun kynnyskaavion mukaisesti . ${\näyttötyyli (m, m)}$

Tämän vuonna 2016 saavutetun järjestelmän täytäntöönpanon monimutkaisuus on . [7] $Päällä)$

Esimerkki:

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

Vastaava joukko vähimmäishyväksyttyjä osajoukkoja $A$ ${\displaystyle \Gamma _{min}=\{\{1,2\},\{3,4\}\))$

Tässä tapauksessa ja . ${\displaystyle \Delta _{max}=\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\))$ $m = 4$

Käyttöoikeusrakenteen kumulatiivisella taulukolla on muoto $A$ $C^{A}={\begin{pmatrix}0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\end{pmatrix}}$

Osallistujien osuudet salaisuudesta ovat yhtä suuret $I_{1}=\{s_{3},s_{4}\};\ \ I_{2}=\{s_{1},s_{2}\};\ \ I_{3}= \{s_{2},s_{4}\};\ \ I_{4}=\{s_{1},s_{3}\}$

Salainen palautus on samanlainen kuin Shamirin kynnysjärjestelmän salainen palautuminen. ${\näyttötyyli (4,4)}$

Brickellin lineaarinen kaavio salaisesta jakamisesta

Pääsyrakenteelle ja jäsenjoukolle muodostetaan kokomatriisi , jossa pituusmerkkijono liittyy jäseneen . Osallistujien osajoukolle , joka vastaa matriisin - rivien joukkoa , ehdon tulee täyttyä, että vektori kuuluu lineaariseen jänneväliin, jonka kattaa . $A$ $P=\{P_{1},...,P_{n}\}$ $M$ $n\ kertaa m$ $M[i]$ $m$ $i$ $x\subset \Gamma$ $M$ $M_{x}$ ${\näyttötyyli (1,0,...,0)}$ $M_{x}$

Jakaja valitsee vektorin , jossa jaettu salaisuus on . Osallistujan salainen osuus : $r=(r_{0},...,r_{m})$ $s=r_{0}$ $i$ $s_{i}=M[i]r$

Salainen toipuminen.

Valitaan vektori , jonka pituus on , — vektori, joka koostuu osallistujajoukkoa vastaavista koordinaateista . $\alpha$ $m$ $\alpha _{x}$ $\alpha$ $x\subset \Gamma$

Jokaisen ehdon on täytyttävä: . Sitten salaisuus voidaan palauttaa kaavalla: $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$ [neljä]

Esimerkki:

Vähimmäishyväksyttyjen osajoukkojen joukko . ${\displaystyle \Gamma =\{\{1,2,3\},\{1,4\}\))$

Sopiva matriisi:

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

$M$ täyttää kaavavaatimuksen:

Käyttäjälle : $\{1, 2, 3\}$ $(1,0,0)=-(0,1,0)+(1,0,1)+(0,1,-1)$

Käyttäjälle : $\{1,4\}$ $(1,0,0)=-(0,1,0)+(1,1,0)$

Jokaisen osallistujan salaisuudet:

$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$

Salainen palautus:

Palauta salaisuus valitsemalla $\alpha =(-1,1,1,1)$

Sitten : $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)$

Ja varten : $x=\{1,4\}$ $\alpha _{x}=(-1,1)$

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

Sovellus

Näitä järjestelmiä käytetään ehdollisen salaisuuksien paljastamisen (CDS) protokollissa [8] , suojatussa hajautetussa tietojenkäsittelyssä [9] [10] [11] , avainten jakeluongelmissa [12] ja useiden vastaanottimien todennusmenetelmissä [13] .

Muistiinpanot

↑ 1 2 Shamir A. Kuinka jakaa salaisuus // Commun. ACM – NYC, USA. - 1979. - T. 22 . - S. 612-613 .
↑ 1 2 Ito M., Saito A., Nishizeki T. Salainen jakamisjärjestelmä yleisen pääsyrakenteen toteuttamiseksi // Elektroniikka ja viestintä Japanissa (Osa III: Elektroniikan perustiede). - 1987. Arkistoitu 23. huhtikuuta 2021.
↑ 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 Joitakin ihanteellisia salaisia jakamisjärjestelmiä // Journal of Combin. Matematiikka. ja yhdistä. Comput. ei. 9. - 1989. - S. 105-113 .
↑ Sreekumar A., Babusundar S. Salaiset jakamisjärjestelmät visuaalista kryptografiaa käyttämällä // Cochinin tiede- ja teknologiayliopisto. – 2009.
↑ Kouya TOCHIKUBO. Valtuutettuihin osajoukkoon perustuvien salaisten jakamisjärjestelmien rakentamismenetelmä // Kansainvälinen symposium informaatioteoriasta ja sen sovelluksista. – 2008.
↑ Lein Harna, Hsu Chingfang, Zhang Mingwua, He Tingtingc, Zhang Maoyuanc. Salaisen jakamisen toteuttaminen yleisen käyttöoikeusrakenteen kanssa // Tietotieteet. - 2016. - Nro 367–368 . - S. 209-220 .
↑ Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T. Tietosuojan suojaaminen yksityisissä tiedonhakujärjestelmissä // Journal of Computer and System Sciences. - 2000. - Nro 60(3) . — S. 592–629 .
↑ Ben-Or, M., Goldwasser, S., Wigderson, A. Täydellisyyslauseet ei-skriptografiseen vikasietoiseen hajautettuun laskentaan. Julkaisussa: 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 turvaa monen osapuolen laskennan mistä tahansa lineaarisesta salaisuuden jakamisjärjestelmästä. // Preneel, B. (toim.) 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. . (linkki ei saatavilla)
↑ Lee, C.-Y., Wang, Z.-H., Harn, L., Chang, C.-C. Suojattu avainten siirtoprotokolla, joka perustuu salaiseen jakamiseen ryhmäviestintää varten // IEICE Trans. inf. ja Syst.. - 2011. - S. 2069–2076 .
↑ Zhang, J., Li, X., Fu, F.-W. Monen vastaanottimen todennusjärjestelmä useille viesteille, jotka perustuvat lineaarisiin koodeihin // Huang, X., Zhou, J. (toim.) ISPEC 2014. LNCS. - 2014. - T. 8434 . — S. 287–301 .