Idealiskt galler

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 september 2021; verifiering kräver 1 redigering .

Ett idealiskt gitter är en specifik matematisk struktur som används för att minska antalet parametrar som behövs för att beskriva gitter (som är fria kommutativa grupper av ändlig rangordning). Denna typ av gitter finns ofta inom många områden inom matematiken, i synnerhet i avsnittet om talteorin . Således är idealiska gitter mer effektiva att använda än andra gitter som används i kryptografi . Idealiska gitter används i kryptografiska systemen NTRUEncrypt och NTRUSign med publik nyckel för att bygga effektiva kryptografiska primitiver . Idealiska gitter utgör också den grundläggande basen för kvantkryptografi , som skyddar mot attacker associerade med kvantdatorer.

Inledning

RSA- och ECC- scheman , baserade antingen på komplexiteten i faktoriseringen eller komplexiteten i det diskreta logaritmproblemet , är de mest populära asymmetriska kryptosystemen som använder olika nycklar för att kryptera information och sedan dekryptera den. Trots dominansen av RSA- och ECC- scheman är de kända för att vara mottagliga för attacker med hjälp av kvantdatorer [1] . Dessutom är RSA och ECC ganska ineffektiva på mycket små och begränsade enheter som 8-bitars AVR -mikrokontroller som används till denna dag inom olika områden som robotik , energi, satellitkommunikationssystem och många andra. Ett möjligt alternativ till ovanstående scheman är asymmetriska kryptosystem baserade på hårda problem i ideala gitter [2] . Den speciella algebraiska strukturen hos ideala gitter kan avsevärt minska storleken på nyckeln och chiffertexten, samtidigt som den tillhandahåller effektiv aritmetik med hjälp av den talteoretiska transformationen. Således, tack vare användningen av ideala gitter, ökar skyddsgraden för krypterad information [3] .

Grundläggande begrepp

Gitterteori kan beskrivas med linjär algebra . Ett gitter ses vanligtvis som ett enhetligt fördelat rutnät av punkter i ett n-dimensionellt reellt linjärt utrymme där alla koordinater är heltal . Denna mängd bildar en grupp när den läggs till över koordinater och är diskret , vilket innebär att det för varje punkt i mängden finns en öppen boll runt den som inte innehåller någon annan punkt i mängden , så ett gitter är mängden av alla heltal linjära kombinationer av en given uppsättning linjärt oberoende punkter i . Gitter är grupper , och idealgitter är ideal [4] . $R^{n}$ ${\displaystyle Z^{n))$

I synnerhet motsvarar ideala gitter ringar av formen för något irreducerbart polynom av grad [5] . Den grundläggande operationen i ideal gitterkryptografi är polynommultiplikation . $\mathbb {Z} [x]/\langle f\rangle$ $f$ $n$

Matematisk definition av ett idealgitter

Ett idealgitter är ett heltalsgitter så att det för någon given bas så att det för något reducerat gradpolynom finns ett ideal ${\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$

Begränsningar på : $f$

$f$ - måste vara irreducerbar
ringens norm får inte vara större än normen för något polynom ${\displaystyle \lVert g\rVert _{f))$ ${\displaystyle \lVert g\rVert _{\infty ))$ $g$

Lemma

Om är ett normaliserat irreducerbart heltalspolynom av grad , då är alla ideal ett isomorft gitter av full rang i , det vill säga basen består av linjärt oberoende vektorer vars koordinater är koefficienterna för gradpolynomet $f$ $n$ $\mathbb {Z} ^{n}$ $n$ $f$ $n$

En algoritm för att identifiera ideala gitter med baser av full rang

Låt basen ges villkor: om det täcker det ideala gittret med avseende på parametern , då sant , annars falskt ${\displaystyle B\in \mathbb {Z} ^{(n,n)))$
$B$ $q$

ta till hermitisk form $B$
$A={\rm {adj}}(B)$ , det vill säga den associerade matrisen är determinanten och $B$ $d=\det(B)$ ${\displaystyle z=B_{(n,n)))$
$P=AMB{\bmod {\ }}d$
om alla kolumner utom den sista är null då $P$
lägg i en icke-null kolumn (nämligen den sista kolumnen ) ${\displaystyle c=P_{(\centerdot ,n)))$ $P$
annars returnerar falskt
om , så finns det en uppsättning element z som uppfyller alla då $z\mid c_{i}$ ${\displaystyle c_{i))$ $i=1,\dots ,n$
tillämpa den kinesiska restsatsen för att hitta och $q^{\ast }\equiv \ (c/z){\bmod {\ }}(d/z)$ $q^{\ast}\equiv 0{\bmod {\ }}z$
annars returnerar falskt
om då $Bq^{\ast}\equiv 0{\bmod {\ }}(d/z)$
föra tillbaka sanningen $q=Bq^{\ast }/d$
annars returnerar falskt

Tillägg: matrisen tar formen $M$

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

Ett exempel på användning av algoritmen för att identifiera ideala gitter med baser av full rang

Med hjälp av denna algoritm [6] kan man verifiera att få gitter är idealiska gitter [6] .
Tänk på ett exempel: Låt och , sedan $n=2$ $k\in \mathbb {Z} \setminus \lbrace 0,\pm 1\rbrace$

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

är perfekt, till skillnad från

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

$B_2$ med ett exempel uppfunnit av Lyubashevsky V. och Missiancio D. [7] $k=2$

För att använda denna algoritm måste matrisen vara en hermitisk normalform , så det första steget i algoritmen är obligatoriskt. Determinanten är , och den tillhörande matrisen $B$ $d=2$

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

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

och slutligen är matrisprodukten $P=AMB{\bmod {d}}$

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

Vid denna tidpunkt stannar algoritmen eftersom alla utom den sista kolumnen måste vara noll om är ett perfekt gitter . $P$ $B$

Vanliga problem inom gitterteorin

sök efter den kortaste vektorn - sök efter den kortaste vektorn som inte är noll , enligt det gitter som representeras av godtyckliga basvektorer. I själva verket övervägs vanligtvis en ungefärlig version av problemet med att hitta den kortaste vektorn, vars syfte är att erhålla en vektor i gittret vars längd inte överstiger längden på den kortaste vektorn som inte är noll med μ(n)- gånger, där μ(n) är approximationskoefficienten och är gittrets dimension. [åtta] $n$
sökandet efter den närmaste vektorn är en generalisering av problemet med att hitta den kortaste vektorn [9]
sök efter de kortaste oberoende vektorerna [10] .

Tillämpningar av ideala gitter

Kollisionsbeständiga hashfunktioner

En kollisionssäker hashfunktion är en funktion som definieras av en mappning så att kardinaliteten för en mängd (en region av något talrymd) är större än kardinaliteten för en mängd , , vilket gör det svårt att hitta en kollision , dvs. ett par . Således, givet en slumpmässigt vald , kan ingen angripare effektivt (inom rimlig tid) hitta kollisioner i , även om det finns kollisioner [11] . Den huvudsakliga användningen av ideala gitter i kryptografi beror på det faktum att tillräckligt effektiva och praktiska kollisionshash -funktioner kan byggas på grundval av hårdheten för att hitta en ungefärlig kortaste vektor i sådana gitter [5] . Grupper av forskare som studerar ideala kryptografiska gitter har undersökt kollisionsbeständiga hashfunktioner byggda på basis av ideala gitter, nämligen Peikret K. och Rosen S. [12] . Dessa resultat banade väg för andra effektiva kryptografiska konstruktioner, inklusive identifierings- och signaturscheman. ${\displaystyle h_{k))$ $:D\rightarrow R$ $D$ $R$ $|R|$ $\ll$ $|D|$ $x_{1},x_{2}\in D,h(x_{1})=h(x_{2})$ $k$ ${\displaystyle h_{k))$

Lobashevsky V. och Missiancio D. [7] föreslog konstruktioner av effektiva och kollisionsbeständiga hashfunktioner , som kan bevisas baserat på den värsta styvheten hos det kortaste vektorproblemet för ideala gitter . Således definierades de övervägda familjerna av hashfunktioner för element:

$h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}$ , där det finns ett urval av slumpmässiga element från , . $m$ $a_{1},\dots ,a_{m}\in R=\mathbb {Z} _{p}[x]/\langle f\rangle$ ${\displaystyle b=(b_{1},...,b_{m})\in D^{m))$

I det här fallet är nyckelns storlek, det vill säga hashfunktionen definierad som [13] , med hjälp av den snabba Fourier-transformeringsalgoritmen , för en lämplig , operationen kan slutföras i tid . Eftersom det är en konstant kräver hashing en begränsad tid . $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}$

Digitala signaturer

Digitala signaturscheman är bland de viktigaste kryptografiska primitiven. De kan erhållas med envägsfunktioner baserade på den värsta styvheten av gallerproblem, men är opraktiska. Sedan felinlärningsproblemet användes i ett kryptografiskt sammanhang har ett antal nya digitala signaturscheman utvecklats , baserade på felinlärning och felringinlärning. [fjorton]

Direkt konstruktion av digitala signaturer är baserad på svårigheten att approximera den kortaste vektorn i ideala gitter. [15] Schemat av V. Lyubashevsky och D. Missiancio [15] , baserat på idealiska gitter, har säkerhetsgarantier även i värsta fall och är den mest asymptotiskt effektiva konstruktionen som är känd idag, vilket också tillåter en att generera signaturer och kontrollera algoritmer som går i nästan linjär tid [16] .

Ett av de största öppna problemen som har tagits upp i de arbeten som beskrivs ovan är att skapa en engångssignatur med liknande effektivitet, men baserat på ett antagande om svagare hårdhet. Till exempel skulle det vara bra att tillhandahålla en engångssignatur med säkerhet baserad på svårigheten att approximera Shortest Vector Problem (SVP) (i idealiska gitter) till inom . [17] ${\tilde {O}}(n)$

Konstruktionen av sådana digitala signaturer är baserad på standardkonverteringen av engångssignaturer (d.v.s. signaturer som gör att ett enda meddelande kan signeras säkert) till generiska signaturscheman, tillsammans med en ny gitterbaserad engångssignaturdesign vars säkerhet är i slutändan baserad på den värsta styvheten för den kortaste vektorapproximationen , motsvarande ideal i ringen för något irreducerbart polynom [16] . $\mathbb {Z} [x]/\langle f\rangle$ $f$

SWIFT hash-funktion

Hashfunktionen är någorlunda effektiv och kan beräknas asymptotiskt i tid med den snabba Fouriertransformen i komplexa tal . Men i praktiken kommer detta med en betydande omkostnad. Uppsättningen av kryptografiska hashfunktioner med beprövad säkerhet SWIFFT definierad av Missiancio D. och Regev [16] är i själva verket en mycket optimerad version av hashfunktionen som beskrivs ovan med den snabba Fourier-transformen i . Vektorn f definieras till att vara lika med potensen 2, så motsvarande polynom är ett irreducerbart polynom. Kollisionsdetektering av SWIFFT- funktioner är likvärdigt med att hitta kollisioner i basfunktionen hos ett idealiskt gitter . Den deklarerade egenskapen för SWIFFT- kollisioner [18] stöds i värsta fall i problem på ideala galler. ${\tilde {O}}(m)$ ${\displaystyle \mathbb {Z} _{q))$ ${\displaystyle (1,0,\dots ,0)\in \mathbb {Z} ^{n))$ $n$ $x^{n}+1$ $f_{A}$

SWIFFT hash - algoritm :

Parametrar: Naturliga tal så att potensen av två , primtal och . $n,m,q,d$ $n$ $q$ $2n\mid (q-1)$ $n\mid m$
Nyckel: Vektorerna väljs oberoende och slumpmässigt i . $m/n$ ${\tilde {a}}_{1},...,{\tilde {a}}_{m/n}$ $\mathbb {Z} _{q}^{n}$
Ingång: vektor . $m/n$ ${\displaystyle y^{(1)},\dots ,y^{(m/n)}\i \lbrace 0,\dots ,d-1\rbrace ^{n))$
Utdata: vektor , där är komponentvektorprodukten , och är en inverterbar matris över $\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))$

Se även

Anteckningar

↑ Shah, Agam Quantum computing genombrottsanspråk från IBM . Hämtad: 1 juni 2015. (obestämd)
↑ Nicolas Gama, Phong Q. Nguyen Lattice-Based Identification Schemes Säkra under aktiva attacker . Predicting Lattice Reduction, 1995.
↑ Daniele Micciancio, Oded Regev Lattice-baserad kryptografi , 2008.
↑ Vadim Lyubashevsky, Chris Peikert, Oded Regev om idealiska gitter och lärande med fel över ringar , 2013.
↑ 1 2 Vadim Lyubashevsky. Gitterbaserade identifieringsscheman säkra under aktiva attacker . I Proceedings of the Practice and theory in public key cryptography , 11:e internationella konferensen om offentlig nyckelkryptering , 2008.
↑ 1 2 Jintai Ding och Richard Lindner. Identifiera idealiska galler . I Cryptology ePrint Archive, Rapport 2007/322 , 2007.
↑ 1 2 Lyubashevsky, V., Micciancio, D. Generaliserade kompakta ryggsäckar är kollisionsbeständiga. . I CBugliesi, M., Preneel, B., Sassone, V., Wegener, I. (red.) ICALP 2006. LNCS, vol. 4052, sid. 144-155. Springer, Heidelberg (2006) .
↑ Lenstra A., Lenstra H., Lovasz L. Factoring polynoms with rational coefficients , 1982.
↑ V.Lyubashevsky, Daniele Micciancio Generaliserade kompakta ryggsäckar är kollisionsbeständiga . I Internationellt kollokvium om automater, språk och programmering , 2008.
↑ Gitterproblemens komplexitet: ett kryptografiskt perspektiv. Kluwer internationella serie inom teknik och datavetenskap , < http://cseweb.ucsd.edu/~daniele/papers/book.bib >
↑ O. Goldreich, S. Goldwasser, S. Halevi. Kollisionsfri hashing från gallerproblem , 1996.
↑ Vadim Lyubashevsky, Chris Peikert och Oded Regev. På idealiska gitter och lärande med fel över ringar (länk ej tillgänglig) . I Eurocrypt 2010, Lecture Notes in Computer Science , 2010.
↑ Mikl´os Ajtai representerar hårda gitter med O(n log n) bitar , 2005.
↑ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded. På idealiska gitter och inlärning med fel över ringar (engelska) // In Proc. Av EUROCRYPT, volym 6110 av LNCS: tidskrift. - 2010. - S. 1-23 .
↑ 1 2 Vadim Lyubashevsky och Daniele Micciancio. Asymptotiskt effektiva gitterbaserade digitala signaturer . I Proceedings of the 5th conference on Theory of cryptography , 2008.
↑ 1 2 3 Daniele Micciancio, Oded Regev Gitterbaserad kryptografi . I POST-QUANTUM CRYPTOGRAPHY , 2009.
↑ Vadim Lyubashevsky, Daniele Micciancio. Asymptotiskt effektiva gitterbaserade digitala signaturer . I 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 : A Modest Proposal for FFT Hashing, 2008.

Litteratur

J. Hoffstein, N. Howgrave-Graham, J. Pipher, JH Silverman, W. Whyte. Ämnen i kryptologi - CT-RSA 2003 . - 2003. - S. 122-140.
J. Hoffstein, J. Pipher och J.H. Silverman. NTRU: Ett ringbaserat kryptosystem med offentlig nyckel . - 1998. - S. 267-288.
V. Lyubashevsky och D. Micciancio. Generaliserade kompakta ryggsäckar är kollisionsbeständiga . - 2006. - S. 144-155.
Peikert, C., Rosen, A. Effektiv kollisionsbeständig hashing från värsta fall antaganden på cykliska gitter . - 2006. - S. 145-166.
Craig Gentry. Fullständigt homomorf kryptering med hjälp av idealiska gitter . - 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 .

Länkar

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. underrätta. teori. - 2002. - T. 48 , nr. 8 .
Daniele Micciancio. Det kortaste vektorproblemet är {NP}-svårt att uppskatta inom någon konstant // SIAM Journal on Computing. - 2001. - T. 30 , nr. 6 . - S. 2008-2035 .
Lyubashevsky, V., Micciancio, D. Generaliserade kompakta ryggsäckar är kollisionsbeständiga . - 2006. - S. 1-27 .
Lyubashevsky, V., Micciancio, D. Asymptotiskt effektiva gitterbaserade digitala signaturer . — 2008.
Lyubashevsky V. Gitterbaserade identifieringsscheman säkra under aktiva attacker . - 2008. - S. 1-18 .
Vadim Lyubashevsky, Chris Peikert och Oded Regev. Om idealiska galler och lärande med fel över ringar . - 2010. - S. 1-27 .
Leo Ducas. Framsteg inom kvantkryptanalys av ideala gitter . - 2017. - S. 184-189 .
Eva Bayer Fluckiger. Idealiska galler . - 2017. - S. 1-17 .
Identifiera ideala galler. Jintai Ding och Richard Lindner . - 2007. - S. 1-12 .
Jintai Ding, Xiang Xie, Xiaodong Lin. Ett enkelt bevisligen säkert nyckelutbytessystem baserat på problemet med inlärning med fel . - 2012. - S. 1-15 .
C. Peikert. Gitterkryptering för Internet . - 2014. - S. 1-25 .
V. Lyubashevsky. Gittersignaturer utan fälldörrar . - 2014. - S. 1-24 .
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka och Keita Xagawa. Effektiv offentlig nyckelkryptering baserad på idealiska gitter . - 2009. - S. 1-19 .