Krátké celé číslo řešení (SIS) a ring-SIS problémy jsou dva průměrný-případové problémy, které se používají v kryptografie založená na mřížce stavby. Kryptografie založená na mřížce začala v roce 1996 ze klíčového díla Ajtai[1] který představil rodinu jednosměrných funkcí založených na problému SIS. Ukázal, že v průměrném případě je bezpečný, pokud nejkratší vektorový problém
(kde
pro nějakou konstantu
) je v nejhorším případě obtížný.
Průměrné problémy s případy jsou problémy, které je obtížné vyřešit pro některé náhodně vybrané instance. Pro kryptografické aplikace není nejhorší případ složitosti dostatečný a musíme zaručit, že kryptografická konstrukce bude tvrdá na základě průměrné složitosti případu.
Mříže
A plná hodnost mříž
je sada celočíselných lineárních kombinací
lineárně nezávislé vektory
, pojmenovaný základ:

kde
je matice mající ve svých sloupcích základní vektory.
Poznámka: Dáno
dvě základny pro mříž
existují unimodulární matice
takhle
.
Ideální mříž
Definice: Provozovatel rotačního posunu zapnutý
je označen
, a je definována jako:

Cyklické mřížky
Micciancio představen cyklické mřížky ve své práci na zobecnění kompaktu batoh problém na libovolné kroužky.[2] Cyklická mříž je mříž, která je uzavřena pod operátorem rotačního posunu. Formálně jsou cyklické mřížky definovány takto:
Definice: Mříž
je cyklický, pokud
.
Příklady:[3]
sama o sobě je cyklická mříž.- Mřížky odpovídající libovolnému ideálu v kvocientovém polynomiálním kruhu
jsou cyklické:
uvažujme kvocient polynomiálního kruhu
a nechte
být nějaký polynom v
, tj.
kde
pro
.
Definujte koeficient vložení
-izomorfismus modulu
tak jako:
![{ displaystyle { begin {zarovnaný} quad rho: R & rightarrow mathbb {Z} ^ {n} [4pt] rho (x) = sum _ {i = 0} ^ {n-1 } a_ {i} x ^ {i} & mapsto (a_ {0}, ldots, a_ {n-1}) end {zarovnáno}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f395be3f541749f24d91808169dfe685a1f4134d)
Nechat
být ideální. Mřížka odpovídá ideálu
, označeno
, je sublattice z
, a je definován jako

Teorém:
je cyklický právě tehdy
odpovídá nějakému ideálu
v kvocientu polynomiálního kruhu
.
důkaz:
My máme:

Nechat
být libovolným prvkem v
. Poté definujte
. Ale od
je ideální, máme
. Pak,
. Ale,
. Proto,
je cyklický.

Nechat
být cyklická mříž. Proto
.
Definujte množinu polynomů
:
- Od té doby
mříž a tedy aditivní podskupina
,
je aditivní podskupina
. - Od té doby
je cyklický,
.
Proto,
je ideální a následně
.
Nechat
být monický polynom stupně
. Pro kryptografické aplikace
je obvykle vybrán jako neredukovatelný. Ideál generovaný
je:
![{ displaystyle (f (x)): = f (x) cdot mathbb {Z} [x] = {f (x) g (x): forall g (x) in mathbb {Z} [X]}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c970d48b2090104e40be59fc404919c712d29107)
Kvocient polynomiální kruh
oddíly
do tříd ekvivalence polynomů stupně nanejvýš
:
![{ displaystyle R = mathbb {Z} [x] / (f (x)) = vlevo { součet _ {i = 0} ^ {n-1} a_ {i} x ^ {i}: a_ {i} in mathbb {Z} vpravo }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a93ba3d1d81e47803821bcde400820a3f39cef90)
kde sčítání a násobení jsou redukovány modulo
.
Zvažte koeficient vložení
-izomorfismus modulu
. Pak každý ideální
definuje sublattice z
volala ideální mříž.
Definice:
, mřížka odpovídá ideálu
, se nazývá ideální mříž. Přesněji řečeno, zvažte kvocient polynomiálního kruhu
, kde
je ideál generovaný titulem
polynomiální
.
, je sublattice z
, a je definována jako:

Poznámka:[6]
- Ukázalo se, že
i pro malé
je obvykle snadné na ideálních mřížích. Intuice spočívá v tom, že algebraické symetrie způsobují, že minimální vzdálenost ideálu leží v úzkém, snadno vypočítatelném rozsahu. - Využitím poskytnutých algebraických symetrií v ideálních mřížkách lze převést krátký nenulový vektor na
lineárně nezávislé (téměř) stejné délky. Proto na ideálních mřížích
a
jsou ekvivalentní s malou ztrátou.[7] Navíc i pro kvantové algoritmy
a
jsou v nejhorším případě velmi těžké.
Krátký celočíselný problém řešení
SIS a Ring-SIS jsou dva průměrný případové problémy, které se používají v kryptografických konstrukcích založených na mřížce. Kryptografie založená na mřížce začala v roce 1996 ze klíčového díla Ajtai[1] který představil rodinu jednosměrných funkcí založených na problému SIS. Ukázal, že v průměrném případě je bezpečný, pokud
(kde
pro nějakou konstantu
) je v nejhorším případě obtížný.
SISn,m,q,β
Nechat
být
matice se záznamy v
který se skládá z
rovnoměrně náhodné vektory
:
. Najděte nenulový vektor
takové, že:


Řešení pro SIS bez požadovaného omezení délky řešení (
) lze snadno vypočítat pomocí Gaussova eliminace technika. Také požadujeme
, v opačném případě
je triviální řešení.
Aby bylo možné zaručit
má netriviální, krátké řešení, požadujeme:
, a
Teorém: Pro všechny
, jakýkoli
a jakékoli dostatečně velké
(pro každou konstantu
), Řešení
s nezanedbatelnou pravděpodobností je přinejmenším stejně těžké jako řešení
a
pro některé
s vysokou pravděpodobností v nejhorším případě.
Ring-SIS
Problém Ring-SIS, kompaktní analogový problém SIS založený na kruhu, byl studován v roce.[2][8] Uvažují o kvocientovém polynomiálním kruhu
s
a
, respektive, a rozšířit definici norma na vektorech v
na vektory v
jak následuje:
Vzhledem k vektoru
kde
jsou některé polynomy v
. Zvažte koeficient vložení
-izomorfismus modulu
:
![{ displaystyle { begin {aligned} & rho: R rightarrow mathbb {Z} ^ {n} [3pt] rho (x) & = sum _ {i = 0} ^ {n-1 } a_ {i} x ^ {i} mapsto (a_ {0}, ldots, a_ {n-1}) end {zarovnáno}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d39b11e5ae89bbf35960347a99edc465935d66da)
Nechat
. Definujte normu
tak jako:

Alternativně se lepší představy o normě dosáhne využitím kanonické vkládání. Kanonické vložení je definováno jako:

kde
je
komplexní kořen
pro
.
R-SISm,q,β
Vzhledem k kvocientu polynomiálního kruhu
, definovat
. Vybrat
nezávislé rovnoměrně náhodné prvky
. Definujte vektor
. Najděte nenulový vektor
takové, že:


Připomeňme, že k zajištění existence řešení problému se SIS požadujeme
. Problém Ring-SIS nám však poskytuje větší kompaktnost a účinnost: abychom zaručili existenci řešení problému Ring-SIS, požadujeme
.
Definice: The nega-cirkulační matice z
je definován jako:
![{ displaystyle { text {pro}} quad b = součet _ {i = 0} ^ {n-1} b_ {i} x ^ {i} v R, quad operatorname {rot} (b ): = { begin {bmatrix} b_ {0} & - b_ {n-1} & ldots & -b_ {1} [0.3em] b_ {1} & b_ {0} & ldots & -b_ {2} [0.3em] vdots & vdots & ddots & vdots [0.3em] b_ {n-1} & b_ {n-2} & ldots & b_ {0} end {bmatrix} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a9663affde7dc867475147d16af19f77f691c05)
Když je kvocient polynomiální kruh
pro
, množení prstenů
lze efektivně vypočítat prvním formováním
, nega-cirkulační matice
a poté se znásobí
s
, vektor vkládacího koeficientu
(nebo alternativně s
, vektor kanonického koeficientu).
Navíc problém R-SIS je zvláštním případem problému SIS, kde je matice
v SIS je problém omezen na negacirculant bloky:
.[9]
Viz také
Reference
- ^ A b Ajtai, Miklósi. [Generování tvrdých případů mřížových problémů.] Sborník z dvacátého osmého ročníku ACM symposia o teorii práce s počítačem. ACM, 1996.
- ^ A b Micciancio, Daniele. [Zobecněné kompaktní batohy, cyklické mřížky a efektivní jednosměrné funkce z předpokladů nejhoršího případu složitosti.] Foundations of Computer Science, 2002. Proceedings. 43. Výroční sympozium IEEE o. IEEE, 2002.
- ^ Fukshansky, Lenny a Xun Sun. [O geometrii cyklických mřížek.] Diskrétní a výpočetní geometrie 52.2 (2014): 240–259.
- ^ Craig Gentry. Plně homomorfní šifrování pomocí ideálních mřížek. v 41. ACM Symposium on Theory of Computing (STOC), 2009.
- ^ http://web.cse.ohio-state.edu/~lai/5359-aut13/05.Gentry-FHE-concrete-scheme.pdf
- ^ Peikert, Chris. [Desetiletí krystalové mřížky.] Kryptologický archiv ePrint, zpráva 2015/939, 2015.
- ^ Peikert, Chris a Alon Rosen. [Účinné hašení odolné proti kolizi z nejhorších předpokladů na cyklických mřížkách.] Teorie kryptografie. Springer Berlin Heidelberg, 2006. 145–166.
- ^ Lyubashevsky, Vadim a kol. [SWIFFT: Skromný návrh hashování FFT.] Rychlé softwarové šifrování. Springer Berlin Heidelberg, 2008.
- ^ Langlois, Adeline a Damien Stehlé. [Nejhorší redukce pro průměrné případy pro mřížky modulů.] Designs, Codes and Cryptography 75.3 (2015): 565–599.
|
---|
Teoretické číslo | |
---|
Skupinová teoretika | |
---|
Spárování | |
---|
Mříže | |
---|
Nekryptografické | |
---|