Ideální mříž

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. září 2021; ověření vyžaduje 1 úpravu .

Ideální svaz je specifická matematická struktura , která se používá ke snížení počtu parametrů potřebných k popisu svazů (což jsou volné komutativní grupy konečné úrovně). Tento typ mřížky se často vyskytuje v mnoha oblastech matematiky, zejména v sekci teorie čísel . Ideální mřížky jsou tedy efektivnější k použití než jiné mřížky používané v kryptografii . Ideální mřížky se používají v kryptografických systémech s veřejným klíčem NTRUEncrypt a NTRUSign k vytváření účinných kryptografických primitiv . Ideální mřížky také tvoří základní základ kvantové kryptografie , která chrání před útoky spojenými s kvantovými počítači.

Úvod

Schémata RSA a ECC , založená buď na složitosti faktorizace nebo na složitosti problému diskrétního logaritmu , jsou nejoblíbenější asymetrické kryptosystémy, které používají různé klíče k šifrování informací a poté je dešifrují. I přes převahu schémat RSA a ECC je známo, že jsou náchylné k útokům pomocí kvantových počítačů [1] . Kromě toho jsou RSA a ECC spíše neefektivní na velmi malých a omezených zařízeních, jako jsou 8bitové mikrokontroléry AVR , které se dodnes používají v různých oblastech, jako je robotika , energetika, satelitní komunikační systémy a mnoho dalších. Možnou alternativou k výše uvedeným schématům jsou asymetrické kryptosystémy založené na tvrdých problémech v ideálních svazech [2] . Speciální algebraická struktura ideálních svazů může výrazně zmenšit velikost klíče a šifrového textu a zároveň poskytuje účinnou aritmetiku využívající číselně-teoretickou transformaci. Díky použití ideálních mřížek se tedy zvyšuje stupeň ochrany šifrovaných informací [3] .

Základní pojmy

Teorii svazů lze popsat pomocí lineární algebry . Mříž je obvykle viděna jako nějaká rovnoměrně rozložená mřížka bodů v n-rozměrném reálném lineárním prostoru se všemi souřadnicemi být celá čísla . Tato množina tvoří skupinu při sčítání přes souřadnice a je diskrétní , což znamená , že pro každý bod v množině je kolem něj otevřená koule , která neobsahuje žádný další bod v množině , takže mřížka je množinou všech celých lineárních čísel kombinace dané množiny lineárně nezávislých bodů v . Svazy jsou skupiny a ideální svazy jsou ideály [4] . $R^{n}$ ${\displaystyle Z^{n))$

Zejména ideální mřížky odpovídají kruhům tvaru pro nějaký ireducibilní polynom stupně [5] . Základní operací v ideální mřížkové kryptografii je polynomiální násobení . $\mathbb {Z} [x]/\langle f\rangle$ $F$ $n$

Matematická definice ideální mřížky

Ideální mřížka je celočíselná mřížka taková, že pro nějaký daný základ takový, že pro nějaký redukovaný polynom stupně existuje ideální ${\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$

Omezení na : $F$

$F$ - musí být neredukovatelné
norma kruhu nesmí být větší než norma pro jakýkoli polynom ${\displaystyle \lVert g\rVert _{f))$ ${\displaystyle \lVert g\rVert _{\infty ))$ $G$

Lemma

Jestliže je normalizovaný ireducibilní celočíselný polynom stupně , pak každý ideál je izomorfní mřížka plného stupně v , to znamená, že základ tvoří lineárně nezávislé vektory, jejichž souřadnice jsou koeficienty polynomu stupně $F$ $n$ $\mathbb {Z} ^{n}$ $n$ $F$ $n$

Algoritmus pro identifikaci ideálních svazů se základnami plné hodnosti

Nechť je dán základ Podmínka: pokud pokrývá ideální mřížku s ohledem na parametr , pak true , jinak nepravda ${\displaystyle B\in \mathbb {Z} ^{(n,n)))$
$B$ $q$

přivést do hermitovské podoby $B$
$A={\rm {adj}}(B)$ , tedy přidružená matice , je determinantem a $B$ $d=\det(B)$ ${\displaystyle z=B_{(n,n)))$
$P=AMB{\bmod {\ }}d$
pokud jsou všechny sloupce kromě posledního prázdné, pak $P$
vložte do nenulového sloupce (jmenovitě do posledního sloupce ) ${\displaystyle c=P_{(\centerdot ,n)))$ $P$
jinak vrátit false
if , pak existuje množina prvků z vyhovujících všem potom $z\mid c_{i}$ ${\displaystyle c_{i))$ $i=1,\tečky ,n$
použijte čínskou větu o zbytku k nalezení a $q^{\ast }\equiv \ (c/z){\bmod {\ }}(d/z)$ $q^{\ast }\equiv 0{\bmod {\ }}z$
jinak vrátit false
pokud pak $Bq^{\ast }\equiv 0{\bmod {\ }}(d/z)$
vrátit pravdu $q=Bq^{\ast }/d$
jinak vrátit false

Sčítání: matice má formu $M$

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

Příklad použití algoritmu pro identifikaci ideálních svazů se bázemi plné hodnosti

Pomocí tohoto algoritmu [6] lze ověřit, že jen málo svazů je ideálních svazů [6] .
Zvažte příklad: Let a , then $n=2$ $k\in \mathbb {Z} \setminus \lbrace 0,\pm 1\rbrace$

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

je ideální, na rozdíl od

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

$B_2$ s příkladem, který vynalezli Lyubashevsky V. a Missiancio D. [7] $k=2$

Chcete-li použít tento algoritmus, matice musí být v hermitovské normální formě , takže první krok algoritmu je povinný. Determinant je a související matice $B$ $d=2$

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

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

a konečně, matricový produkt je $P=AMB{\bmod {d}}$

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

V tomto okamžiku se algoritmus zastaví, protože všechny sloupce kromě posledního musí být nula, pokud je dokonalá mřížka . $P$ $B$

Běžné problémy v teorii svazů

hledat nejkratší vektor - hledat nejkratší nenulový vektor podle mřížky reprezentované libovolnými bázovými vektory. Ve skutečnosti se obvykle uvažuje přibližná verze problému hledání nejkratšího vektoru, jejímž účelem je získat v mřížce vektor, jehož délka nepřesahuje délku nejkratšího nenulového vektoru o μ(n)- krát, kde μ(n) je aproximační koeficient a je rozměr mřížky. [osm] $n$
hledání nejbližšího vektoru je zobecněním problému hledání nejkratšího vektoru [9]
hledat nejkratší nezávislé vektory [10] .

Aplikace ideálních mřížek

Hašovací funkce odolné proti kolizi

Hašovací funkce odolná proti kolizi je funkce definovaná mapováním tak, že mohutnost množiny (oblast nějakého číselného prostoru) je větší než mohutnost množiny , , takže je obtížné najít kolizi , tzn. pár . Pokud je tedy daný náhodně vybraný , žádný útočník nemůže efektivně (v rozumném čase) najít kolize v , i když kolize jsou [11] . Hlavní využití ideálních svazů v kryptografii je dáno tím, že dostatečně účinné a praktické kolizní hašovací funkce lze sestavit na základě náročnosti nalezení přibližného nejkratšího vektoru v takových svazech [5] . Skupiny vědců studujících ideální kryptografické mřížky zkoumaly hašovací funkce odolné proti kolizi postavené na základě ideálních mřížek, jmenovitě Peikret K. a Rosen S. [12] . Tyto výsledky připravily cestu pro další účinné kryptografické konstrukce, včetně identifikačních a podpisových schémat. ${\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. a Missiancio D. [7] navrhli konstrukce efektivních hašovacích funkcí odolných proti kolizím , které lze dokázat na základě tuhosti nejkratšího vektorového problému pro ideální svazy v nejhorším případě . Tak byly definovány uvažované rodiny hashovacích funkcí pro prvky:

${\displaystyle h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i))$ , kde je vzorek náhodných prvků z , . $m$ $a_{1},\tečky ,a_{m}\in R=\mathbb {Z} _{p}[x]/\langle f\rangle$ ${\displaystyle b=(b_{1},...,b_{m})\in D^{m))$

V tomto případě je velikost klíče, tedy hashovací funkce , definována jako [13] , s použitím rychlého algoritmu Fourierovy transformace , pro vhodný , lze operaci dokončit v čase . Protože je to konstanta, hašování vyžaduje konečný čas . $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ální podpisy

Schémata digitálního podpisu patří mezi nejdůležitější kryptografická primitiva. Lze je získat pomocí jednosměrných funkcí založených na nejhorším případě tuhosti mřížových problémů, ale jsou nepraktické. Od použití problému učení s chybou v kryptografickém kontextu bylo vyvinuto množství nových schémat digitálního podpisu , založených na učení chyb a učení v kruhu chyb. [čtrnáct]

Přímá konstrukce digitálních podpisů je založena na obtížnosti aproximace nejkratšího vektoru v ideálních mřížkách. [15] Schéma V. Lyubashevského a D. Missiancia [15] , založené na ideálních mřížkách, má záruky bezpečnosti i v nejhorším případě a je dnes asymptoticky nejúčinnější konstrukcí, která také umožňuje generovat signatury a kontrolní algoritmy. které běží v téměř lineárním čase [16] .

Jedním z hlavních otevřených problémů, které byly zmíněny ve výše popsaných pracích, je vytvořit jednorázový podpis s podobnou účinností, ale založený na slabším předpokladu tvrdosti. Například by bylo skvělé poskytnout jednorázový podpis se zabezpečením založeným na obtížnosti aproximace problému nejkratšího vektoru (SVP) (v ideálních mřížkách) do . [17] ${\tilde {O}} (n)$

Konstrukce takových digitálních podpisů je založena na standardní konverzi jednorázových podpisů (tj. podpisů, které umožňují bezpečné podepsání jedné zprávy) na generická podpisová schémata, spolu s novým návrhem jednorázového podpisu založeného na mřížce, jehož bezpečnost je nakonec založen na tuhosti nejhoršího případu nejkratší vektorové aproximace , odpovídající ideálům v kruhu pro jakýkoli ireducibilní polynom [16] . $\mathbb {Z} [x]/\langle f\rangle$ $F$

SWIFT hashovací funkce

Hašovací funkce je přiměřeně účinná a lze ji vypočítat asymptoticky v čase pomocí rychlé Fourierovy transformace v komplexních číslech . V praxi to však přináší značnou režii. Sada kryptografických hašovacích funkcí s osvědčenou bezpečností SWIFFT definovaná Missiancio D. a Regevem [16] je ve skutečnosti vysoce optimalizovaná verze výše popsané hašovací funkce využívající rychlou Fourierovu transformaci v . Vektor f je definován jako rovný mocnině 2, takže odpovídající polynom je ireducibilní polynom. Detekce kolizí funkcí SWIFFT je ekvivalentní hledání kolizí v základní funkci ideální mřížky . Deklarovaná vlastnost kolizí SWIFFT [18] je v nejhorším případě podporována v problémech na ideálních svazech. ${\tilde {O}} (m)$ ${\displaystyle \mathbb {Z} _{q))$ ${\displaystyle (1,0,\tečky ,0)\in \mathbb {Z} ^{n))$ $n$ $x^{n}+1$ $f_{A}$

Hashovací algoritmus SWIFFT :

Parametry: Přirozená čísla taková, že mocnina dvou , prvočíslo a . $n,m,q,d$ $n$ $q$ $2n\mid (q-1)$ $n\mid m$
Klíč: Vektory jsou vybírány nezávisle a náhodně v . $m/n$ ${\tilde {a}}_{1},...,{\tilde {a}}_{m/n}$ ${\displaystyle \mathbb {Z} _{q}^{n))$
Vstup: vektor . $m/n$ ${\displaystyle y^{(1)},\tečky ,y^{(m/n)}\in \lbrace 0,\tečky ,d-1\rbrace ^{n))$
Výstup: vector , kde je složka vektorový produkt a je invertibilní matice nad $\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))$

Viz také

Poznámky

↑ Shah, Agam Quantum computing nárok na průlom od IBM . Staženo: 1. června 2015. (neurčitý)
↑ Nicolas Gama, Phong Q. Nguyen Schémata identifikace založená na mřížce bezpečná při aktivních útocích . Predikce redukce mřížky, 1995.
↑ Daniele Micciancio, Oded Regev Lattice-based Cryptography , 2008.
↑ Vadim Lyubashevsky, Chris Peikert, Oded Regev On Ideal Lattices and Learning with Errors Over Rings , 2013.
↑ 1 2 Vadim Lyubashevsky. Schémata identifikace na bázi mřížky zabezpečená při aktivních útocích . In Proceedings of the Practice and theory in public key cryptography , 11th international conference on Public key cryptography , 2008.
↑ 1 2 Jintai Ding a Richard Lindner. Identifikace ideálních mřížek . In Cryptology ePrint Archive, Report 2007/322 , 2007.
↑ 1 2 Lyubashevsky, V., Micciancio, D. Zobecněné kompaktní batohy jsou odolné proti kolizím. . In CBugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, sv. 4052, str. 144-155. Springer, Heidelberg (2006) .
↑ Lenstra A., Lenstra H., Lovasz L. Faktorování polynomů s racionálními koeficienty , 1982.
↑ V.Lyubashevsky, Daniele Micciancio Zobecněné kompaktní batohy jsou odolné proti nárazům . In Mezinárodní kolokvium o automatech, jazycích a programování , 2008.
↑ Složitost problémů s mřížkou: kryptografický pohled. Mezinárodní řada Kluwer ve strojírenství a informatice , < http://cseweb.ucsd.edu/~daniele/papers/book.bib >
↑ O. Goldreich, S. Goldwasser, S. Halevi. Hašování bez kolize z problémů s mřížkou , 1996.
↑ Vadim Lyubashevsky, Chris Peikert a Oded Regev. O ideálních mřížkách a učení s chybami přes kroužky (odkaz není k dispozici) . V Eurocrypt 2010, Lecture Notes in Computer Science , 2010.
↑ Mikl´os Ajtai Representing Hard Latices with O(n log n) Bits , 2005.
↑ Ljubaševskij, Vadim; Peikert, Chris; Regev, Oded. O ideálních svazech a učení s chybami přes kroužky (anglicky) // In Proc. EUROCRYPT, svazek 6110 LNCS: journal. - 2010. - S. 1-23 .
↑ 1 2 Vadim Lyubashevsky a Daniele Micciancio. Asymptoticky efektivní digitální podpisy založené na mřížce . In Sborník příspěvků z 5. konference o teorii kryptografie , 2008.
↑ 1 2 3 Daniele Micciancio, Oded Regev Kryptografie založená na mřížce . In POST-KVANTOVÁ KRYPTOGRAFIE , 2009.
↑ Vadim Lyubashevsky, Daniele Micciancio. Asymptoticky efektivní digitální podpisy založené na mřížce . In Sborník příspěvků z 5. konference o teorii kryptografie , 2008.
↑ Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen [ https://link.springer.com/chapter/10.1007%2F978-3-540-71039-4_4 : Skromný návrh pro FFT Hashing, 2008.

Literatura

J. Hoffstein, N. Howgrave-Graham, J. Pipher, JH Silverman, W. Whyte. Témata v kryptologii - CT-RSA 2003 . - 2003. - S. 122-140.
J. Hoffstein, J. Pipher a J. H. Silverman. NTRU: Kruhový kryptosystém s veřejným klíčem . - 1998. - S. 267-288.
V. Lyubashevsky a D. Micciancio. Generalizované kompaktní batohy jsou odolné proti kolizi . - 2006. - S. 144-155.
Peikert, C., Rosen, A. Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices . - 2006. - S. 145-166.
Craig Gentry. Plně homomorfní šifrování pomocí ideálních mřížek . - 2009. - S. 169-178.
Phong Q. Nguyen, Jacques Stern. Redukce mřížky v kryptologii: Aktualizace // Sborník příspěvků ze 4. mezinárodního sympozia o algoritmické teorii čísel. - Springer-Verlag, 2000. - S. 85-112. — ISBN 3-540-67695-3 .

Odkazy

Agrell E., Eriksson T., Vardy A., Zeger K. Nejbližší vyhledávání bodů v mřížkách // IEEE Trans. informovat. teorie. - 2002. - T. 48 , no. 8 .
Daniele Micciancio. Problém nejkratšího vektoru je {NP} - těžko se aproximuje v rámci nějaké konstanty // SIAM Journal on Computing. - 2001. - T. 30 , no. 6 . - S. 2008-2035 .
Lyubashevsky, V., Micciancio, D. Generalizované kompaktní batohy jsou odolné proti kolizím . - 2006. - S. 1-27 .
Lyubashevsky, V., Micciancio, D. Asymptoticky efektivní digitální podpisy založené na mřížce . — 2008.
Lyubashevsky V. Identifikační schémata založená na mřížce bezpečná při aktivních útokech . - 2008. - S. 1-18 .
Vadim Lyubashevsky, Chris Peikert a Oded Regev. O ideálních mřížkách a učení s chybami přes kroužky . - 2010. - S. 1-27 .
Leo Ducas. Pokroky v kvantové kryptoanalýze ideálních mříží . - 2017. - S. 184-189 .
Eva Bayer Fluckiger. Ideální mříže . - 2017. - S. 1-17 .
Identifikace ideálních mřížek. Jintai Ding a Richard Lindner . - 2007. - S. 1-12 .
Jintai Ding, Xiang Xie, Xiaodong Lin. Jednoduché schéma prokazatelně bezpečné výměny klíčů založené na problému učení s chybami . - 2012. - S. 1-15 .
C. Peikert. Mřížková kryptografie pro internet . - 2014. - S. 1-25 .
V. Ljubaševskij. Mřížové podpisy bez poklopů . - 2014. - S. 1-24 .
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka a Keita Xagawa. Efektivní šifrování veřejného klíče založené na ideálních mřížkách . - 2009. - S. 1-19 .