Ihanteellinen ristikko

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.9.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Ihanteellinen hila on tietty matemaattinen rakenne , jota käytetään vähentämään hilan (jotka ovat vapaita kommutatiivisia äärellisen järjestyksen ryhmiä) kuvaamiseen tarvittavien parametrien määrää . Tämän tyyppinen hila löytyy usein monilta matematiikan aloilta, erityisesti lukuteorian osiosta . Siten ihanteelliset hilat ovat tehokkaampia käyttää kuin muut kryptografiassa käytettävät hilat . Ihanteellisia hiloja käytetään julkisen avaimen NTRUEncrypt ja NTRUSign salausjärjestelmissä tehokkaiden salausprimitiivien rakentamiseen . Ihanteelliset hilat muodostavat myös kvanttisalauksen perustan , joka suojaa kvanttitietokoneisiin liittyviltä hyökkäyksiltä.

Johdanto

RSA- ja ECC - järjestelmät , jotka perustuvat joko tekijöiden jakamisen tai diskreetin logaritmiongelman monimutkaisuuteen , ovat suosituimpia epäsymmetrisiä salausjärjestelmiä, jotka käyttävät eri avaimia tiedon salaamiseen ja sen jälkeen sen salauksen purkamiseen. Huolimatta RSA- ja ECC -järjestelmien hallitsevuudesta , niiden tiedetään olevan herkkiä kvanttitietokoneita käyttäville hyökkäyksille [1] . Lisäksi RSA ja ECC ovat melko tehottomia hyvin pienissä ja rajoitetuissa laitteissa, kuten 8-bittiset AVR -mikro-ohjaimet , joita käytetään tähän päivään eri aloilla, kuten robotiikassa , energiassa, satelliittiviestintäjärjestelmissä ja monilla muilla. Mahdollinen vaihtoehto yllä oleville kaavioille ovat epäsymmetriset salausjärjestelmät, jotka perustuvat ihanteellisten hilan koviin ongelmiin [2] . Ideaalihilojen erityinen algebrallinen rakenne voi merkittävästi pienentää avaimen ja salatekstin kokoa samalla kun se tarjoaa tehokkaan aritmeettisen lukuteoreettisen muunnoksen avulla. Näin ollen ideaalihilojen käytön ansiosta salatun tiedon suojausaste kasvaa [3] .

Peruskäsitteet

Hilateoria voidaan kuvata lineaarisen algebran avulla . Hila nähdään yleensä minkä tahansa tasaisesti jakautuneena pisteiden ruudukkona n-ulotteisessa todellisessa lineaarisessa avaruudessa , jonka kaikki koordinaatit ovat kokonaislukuja . Tämä joukko muodostaa ryhmän koordinaattien päälle lisättynä ja on diskreetti , mikä tarkoittaa, että jokaisella joukon pisteellä on sen ympärillä avoin pallo , joka ei sisällä muita pisteitä joukossa , joten hila on kaikkien lineaaristen kokonaislukujen joukko. yhdistelmät tietyistä lineaarisesti riippumattomien pisteiden joukosta . Hilat ovat ryhmiä ja ideaaliset hilat ovat ihanteita [4] . $R^{n}$ ${\displaystyle Z^{n))$

Erityisesti ideaaliset hilat vastaavat muodon renkaita jollekin redusoitumattomalle astepolynomille [ 5] . Ihanteellisen hilakalastuksen perustoiminto on polynomikerto . $\mathbb {Z} [x]/\langle f\rangle$ $f$ $n$

Ihanteellisen hilan matemaattinen määritelmä

Ideaalihila on kokonaislukuhila , jossa jollekin tietylle kantalle niin, että jollekin pelkistetylle astepolynomille on olemassa ideaali ${\mathcal {L}}(I)\subseteq \mathbb {Z} ^{n}$ ${\displaystyle B\in \mathbb {Z} ^{(n,n)))$ $B=$ $\lbrace (g\ {\bmod {\ }}\ f):g\in \mathbb {Z} [x]\rbrace$ $f$ $n$ $I\subseteq \mathbb {Z} [x]/\langle f\rangle$

Rajoitukset : $f$

$f$ - on oltava peruuttamaton
renkaan normi ei saa olla suurempi kuin minkään polynomin normi ${\displaystyle \lVert g\rVert _{f))$ ${\displaystyle \lVert g\rVert _{\infty ))$ $g$

Lemma

Jos on normalisoitu pelkistymätön kokonaislukupolynomi asteella , niin mikä tahansa ideaalinen on isomorfinen hila , jolla on täysi arvo , eli kanta koostuu lineaarisesti riippumattomista vektoreista, joiden koordinaatit ovat astepolynomin kertoimia $f$ $n$ $\mathbb {Z} ^{n}$ $n$ $f$ $n$

Algoritmi ihanteellisten hilan tunnistamiseksi täydellä arvolla

Olkoon kanta annettu Ehto: jos se kattaa ideaalisen hilan parametrin suhteen , niin tosi , muuten epätosi ${\displaystyle B\in \mathbb {Z} ^{(n,n)))$
$B$ $q$

tuoda hermiittiseen muotoon $B$
$A={\rm {adj}}(B)$ , eli siihen liittyvä matriisi , on determinantti , ja $B$ $d=\det(B)$ ${\displaystyle z=B_{(n,n)))$
$P=AMB{\bmod {\ }}d$
jos kaikki sarakkeet viimeistä lukuun ottamatta ovat tyhjiä , silloin $P$
laita ei-nolla-sarakkeeseen (eli viimeiseen sarakkeeseen ) ${\displaystyle c=P_{(\centerdot ,n)))$ $P$
muuten palauttaa epätosi
jos , silloin on joukko elementtejä z, jotka tyydyttävät kaikki sitten ${\displaystyle z\mid c_{i))$ ${\displaystyle c_{i))$ $i=1,\dots ,n$
soveltaa Kiinan jäännöslausetta löytääksesi ja $q^{\ast }\equiv \ (c/z){\bmod {\ }}(d/z)$ $q^{\ast }\equiv 0{\bmod {\ }}z$
muuten palauttaa epätosi
jos sitten $Bq^{\ast }\equiv 0{\bmod {\ }}(d/z)$
tuo totuus takaisin $q=Bq^{\ast }/d$
muuten palauttaa epätosi

Lisäys: matriisi saa muodon $M$

M={\begin{pmatrix}0&.&.&.&0\\&&&&.\\&&&&.\\I_{n-1}&&&&.\\&&&&0\end{pmatrix))

Esimerkki algoritmin käyttämisestä ideaalisten hilan identifioimiseksi, joiden kantakannat ovat täydet

Tällä algoritmilla [6] voidaan varmistaa, että harvat hilat ovat ihanteellisia hiloja [6] .
Harkitse esimerkkiä: Anna ja sitten $n = 2$ $k\in \mathbb {Z} \setminus \lbrace 0,\pm 1\rbrace$

B_{1}={\begin{pmatrix}k&0\\0&1\end{pmatrix}}

on ihanteellinen, toisin kuin

B_{2}={\begin{pmatrix}1&0\\0&k\end{pmatrix}}

$B_2$ Lyubashevsky V:n ja Missiancio D:n [7] keksimällä esimerkillä $k = 2$

Tämän algoritmin käyttämiseksi matriisin on oltava hermiittinen normaalimuoto , joten algoritmin ensimmäinen vaihe on pakollinen. Determinantti on , ja siihen liittyvä matriisi $B$ $d = 2$

A={\begin{pmatrix}2&0\\0&1\end{pmatrix}}

M={\begin{pmatrix}0&0\\1&0\end{pmatrix}}

ja lopuksi matriisitulo on $P=AMB{\bmod {d}}$

P={\begin{pmatrix}0&0\\1&0\end{pmatrix}}.

Tässä vaiheessa algoritmi pysähtyy, koska kaikkien paitsi viimeisen sarakkeen on oltava nolla, jos se on täydellinen hila . $P$ $B$

Hilateorian yleisiä ongelmia

etsi lyhin vektori - etsi lyhin nollasta poikkeava vektori mielivaltaisten kantavektoreiden edustaman hilan mukaan. Itse asiassa yleensä tarkastellaan likimääräistä versiota lyhimmän vektorin löytämisen ongelmasta, jonka tarkoituksena on saada hilaan vektori, jonka pituus ei ylitä lyhimmän nollasta poikkeavan vektorin pituutta μ(n)- kertaa, missä μ(n) on approksimaatiokerroin ja on hilan mitta. [kahdeksan] $n$
lähimmän vektorin etsiminen on yleistys lyhimmän vektorin löytämisongelmasta [9]
etsi lyhimmät riippumattomat vektorit [10] .

Ihanteellisten hilojen sovellukset

Törmäyksenkestävät hash-funktiot

Törmäyksenkestävä hash-funktio on funktio, joka määritellään kartoituksella siten, että joukon kardinaliteetti (jonkin lukuavaruuden alue) on suurempi kuin joukon kardinaliteetti , mikä vaikeuttaa törmäyksen löytämistä , eli pari . Näin ollen satunnaisesti valitulla hyökkääjällä ei voida tehokkaasti (kohtuullisessa ajassa) löytää törmäyksiä kohteessa , vaikka törmäyksiä onkin [11] . Ideaalihilojen pääasiallinen käyttö kryptografiassa johtuu siitä, että riittävän tehokkaita ja käytännöllisiä törmäyshajautusfunktioita voidaan rakentaa likimääräisen lyhimmän vektorin löytämisen kovuuden perusteella tällaisissa hilassa [5] . Ihanteellisia kryptografisia hiloja tutkivat tutkijaryhmät ovat tutkineet ideaalihilojen pohjalta rakennettuja törmäyksenkestäviä hash-funktioita , nimittäin Peikret K. ja Rosen S. [12] . Nämä tulokset tasoittivat tietä muille tehokkaille kryptografisille rakenteille, mukaan lukien tunnistus- ja allekirjoitusjärjestelmät. ${\displaystyle h_{k))$ ${\näyttötyyli :D\rightarrow R}$ $D$ $R$ $|R|$ ${\näyttötyyli \ll }$ $|D|$ $x_{1},x_{2}\in D,h(x_{1})=h(x_{2})$ $k$ ${\displaystyle h_{k))$

Lobashevsky V. ja Missiancio D. [ 7] ehdottivat tehokkaiden ja törmäyskestävien hajautusfunktioiden konstruktioita , jotka voidaan todistaa ihanteellisten hilan lyhimmän vektoriongelman pahimman tapauksen jäykkyyden perusteella . Siten määriteltiin elementeille tarkasteltavat hash-funktioiden perheet:

$h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}$ , jossa on näyte satunnaisista elementeistä kohteesta , . $m$ $a_{1},\dots ,a_{m}\in R=\mathbb {Z} _{p}[x]/\langle f\rangle$ ${\displaystyle b=(b_{1},...,b_{m})\in D^{m))$

Tässä tapauksessa avaimen koko eli hash-funktio määritellään [13] , käyttäen nopeaa Fourier-muunnosalgoritmia , sopivalle ,operaatio voidaan suorittaa ajoissa . Koska se on vakio, hajautus vaatii rajallisen ajan . $O(mn\log p)=O(n\log n)$ $f$ ${\displaystyle \alpha _{i}\centerdot b_{i))$ $O(n\log n\log \log n)$ $m$ $O(n\log n\log \log n)$ ${\displaystyle}$

Digitaaliset allekirjoitukset

Digitaaliset allekirjoitusjärjestelmät ovat tärkeimpiä kryptografisia primitiivejä . Ne voidaan saada käyttämällä yksisuuntaisia funktioita , jotka perustuvat hilaongelmien pahimman tapauksen jäykkyyteen, mutta ne ovat epäkäytännöllisiä. Virheoppimisongelman käytön jälkeen kryptografisessa kontekstissa on kehitetty useita uusia digitaalisia allekirjoitusmenetelmiä , jotka perustuvat virheoppimiseen ja virherenkaan oppimiseen. [neljätoista]

Digitaalisten allekirjoitusten suora rakentaminen perustuu vaikeuteen approksimoida lyhin vektori ideaalisissa hilassa. [15] V. Lyubashevskyn ja D. Missiancion [15] ideaalisiin ristikkoihin perustuvalla skeemalla on turvatakuut pahimmassakin tapauksessa ja se on asymptoottisesti tehokkain nykyään tunnettu rakenne, joka mahdollistaa myös allekirjoitusten generoinnin ja algoritmien tarkistamisen. jotka kulkevat lähes lineaarisessa ajassa [16] .

Yksi tärkeimmistä avoimista ongelmista, joita yllä kuvatuissa töissä on nostettu esille, on luoda kertaluonteinen allekirjoitus samalla tehokkuudella, mutta heikompaan kovuusoletukseen perustuen. Olisi esimerkiksi hienoa tarjota kertaluonteinen allekirjoitus suojauksella, joka perustuu lyhyimmän vektoriongelman (SVP) lähentämisen vaikeuteen (ihanteellisissa hilassa) sisällä . [17] ${\tilde {O}}(n)$

Tällaisten digitaalisten allekirjoitusten rakentaminen perustuu kertaluonteisten allekirjoitusten (eli allekirjoitusten, jotka mahdollistavat yhden viestin turvallisen allekirjoittamisen) standardimuuntamiseen yleisiksi allekirjoitusmalleiksi sekä uuteen hilapohjaiseen kertaluonteiseen allekirjoitusmalliin, jonka turvallisuus on suojattu. perustuu viime kädessä lyhimmän vektorin likimääräisen , mikä vastaa renkaan ihanteita mille tahansa redusoitumattomalle polynomille [16] . $\mathbb {Z} [x]/\langle f\rangle$ $f$

SWIFT-hajautusfunktio

Hajautusfunktio on kohtuullisen tehokas ja se voidaan laskea asymptoottisesti ajassa käyttämällä nopeaa Fourier - muunnosta kompleksiluvuissa . Käytännössä tähän liittyy kuitenkin huomattavat yleiskustannukset. Missiancio D.:n ja Regevin [16] määrittelemä salausteknisten hajautusfunktioiden joukko , joiden turvallisuus on todistettu SWIFFT :llä , on itse asiassa erittäin optimoitu versio yllä kuvatusta hash-funktiosta käyttämällä nopeaa Fourier-muunnosta vuonna . Vektorin f määritetään olevan yhtä suuri kuin 2:n potenssi, joten vastaava polynomi on redusoitumaton polynomi. SWIFFT- funktioiden törmäysten havaitseminen vastaa törmäysten löytämistä ihanteellisen hilan perusfunktiosta . SWIFFT- törmäysten ilmoitettua ominaisuutta [18] tuetaan pahimmassa tapauksessa ideaalihilojen ongelmissa. ${\tilde {O}}(m)$ ${\displaystyle \mathbb {Z} _{q))$ ${\displaystyle (1,0,\pisteet ,0)\in \mathbb {Z} ^{n))$ $n$ $x^{n}+1$ $f_{A}$

SWIFFT - hajautusalgoritmi :

Parametrit: Luonnolliset numerot siten, että teho kaksi , prime, ja . ${\näyttötyyli n,m,q,d}$ $n$ $q$ $2n\mid (q-1)$ $n\mid m$
Avain: Vektorit valitaan itsenäisesti ja satunnaisesti . $m/n$ ${\tilde {a}}_{1},...,{\tilde {a}}_{m/n}$ ${\displaystyle \mathbb {Z} _{q}^{n))$
Syöttö: vektori . $m/n$ ${\displaystyle y^{(1)},\pisteet ,y^{(m/n)}\in \lsulku 0,\pisteet ,d-1\rhaulu ^{n))$
Tulos: vektori , jossa on komponenttivektoritulo ja on käännettävä matriisi yli $\sum _{i=1}^{m/n}{\tilde {a}}^{(i)}\odot ({\textbf {W}}y^{(i)})\in \mathbb {Z} _{q}^{n}$ $\odot$ ${\textbf {W}}\in \mathbb {Z} _{q}^{n\times n}$ ${\displaystyle \mathbb {Z} _{q))$

Katso myös

Muistiinpanot

↑ Shah, Agam Quantum-laskennan läpimurtovaatimus IBM:ltä . Haettu: 1.6.2015. (määrätön)
↑ Nicolas Gama, Phong Q. Nguyen Hilapohjaiset tunnistusjärjestelmät turvassa aktiivisten hyökkäysten alla . Ennustava hilavähennys, 1995.
↑ Daniele Micciancio, Oded Regev Lattice-pohjainen kryptografia , 2008.
↑ Vadim Lyubashevsky, Chris Peikert, Oded Regev Ihanteellisista ristikkoverkoista ja renkaiden virheiden kanssa oppimisesta , 2013.
↑ 1 2 Vadim Ljubaševski. Hilapohjaiset tunnistusjärjestelmät suojatut aktiivisten hyökkäysten alla . Julkaisussa Proceedings of the Practice and theory in public key cryptography , 11. kansainvälinen julkisen avaimen kryptografiaa käsittelevä konferenssi , 2008.
↑ 1 2 Jintai Ding ja Richard Lindner. Ihanteellisten ristikoiden tunnistaminen . Julkaisussa Cryptology ePrint Archive, raportti 2007/322 , 2007.
↑ 1 2 Lyubashevsky, V., Micciancio, D. Yleiset kompaktit reput ovat törmäyksenkestäviä. . Teoksessa CBugliesi, M., Preneel, B., Sassone, V., Wegener, I. (toim.) ICALP 2006. LNCS, voi. 4052, s. 144-155. Springer, Heidelberg (2006) .
↑ Lenstra A., Lenstra H., Lovasz L. Polynomien faktorointi rationaalisilla kertoimilla , 1982.
↑ V.Lyubashevsky, Daniele Micciancio Yleiset kompaktit reput ovat törmäyksenkestäviä . Kansainvälisessä kollokviumissa automaateista, kielistä ja ohjelmoinnista , 2008.
↑ Hilaongelmien monimutkaisuus: kryptografinen näkökulma. Kluwerin kansainvälinen tekniikan ja tietojenkäsittelytieteen sarja , < http://cseweb.ucsd.edu/~daniele/papers/book.bib >
↑ O. Goldreich, S. Goldwasser, S. Halevi. Törmäysvapaa hajautus lattice-ongelmista , 1996.
↑ Vadim Lyubashevsky, Chris Peikert ja Oded Regev. Ihanteellisista ristikoista ja renkaiden virheistä oppimisesta (linkki ei ole käytettävissä) . Julkaisussa Eurocrypt 2010, Lecture Notes in Computer Science , 2010.
↑ Mikl´os Ajtai edustaa kovaa ristikkoa O(n log n) biteillä , 2005.
↑ Ljubaševski, Vadim; Peikert, Chris; Regev, Oded. Ihanteellisista hioista ja oppimisesta renkaiden yli virheillä (englanniksi) // In Proc. EUROCRYPT, LNCS:n osa 6110: aikakauslehti. - 2010. - s. 1-23 .
↑ 1 2 Vadim Lyubashevsky ja Daniele Micciancio. Asymptoottisesti tehokkaat hilapohjaiset digitaaliset allekirjoitukset . julkaisussa Proceedings of the 5th Conference on Theory of cryptography , 2008.
↑ 1 2 3 Daniele Micciancio, Oded Regev Lattice-pohjainen kryptografia . Julkaisussa POST-QUANTUM CRYPTOGRAPHY , 2009.
↑ Vadim Lyubashevsky, Daniele Micciancio. Asymptoottisesti tehokkaat hilapohjaiset digitaaliset allekirjoitukset . julkaisussa Proceedings of the 5th Conference on Theory of cryptography , 2008.
↑ Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen [ https://link.springer.com/chapter/10.1007%2F978-3-540-71039-4_4 : Vaatimaton ehdotus FFT Hashingille, 2008.

Kirjallisuus

J. Hoffstein, N. Howgrave-Graham, J. Pipher, JH Silverman, W. Whyte. Kryptologian aiheet - CT-RSA 2003 . - 2003. - S. 122-140.
J. Hoffstein, J. Pipher ja J. H. Silverman. NTRU: Rengaspohjainen julkisen avaimen salausjärjestelmä . - 1998. - S. 267-288.
V. Lyubashevsky ja D. Micciancio. Yleiset kompaktit selkäreput ovat törmäyksenkestäviä . - 2006. - S. 144-155.
Peikert, C., Rosen, A. Tehokas törmäyskestävä tiivistys pahimman tapauksen oletuksista syklisissä ristikoissa . - 2006. - S. 145-166.
Craig Gentry. Täysin homomorfinen salaus ihanteellisia hiloja käyttäen . - 2009. - S. 169-178.
Phong Q. Nguyen, Jacques Stern. Lattice Reduction in Cryptology: An Update // Proceedings of the 4th International Symposium on Algorithmic Number Theory. - Springer-Verlag, 2000. - S. 85-112. — ISBN 3-540-67695-3 .

Linkit

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. ilmoittaa. teoria. - 2002. - T. 48 , no. 8 .
Daniele Micciancio. Lyhyin vektoriongelma on {NP}-vaikea approksimoida johonkin vakioon // SIAM Journal on Computing. - 2001. - T. 30 , no. 6 . - S. 2008-2035 .
Lyubashevsky, V., Micciancio, D. Yleiset kompaktit reput ovat törmäyksenkestäviä . - 2006. - S. 1-27 .
Lyubashevsky, V., Micciancio, D. Asymptoottisesti tehokkaat hilapohjaiset digitaaliset allekirjoitukset . – 2008.
Lyubashevsky V. Hilapohjaiset tunnistusjärjestelmät, jotka ovat turvassa aktiivisten hyökkäysten alla . - 2008. - S. 1-18 .
Vadim Lyubashevsky, Chris Peikert ja Oded Regev. Ihanteellisista ristikoista ja renkaiden virheiden oppimisesta . - 2010. - S. 1-27 .
Leo Ducas. Edistystä ideaalihilojen kvanttikriptianalyysissä . - 2017. - S. 184-189 .
Eva Bayer Fluckiger. Ihanteelliset ristikot . - 2017. - S. 1-17 .
Ihanteellisten ristikoiden tunnistaminen. Jintai Ding ja Richard Lindner . - 2007. - S. 1-12 .
Jintai Ding, Xiang Xie, Xiaodong Lin. Yksinkertainen todistetusti suojattu avainten vaihtojärjestelmä, joka perustuu virheiden kanssa oppimiseen -ongelmaan . - 2012. - S. 1-15 .
C. Peikert. Lattice Cryptography for Internet . - 2014. - S. 1-25 .
V. Lyubashevsky. Hila-allekirjoitukset ilman sulkuovia . - 2014. - S. 1-24 .
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka ja Keita Xagawa. Tehokas julkisen avaimen salaus, joka perustuu ihanteellisiin hilakoihin . - 2009. - S. 1-19 .