Michiancio kriptorendszere

A Michiancio kriptorendszert, a GGH titkosítási sémán alapuló kriptorendszert Daniel Michiancio , a San Diego-i Kaliforniai Egyetem professzora javasolta 2001-ben .

A GGH titkosítási séma a rácsos kriptográfiára támaszkodik , amelyet ígéretesnek tartanak a posztkvantum rendszerekben való használatra ( mivel az egész faktorizációt , diszkrét logaritmust , diszkrét logaritmust használó titkosítási rendszereket elliptikus görbéken hatékonyan meg lehet törni egy kvantumszámítógép , ha Shor algoritmussal alkalmazzák ). . A Michiancio kriptorendszer valójában a GGH titkosítási séma továbbfejlesztése, a kulcs és a rejtjelezett szöveg méretére vonatkozó követelmények egyszeres csökkentésével a rendszer biztonságának veszélyeztetése nélkül, hol van a rács mérete . . Tipikus kriptorendszereknél ez több száz. Christoph Ludwig 2004-ben empirikusan kimutatta, hogy a biztonságos használathoz emellett egy kulcs létrehozása és a visszafejtése is elfogadhatatlanul hosszú időt vesz igénybe, magának a kulcsnak pedig 1 MB -nál nagyobbnak kell lennie . Emiatt ez a kriptorendszer a gyakorlatban nem használható [1] [2] [3] [4] . $N$ $N$ ${\textstyle N\geq 782}$

Alapfogalmak és jelölések

Legyen , ahol lineárisan független vektorok halmaza , és mindegyik vektor összetevője egész szám, és ezeknek a vektoroknak a mátrixa . Továbbá az elmélet a számára készült . Egy rácsot halmaznak nevezünk [5] . ${\displaystyle \mathrm {B} =\{\mathbf {b} _{1},...,\mathbf {b} _{N}\))$ $\mathbf {b} _{i}\in \mathbb {R} ^{M},i={\overline {1,N))$ $N$ $B$ $M\times N$ $M=N$ ${\displaystyle {\mathcal {L}}(\mathrm {B} )=\{\mathrm {B} x\mid x\in \mathbb {Z} ^{M}\))$

Tekintettel arra, hogy az alap nem feltétlenül egyedi, alapjául szokás a hermitikus normálformát választani , amely minden egyes rácsra egyedi. Ez azt jelenti, hogy az alapvektorokból álló mátrix felső háromszög alakú , minden átlós elem szigorúan pozitív, a többi elem pedig teljesül . Ennek a mátrixtípusnak a következő hasznos tulajdonságai vannak. Először is, a Gram-Schmidt ortogonalizáció révén egy ilyen mátrixot átlós alakra redukálunk, az átlón lévő elemekkel . Másodszor, egy ilyen mátrix determinánsa egyenlő az átlós elemeinek szorzatával, azaz [5] . $\mathrm{B}$ ${\displaystyle 0\leq b_{ij}<b_{ii))$ ${\displaystyle b_{ii))$ ${\textstyle \det(\mathrm {B} )=\prod _{i=1}^{n}b_{ii))$

Ez utóbbi magában foglalja az egész rácsok egy fontos tulajdonságát is:

Legyen tetszőleges vektorok és olyanok, hogy $v$ $w$ . Ebben az esetben akkor és csak akkor, ha . $v_{i}\equiv w_{i}\ \mod \det(\mathrm {B} )$ $v\in {\mathcal {L}}(\mathrm {B} )$ $w\in {\mathcal {L}}(\mathrm {B} )$

Legyen egy jobb oldali paralelepipedon , ahol az egész koordináták , a Gram-Schmidt folyamat által ortogonalizált bázisvektorok , . Ilyen paralelepipedonokkal lehet csempézni a teret . Ekkor bármelyikhez van egy egyedi vektor . Az ilyen vektort egy vektorra modulo redukáltnak nevezzük . Ezt úgy kapjuk meg, hogy megtaláljuk a relatív pozíciót -ben , ahol [5] . ${\textstyle {\mathcal {P}}(\mathrm {B} ^{*})=\{\sum _{i}x_{i}\mathbf {b_{i}^{*}} \ |\ 0 \leq x_{i}<1\}}$ $x_{i}$ $\mathbf {b_{i}^{*}}$ $i={\overline {1,N))$ $\mathbb {R} ^{N}$ $v\in \mathbb {Z} ^{N}$ $w\in {\mathcal {P}}(\mathrm {B} ^{*})$ $v\in \mathbb {Z} ^{N}$ $\mathrm{B}$ $v$ $z+{\mathcal {P}}(\mathrm {B} ^{*})$ $z\in {\mathcal {L}}(\mathrm {B} )$

Ezt a vektort a következő algoritmussal találhatjuk meg :

megtalálja ${\textstyle \alpha _{i}={\frac {\langle v,b_{i}^{*}\rangle }{\langle b_{i}^{*},b_{i}^{*}\ hatótávolság }}}$
Számítsa ki a kívánt vektort a [6] képlet segítségével . $w=v-\lfloor \alpha _{i}\rfloor \mathbf {b_{i)) \in {\mathcal {P))(\mathrm {B} ^{*})$

Módszertan

A rácsokon lévő kriptorendszerekben a kulcsok az alapok . Legyen és legyen ugyanannak a rácsnak nyilvános és privát bázisa . A titkosítási rendszer és a GGH titkosítási rendszer közötti különbség az egyirányú funkció optimálisabb megválasztásában rejlik . A funkció fontos jellemzője a Michiancio kriptorendszerben a determinizmus . A következő részben a GGH formájú függvények általános osztályát állítjuk össze. [7] $\mathrm {B}$ ${\mathrm {R}}$ ${\mathcal {L}}={\mathcal {L}}(\mathrm {B} )={\mathcal {L}}\mathrm {(} R)$

A GGH formátumú egyirányú függvények osztálya

A GGH titkosítási sémában az egyirányú függvény a következőt ölti : , ahol a rejtjelezett szöveg , egy egész szám vektor, és a hibavektor hossza legfeljebb , . Ez utóbbira azért van szükség, hogy a hiba ne okozzon erős torzulásokat privát alapú számításnál, és fordítva, nyilvános számításnál. Feltételezzük, hogy az üzenet kódolása -ben van , és véletlenszerűen van kiválasztva [5] . $c=\mathrm {B} x+\epsilon$ $c$ $x$ $\epsilon$ $\rho$ ${\frac {1}{2}}\min _{i}(\mathbf {b_{i}^{*}} )\ll \rho ={\frac {1}{2}}\min _{i}(\mathbf {r_{i}^{*}} )$ $m$ $\epsilon$ $x$

A GGH-típusú egyirányú függvénycsalád , amelyet algoritmusok és , paramétereznek , megfelel: ${\displaystyle f_{\beta ,\gamma ))$ $\gamma$ $\beta$

$\beta$ privát bázist vesz be bemenetként , és nyilvános alapot ad ki ugyanahhoz a rácshoz. ${\mathrm {R}}$ $\mathrm {B}$
$\gamma$ megkapja és , és visszaadja a rácspont együtthatóit $\mathrm {B}$ $\epsilon$ $x$
Ezután leképezi a vektorhalmazt rövidebbre a következőképpen: [5] ${\displaystyle f_{\beta ,\gamma ))$ $\rho$ $f_{\beta ,\gamma }(\epsilon )=\beta ({\mathsf {R)))\gamma ({\mathsf {R)),\epsilon )+\epsilon$

Ha a hibavektor hossza kisebb, mint , akkor a privát bázis segítségével megkereshetjük a legközelebbi pontot , és ennek megfelelően a helyreállítást ( a legközelebbi vektor megtalálásának problémája ) [5] . $\rho$ ${\mathrm {R}}$ $\mathrm {B} x$ $f_{\beta ,\gamma }(\epsilon )$ $\epsilon$

A nyilvános alap kiválasztása

Legyen ismert egy „jó” privát bázis , vagyis annak használatával megoldható a legközelebbi vektor megtalálásának problémája -ben , ami megegyezik - a rejtjelezett szöveg visszafejtése . A feladat az, hogy egy ilyen nyilvános alapból generáljunk, hogy minimálisra csökkentsük a vonatkozó információkat . A szokásos GGH titkosítási sémában véletlenszerű transzformációk halmazát alkalmazzák a . A Michiancio kriptorendszer a Hermite Normal Formát használja nyilvános alapként , azaz (HNF - Hermite Normal Form). Egyedülálló egy adott rácsra, ahogy fentebb említettük . Ez oda vezet, hogy ha az adott rácsnak van más alapja , akkor . Ez azt jelenti, hogy nem tartalmaz több információt, mint a -ról , amelyen ennek a kriptorendszernek a biztonsága alapszik [5] . ${\mathrm {R}}$ ${\mathcal {L}}\mathrm {(} R)$ ${\mathrm {R}}$ $\mathrm {B}$ ${\mathrm {R}}$ $\mathrm {B}$ ${\mathrm {R}}$ $\mathrm {B}$ $\mathrm {B} =HNF(\mathrm {R} )$ $\mathrm {B} '$ $\mathrm {B} =HNF(\mathrm {R} )=HNF(\mathrm {\mathrm {B} '} )$ $\mathrm {B}$ ${\mathrm {R}}$ $\mathrm {B} '$

"Véletlenszerű" rácspont hozzáadása

Ezután szimulálnia kell egy véletlenszerű rácspont hozzáadását . Ideális esetben ezt a pontot tetszőlegesen egységesen kell kiválasztani az összes rácspont között. Ez azonban gyakorlati vagy elméleti szempontból lehetetlen. Majdnem ugyanazt az eredményt kapjuk, ha a redukált vektort használjuk . A hibavektor a nyilvános alapon modulo módon redukálódik , hogy megkapja a titkosított szöveget , ahelyett, hogy véletlenszerű vektort adna hozzá . Ennek eredményeként az egyirányú függvényt a következőképpen adjuk meg: , ahol . A mátrix felső háromszög alakja miatt ez a függvény számítási szempontból nagyon egyszerű. Az érvelést alkalmazva a redukált vektor kiszámításához a -tól kezdve egy képlet található , amely egyedi pontot ad az [5] dobozban . $\mathrm {B} x$ $\epsilon$ $\mathrm {B}$ $c\in {\mathcal {P}}(\mathrm {B} ^{*})$ $f(\epsilon )=\epsilon {\pmod {\mathrm {B} }}$ $\mathrm {B} =HNF(\mathrm {R} )$ $\mathrm {B}$ $x_{i}=\lfloor {\frac {\epsilon _{i}-\sum _{j>i}b_{ij}x_{j}}{b_{ii}}}\rfloor$ $x_{N}$ ${\mathcal {P}}(\mathrm {B} ^{*})$

Összegzés

Legyen magánalap, és legyen viszonylag nagy, legyen nyilvános és . A bázis egy függvényt generál, amely a megfelelő egyenes paralelepipedonnál kisebb hosszúságú vektorokat képez le . Főbb pontok: ${\mathrm {R}}$ $\rho ={\frac {1}{2}}\min _{i}(\mathbf {r_{i}^{*}} )$ $\mathrm {B}$ $\mathrm {B} =HNF(\mathrm {R} )$ $\mathrm {B}$ $f(\epsilon )=\epsilon {\pmod {\mathrm {B} }}$ $\rho$ $\mathrm {B}$ ${\mathcal {P}}(\mathrm {B} ^{*})$

Még ha kezdetben közel van is a ponthoz , a redukciós művelet után egy olyan vektort kapunk, amely közel van a rács többi pontjához. $f(\epsilon )$ $\epsilon$
A -ból való kilábaláshoz meg kell oldani a legközelebbi vektor megtalálásának problémáját , amelyre NP-komplexitás bizonyított. Ezért a visszaállítása , amelynek csak a rendelkezik , szinte lehetetlen, még kvantumszámítógépeknél is. Ez azonban hatékonyan megoldható, ha ismert az alap . $\epsilon$ $f(\epsilon )$ $\epsilon$ $\mathrm {B}$ ${\mathrm {R}}$
A legközelebbi pont a paralelepipedon középpontja, amely tartalmazza a -t, és az alap ismeretében könnyen megtalálható [5] . $f(\epsilon )$ $f(\epsilon )$ ${\mathrm {R}}$

Elméleti elemzés

Biztonság

Ennek a kriptorendszernek az új funkciója ugyanolyan biztonságos, mint a GGH titkosítási séma szolgáltatása . A következő tétel kimondja, hogy a fent definiált függvény legalább olyan jó, mint bármely más GGH típusú függvény [5] .

A következő állítás érvényes: minden függvényre és minden olyan algoritmusra, amely nem nulla valószínűséggel talál meg valamilyen részinformációt , létezik egy hatékony algoritmus, amelynek bemenete ugyanazt az információt ugyanolyan valószínűséggel tudja visszaállítani [5] . $\beta ,\gamma$ $f(\epsilon )$ $\epsilon$ $f_{\beta ,\gamma }(\epsilon )$

Bizonyítás: legyen egy feltörni képes algoritmus . Adott nyilvános alap = és rejtjelezett szöveg . A feltörő algoritmusnak meg kell próbálnia információt találni a . Először és . Az előző rész elméleti eredményeiből az következik, hogy és . Ezért a megfelelő eloszlásúak. Az algoritmust rájuk alkalmazva megkapjuk az [5] tétel állítását . $A$ $f$ $\mathrm{B}$ $\beta (\epsilon )$ $c=\mathrm {B} \gamma +\epsilon$ $\epsilon$ $\mathrm {B} '=HNF(\mathrm {B} )$ $c'=c{\pmod {B'}}$ $\mathrm {B} '=HNF(\mathrm {R} )$ $c'=\mathrm {B} \gamma +\epsilon {\pmod {B'}}=\epsilon {\pmod {B'}}$ $B'$ $c'$ $A$

Aszimptotikus memóriabecslések

Hagyja, hogy a privát kulcs teljesüljön , akkor megbecsüljük a kulcs által elfoglalt méretet . A Hadamard-egyenlőtlenséget felhasználva , valamint azt, hogy a rendszer nyilvános bázisára és titkosított szövegére a GGH becslések és , ebből az következik, hogy a becslések rendszerünk nyilvános alapjára és titkosított szövegére és [5] [7] . $|r_{ij}|<poly(N)$ $O(N^{2}\ \lg N^{2})$ $O(N^{2}\ \lg(\det({\mathcal {L)))))=O(N^{2}\ \lg(N))$ $O(N\ \lg(\det({\mathcal {L)))))=O(N\ \lg(N))$ $O(N^{2}\ \lg(N))$ $O(N\ \lg(N))$

Aszimptotikus futásidejű becslések

Elméletileg az algoritmus várhatóan gyorsabb, mint a GGH, két okból is (a tapasztalati eredményeket alább közöljük). Először is, a GGH rendszerek titkosítási ideje nagymértékben függ a nyilvános kulcs méretétől. A kulcs által elfoglalt memória elméleti becslései a kulcs csökkentését, és ezáltal a titkosítás felgyorsulását jelzik . Ugyanakkor a GGH futási ideje összemérhető az RSA áramkör futási idejével . Másodszor, a kulcs generálásához az eredeti algoritmus a Lenstra-Lenstra-Lovas algoritmust alkalmazza a nagy dimenziós, nagy elemértékű mátrixokra, míg a Michiancio-rendszer egy meglehetősen egyszerű algoritmust használ a Hermitiánus normálalak megtalálásához. A visszafejtéshez a Babai algoritmust [8] használjuk , némi memória- és pontossági veszteséggel, de időbeli javulással helyettesíthető egy egyszerűbb kerekítési algoritmussal [9] , azonban ebben a részben a végrehajtási idő gyorsulása nem várható.

A rendszerbiztonság empirikus értékelése

A gyakorlatban ennek a rendszernek a biztonsága érdekében van szükség . Feltételezve, hogy az időbeli javulás eléri a maximális aszimptotikus becslést , a szükséges minimumnak nagyobbnak kell lennie, mint . Megmutatták továbbá, hogy a nyilvános kulcsnak legalább 1 MB-nak kell lennie. Ráadásul a kulcsgenerálási idő körülbelül egy napot vesz igénybe. A titkosítási eljárás valóban elég gyors. A visszafejtés azonban instabil a Babai algoritmus miatt . Ez leküzdhető, de akkor 73 percet vesz igénybe az ortogonalizáció nélkül . Ha ezt a lépést előre megtette, akkor 4,8 MB hozzáadódik a memóriaköltségekhez ugyanazon dimenzió esetében. Ezekből az eredményekből az következik, hogy a Michiancio kriptorendszer nem alkalmazható a gyakorlatban [1] [2] [3] [4] . $N\geq 782$ $N$ $2093$ $N=800$

Jegyzetek

↑ 12 Christoph Ludwig . A Micciancio-féle kriptorendszer biztonsága és hatékonysága // IACR Cryptology : Cikk. – 2004.
↑ 1 2 T. Plantard, M. Rose, W. Susilo. Rács-alapú kriptográfia fejlesztése CRT használatával. — Kvantumkommunikáció és kvantumhálózat: első nemzetközi konferencia. - 2009. - S. 275-282. — ISBN 9783642117305 .
↑ 1 2 M. Rose, T. Plantard, F. Susilo. A BDD kriptorendszerek javítása az általános rácsokban . — Információbiztonsági gyakorlat és tapasztalat: 7. nemzetközi konferencia. - 2011. - S. 152-167. — ISBN 9783642210303 . Archiválva : 2019. február 22. a Wayback Machine -nél
↑ 1 2 Thomas Richard Rond. A GGH rács alapú titkosítási rendszer fejlődése . Mesterdolgozat (2016). (határozatlan)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Daniele Micciancio. Rács alapú kriptorendszerek fejlesztése a Hermite normál formával // Nemzetközi kriptográfiai és rácsos konferencia. - 2001. - S. 126-145 . - doi : 10.1007/3-540-44670-2_11 . Archiválva az eredetiből: 2020. július 20.
↑ Steven Galbraith. Cryptosystems Based on Lattices (angol) // Cambridge University Press: Paper. - 2012. Archiválva : 2020. február 12.
↑ 1 2 Oded Goldreich, Shafi Goldwasser és Shai Halevi. Nyilvános kulcsú kriptorendszerek a rácsredukciós problémákból // A kriptológia fejlődése – CRYPTO. - 1997. Archiválva : 2019. július 16.
↑ Oded Regev. CVP algoritmus : Rácsok a számítástechnikában. - 2004. Archiválva : 2020. november 1.
↑ Noah Stephens-Davidowitz. Babai algoritmusa (angolul) : NYU, Rácsos minitanfolyam. - 2016. Archiválva : 2019. október 29.

Irodalom

Daniele Micciancio, Oded Regev Rács -alapú kriptográfia // Post Quantum Cryptography. – 2009.
Daniele Micciancio Rács alapú titkosítási rendszerek javítása a Hermite normálforma használatával // Előadásjegyzetek a számítástechnikából. – 2001.
Christoph Ludwig Micciancio kriptorendszerének biztonsága és hatékonysága // IACR Cryptology. – 2004.