Ideális rács

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 7-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az ideális rács egy meghatározott matematikai struktúra , amelyet a rácsok (amelyek véges rangú szabad kommutatív csoportok) leírásához szükséges paraméterek számának csökkentésére használnak . Ez a fajta rács gyakran megtalálható a matematika számos területén, különösen a számelmélet részében . Így az ideális rácsok hatékonyabban használhatók, mint a kriptográfiában használt többi rács . Ideális rácsokat használnak az NTRUEncrypt és NTRUSign nyilvános kulcsú kriptográfiai rendszerekben a hatékony kriptográfiai primitívek létrehozására . Az ideális rácsok képezik a kvantumkriptográfia alapvető alapját is , amely védelmet nyújt a kvantumszámítógépekkel kapcsolatos támadásokkal szemben.

Bevezetés

Az RSA és az ECC sémák , amelyek akár a faktorizáció összetettségén , akár a diszkrét logaritmusprobléma összetettségén alapulnak , a legnépszerűbb aszimmetrikus titkosítási rendszerek, amelyek különböző kulcsokat használnak az információk titkosításához, majd visszafejtéséhez. Az RSA és ECC sémák túlsúlya ellenére ismert, hogy érzékenyek a kvantumszámítógépeket használó támadásokra [1] . Ezenkívül az RSA és az ECC meglehetősen nem hatékony a nagyon kicsi és korlátozott eszközökön, például a 8 bites AVR mikrokontrollereken , amelyeket a mai napig használnak különféle területeken, mint például a robotika , az energia, a műholdas kommunikációs rendszerek és sok más. A fenti sémák egy lehetséges alternatívája az ideális rácsokban lévő kemény problémákon alapuló aszimmetrikus kriptorendszerek [2] . Az ideális rácsok speciális algebrai szerkezete jelentősen csökkentheti a kulcs és a rejtjelezett szöveg méretét, miközben hatékony aritmetikát biztosít a számelméleti transzformáció segítségével. Így az ideális rácsok használatának köszönhetően a titkosított információk védettségi foka megnövekszik [3] .

Alapfogalmak

A rácselmélet lineáris algebra segítségével írható le . A rácsot általában egy n-dimenziós valós lineáris tér bármely egyenletes eloszlású pontrácsának tekintik, ahol minden koordináta egész szám . Ez a halmaz egy csoportot alkot, ha koordinátákhoz adjuk, és diszkrét , ami azt jelenti, hogy a halmaz minden pontja körül van egy nyitott golyó , amely nem tartalmaz más pontot a halmazban , így a rács az összes lineáris egész halmaza. egy adott lineárisan független ponthalmaz kombinációi a -ban . A rácsok csoportok , az ideális rácsok pedig az ideálok [4] . $R^{n}$ ${\displaystyle Z^{n))$

Konkrétan, az ideális rácsok valamilyen irreducibilis fokú polinom alakú gyűrűknek felelnek meg [5] . Az ideális rácsos kriptográfia alapvető művelete a polinomiális szorzás . $\mathbb {Z} [x]/\langle f\rangle$ $f$ $n$

Egy ideális rács matematikai meghatározása

Ideális rács olyan egész rács , amely bizonyos bázisra úgy , hogy valamilyen redukált fokszámú polinomra létezik ideális ${\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$

Korlátozások : $f$

$f$ - redukálhatatlannak kell lennie
a gyűrű normája nem lehet nagyobb, mint egyetlen polinomra sem ${\displaystyle \lVert g\rVert _{f))$ ${\displaystyle \lVert g\rVert _{\infty ))$ $g$

Lemma

Ha egy fokú normalizált irreducibilis egész polinom , akkor bármely ideál teljes rangú izomorf rács -ben , azaz az alap lineárisan független vektorokból áll, amelyek koordinátái a fokpolinom együtthatói . $f$ $n$ $\mathbb {Z} ^{n}$ $n$ $f$ $n$

Algoritmus ideális rácsok azonosítására teljes rangú bázisokkal

Legyen adott a bázis Feltétel: ha lefedi az ideális rácsot a paraméterhez képest , akkor igaz , egyébként hamis ${\displaystyle B\in \mathbb {Z} ^{(n,n)))$
$B$ $q$

hermitikus formába hozzuk $B$
$A={\rm {adj}}(B)$ , azaz a társított mátrix a determináns , és $B$ $d=\det(B)$ ${\displaystyle z=B_{(n,n)))$
$P=AMB{\bmod {\ }}d$
ha az utolsó kivételével minden oszlop üres, akkor $P$
egy nem nulla oszlopba (nevezetesen az utolsó oszlopba ) ${\displaystyle c=P_{(\centerdot ,n)))$ $P$
különben vissza hamis
ha , akkor van egy z elemhalmaz , amely minden akkor kielégítő ${\displaystyle z\mid c_{i))$ ${\displaystyle c_{i))$ $i=1,\pontok ,n$
alkalmazzuk a kínai maradéktételt az és megtalálásához $q^{\ast }\equiv \ (c/z){\bmod {\ }}(d/z)$ $q^{\ast }\equiv 0{\bmod {\ }}z$
különben vissza hamis
ha akkor $Bq^{\ast }\equiv 0{\bmod {\ }}(d/z)$
hozza vissza az igazságot $q=Bq^{\ast }/d$
különben vissza hamis

Kiegészítés: a mátrix felveszi a formát $M$

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

Példa a teljes rangú bázisú ideális rácsok azonosítására szolgáló algoritmus használatára

Ezzel az algoritmussal [6] ellenőrizhető, hogy kevés rács ideális rács [6] .
Vegyünk egy példát: Legyen és , akkor $n=2$ $k\in \mathbb {Z} \setminus \lbrace 0,\pm 1\rbrace$

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

ideális, ellentétben

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

$B_2$ Lyubashevsky V. és Missiancio D. által kitalált példával [7] $k=2$

Az algoritmus használatához a mátrixnak egy hermitikus normálformának kell lennie , tehát az algoritmus első lépése kötelező. A determináns , és a hozzá tartozó mátrix $B$ $d=2$

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

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

és végül a mátrixszorzat az $P=AMB{\bmod {d}}$

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

Ezen a ponton az algoritmus leáll, mert az utolsó oszlop kivételével minden oszlopnak nullának kell lennie, ha tökéletes rács . $P$ $B$

Gyakori problémák a rácselméletben

a legrövidebb vektor keresése - a legrövidebb nem nulla vektor keresése a tetszőleges bázisvektorok által képviselt rács szerint. Valójában a legrövidebb vektor megtalálásának problémájának hozzávetőleges változatát szokták figyelembe venni, amelynek célja, hogy olyan vektort kapjunk a rácsban, amelynek hossza nem haladja meg a legrövidebb nem nulla vektor hosszát μ(n)-val. alkalommal, ahol μ(n) a közelítési együttható, és a rács dimenziója. [nyolc] $n$
a legközelebbi vektor keresése a legrövidebb vektor megtalálásának problémájának általánosítása [9]
keressük meg a legrövidebb független vektorokat [10] .

Ideális rácsok alkalmazásai

Ütközésálló hash függvények

Az ütközésálló hash függvény olyan leképezéssel definiált függvény , hogy egy halmaz (valamely számtér tartománya) kardinalitása nagyobb, mint egy halmaz számossága , , ami megnehezíti az ütközés megtalálását , azaz egy pár . Így egy véletlenszerűen kiválasztott támadó esetén egyetlen támadó sem tud hatékonyan (ésszerű időn belül) találni ütközéseket a -ban , annak ellenére, hogy vannak ütközések [11] . Az ideális rácsok fő felhasználása a kriptográfiában annak köszönhető, hogy kellően hatékony és praktikus ütközési hash függvények építhetők fel az ilyen rácsokban a hozzávetőleges legrövidebb vektor megtalálásának keménysége alapján [5] . Ideális kriptográfiai rácsokat tanulmányozó tudóscsoportok az ideális rácsokra épülő ütközésálló hash függvényeket vizsgálták, nevezetesen Peikret K. és Rosen S. [12] . Ezek az eredmények megnyitották az utat más hatékony kriptográfiai konstrukciók, köztük az azonosítási és aláírási sémák előtt. ${\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. és Missiancio D. [ 7] hatékony és ütközésálló hash függvényeket javasoltak, amelyek az ideális rácsok legrövidebb vektorproblémájának legrosszabb merevsége alapján igazolhatók . Így meghatároztuk az elemekhez tartozó hash függvények figyelembe vett családjait:

${\displaystyle h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i))$ , ahol van egy minta véletlenszerű elemekből , . $m$ $a_{1},\dots ,a_{m}\in R=\mathbb {Z} _{p}[x]/\langle f\rangle$ ${\displaystyle b=(b_{1},...,b_{m})\in D^{m))$

Ebben az esetben a kulcs méretét, vagyis a hash függvényt [13] -ban definiáljuk , a gyors Fourier-transzformációs algoritmus segítségével megfelelő , a művelet időben befejezhető . Mivel ez egy állandó, a kivonatoláshoz véges idő szükséges . $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}$

Digitális aláírások

A digitális aláírási sémák a legfontosabb kriptográfiai primitívek közé tartoznak. Ezek a rácsproblémák legrosszabb merevségén alapuló egyirányú függvényekkel érhetők el , de nem praktikusak. A hibatanulási probléma kriptográfiai felhasználása óta számos új digitális aláírási sémát fejlesztettek ki , amelyek a hibatanuláson és a hibagyűrűs tanuláson alapulnak. [tizennégy]

A digitális aláírások közvetlen felépítése azon alapul, hogy az ideális rácsok legrövidebb vektorát nehéz megközelíteni . [15] V. Lyubashevsky és D. Missiancio [15] ideális rácsokon alapuló sémája a legrosszabb esetben is biztonsági garanciákkal rendelkezik, és a ma ismert aszimptotikusan leghatékonyabb konstrukció, amely lehetővé teszi aláírások generálását és algoritmusok ellenőrzését is. amelyek szinte lineáris időben futnak [16] .

Az egyik fő nyitott probléma, amely a fent leírt munkák során felmerült, az egyszeri aláírás létrehozása hasonló hatékonysággal, de gyengébb keménységi feltételezés alapján. Például nagyszerű lenne egy egyszeri aláírást biztosítani olyan biztonsággal, amely a legrövidebb vektorprobléma (SVP) (ideális rácsokban) belülre való közelítésének nehézségén alapul . [17] ${\tilde {O}}(n)$

Az ilyen digitális aláírások létrehozása az egyszeri aláírások (azaz egyetlen üzenet biztonságos aláírását lehetővé tévő aláírások) általános aláírási sémákká történő konvertálásán alapul, valamint egy új, rács alapú egyszeri aláírás-tervezés, amelynek biztonsága végső soron a legrövidebb vektorközelítés legrosszabb merevségén alapul az összes rácsban , ami megfelel a gyűrűben lévő ideáloknak bármely irreducibilis polinomra [16] . $\mathbb {Z} [x]/\langle f\rangle$ $f$

SWIFT hash függvény

A hash függvény meglehetősen hatékony, és időben aszimptotikusan kiszámolható a komplex számok gyors Fourier-transzformációjával . A gyakorlatban azonban ez jelentős többletköltséggel jár. A Missiancio D. és Regev [16] által definiált SWIFFT bizonyított biztonságú kriptográfiai hash függvények halmaza valójában a fent leírt hash függvény rendkívül optimalizált változata a gyors Fourier-transzformáció segítségével . Az f vektort úgy határozzuk meg, hogy egyenlő 2 hatványával, tehát a megfelelő polinom egy irreducibilis polinom. A SWIFFT- függvények ütközésérzékelése egyenértékű az ideális rács alapfüggvényében található ütközések megtalálásával . A SWIFFT ütközések deklarált tulajdonsága [18] a legrosszabb esetben az ideális rácsok problémáinál támogatott. ${\tilde {O}}(m)$ ${\displaystyle \mathbb {Z} _{q))$ ${\displaystyle (1,0,\pontok ,0)\in \mathbb {Z} ^{n))$ $n$ $x^{n}+1$ $f_{A}$

SWIFFT hash algoritmus :

Paraméterek: Természetes számok , így a kettő hatványa , prím és . $n,m,q,d$ $n$ $q$ $2n\mid (q-1)$ $n\mid m$
Kulcs: A vektorok egymástól függetlenül és véletlenszerűen kerülnek kiválasztásra a -ban . $m/n$ ${\tilde {a}}_{1},...,{\tilde {a}}_{m/n}$ $\mathbb {Z} _{q}^{n}$
Bemenet: vektor . $m/n$ ${\displaystyle y^{(1)},\dots ,y^{(m/n)}\in \lbrace 0,\dots ,d-1\rbrace ^{n))$
Kimenet: vektor , ahol a komponens vektorszorzata , és egy invertálható mátrix over $\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))$

Lásd még

Jegyzetek

↑ Shah, Agam A Quantum számítástechnika áttörést jelentő követelése az IBM-től . Letöltve: 2015. június 1. (határozatlan)
↑ Nicolas Gama, Phong Q. Nguyen Rács-alapú azonosítási sémák biztonságosak aktív támadások alatt . A rácscsökkentés előrejelzése, 1995.
↑ Daniele Micciancio, Oded Regev, rácsalapú kriptográfia , 2008.
↑ Vadim Ljubasevszkij, Chris Peikert, Oded Regev Az ideális rácsokról és a gyűrűs hibákkal való tanulásról , 2013.
↑ 1 2 Vadim Ljubasevszkij. A rács alapú azonosítási sémák biztonságosak aktív támadások alatt . In Proceedings of the Practice and theory in public key cryptography , 11. nemzetközi konferencia a nyilvános kulcsú titkosításról , 2008.
↑ 1 2 Jintai Ding és Richard Lindner. Ideális rácsok azonosítása . In Cryptology ePrint Archive, Report 2007/322 , 2007.
↑ 1 2 Lyubashevsky, V., Micciancio, D. Az általánosított kompakt hátizsákok ütközésállóak. . In CBugliesi, M., Preneel, B., Sassone, V., Wegener, I. (szerk.) ICALP 2006. LNCS, vol. 4052, pp. 144-155. Springer, Heidelberg (2006) .
↑ Lenstra A., Lenstra H., Lovasz L. Polinomok faktorálása racionális együtthatókkal , 1982.
↑ V.Lyubashevsky, Daniele Micciancio Az általánosított kompakt hátizsákok ütközésállóak . Az automatákról, nyelvekről és programozásról szóló nemzetközi kollokviumban , 2008.
↑ A rácsproblémák összetettsége: kriptográfiai perspektíva. A Kluwer nemzetközi mérnöki és számítástechnikai sorozat , < http://cseweb.ucsd.edu/~daniele/papers/book.bib >
↑ O. Goldreich, S. Goldwasser, S. Halevi. Ütközésmentes kivonat a rácsproblémákból , 1996.
↑ Vadim Ljubasevszkij, Chris Peikert és Oded Regev. Az ideális rácsokról és a gyűrűk feletti hibákkal való tanulásról (hivatkozás nem érhető el) . In Eurocrypt 2010, Lecture Notes in Computer Science , 2010.
↑ Ajtai Mikl´os Keményrácsok ábrázolása O(n log n) bitekkel , 2005.
↑ Ljubasevszkij, Vadim; Peikert, Chris; Regev, Oded. Az ideális rácsokról és a gyűrűk feletti hibákkal való tanulásról (angol) // In Proc. Az EUROCRYPT, LNCS 6110. kötete: folyóirat. - 2010. - P. 1-23 .
↑ 1 2 Vadim Lyubashevsky és Daniele Micciancio. Aszimptotikusan hatékony rács alapú digitális aláírások . In Proceedings of the 5th Conference on Theory of cryptography , 2008.
↑ 1 2 3 Daniele Micciancio, Oded Regev Rács -alapú kriptográfia . In POSZT-QUANTUM KRIPTOGRÁFIA , 2009.
↑ Vadim Ljubasevszkij, Daniele Micciancio. Aszimptotikusan hatékony rács alapú digitális aláírások . In 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 : Szerény javaslat az FFT Hashing-hez, 2008.

Irodalom

J. Hoffstein, N. Howgrave-Graham, J. Pipher, JH Silverman, W. Whyte. Kriptológiai témák - CT-RSA 2003 . - 2003. - S. 122-140.
J. Hoffstein, J. Pipher és J. H. Silverman. NTRU: Gyűrűalapú nyilvános kulcsú kriptorendszer . - 1998. - S. 267-288.
V. Lyubashevsky és D. Micciancio. Az általánosított kompakt hátizsákok ütközésállóak . - 2006. - S. 144-155.
Peikert, C., Rosen, A. Hatékony ütközésálló kivonatolás a legrosszabb eset feltételezéséből a ciklikus rácsokon . - 2006. - S. 145-166.
Craig Gentry. Teljesen homomorf titkosítás ideális rácsokkal . - 2009. - S. 169-178.
Phong Q. Nguyen, Jacques Stern. Rácsredukció a kriptológiában: frissítés // Proceedings of the 4th International Symposium on Algorithmic Number Theory. - Springer-Verlag, 2000. - S. 85-112. — ISBN 3-540-67695-3 .

Linkek

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. tájékoztatni. elmélet. - 2002. - T. 48 , sz. 8 .
Daniele Micciancio. A legrövidebb vektor probléma {NP}-nehezen közelíthető valamilyen állandó // SIAM Journal on Computing-on belül. - 2001. - T. 30 , sz. 6 . - S. 2008-2035 .
Lyubashevsky, V., Micciancio, D. Az általánosított kompakt hátizsákok ütközésállóak . - 2006. - S. 1-27 .
Lyubashevsky, V., Micciancio, D. Aszimptotikusan hatékony rács alapú digitális aláírások . – 2008.
Lyubashevsky V. Rács -alapú azonosítási sémák biztonságosak aktív támadások alatt . - 2008. - S. 1-18 .
Vadim Ljubasevszkij, Chris Peikert és Oded Regev. Az ideális rácsokról és a gyűrűk feletti hibákról való tanulásról . - 2010. - S. 1-27 .
Leo Ducas. Előrelépések az ideális rácsok kvantumkriptoanalízisében . - 2017. - S. 184-189 .
Bayer Fluckiger Éva. Ideális rácsok . - 2017. - S. 1-17 .
Ideális rácsok azonosítása. Jintai Ding és Richard Lindner . - 2007. - S. 1-12 .
Jintai Ding, Xiang Xie, Xiaodong Lin. Egy egyszerű, bizonyíthatóan biztonságos kulcscsere-séma a Tanulás hibákkal problémán alapul . - 2012. - S. 1-15 .
C. Peikert. Rácsos kriptográfia az internethez . - 2014. - S. 1-25 .
V. Ljubasevszkij. Rácsos aláírások csapóajtók nélkül . - 2014. - S. 1-24 .
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka és Keita Xagawa. Ideális rácsokon alapuló hatékony nyilvános kulcsú titkosítás . - 2009. - S. 1-19 .