Problème de solution entière courte

Les problèmes de solution entière courte (SIS) et de SIS annulaire sont deux problèmes de cas moyen utilisés dans les constructions de cryptographie sur réseau . La cryptographie sur réseau a vu le jour en 1996 grâce à un travail fondateur de Miklós Ajtai , qui a présenté une famille de fonctions à sens unique basées sur le problème SIS. Il a démontré que la sécurité est assurée en moyenne si le problème du vecteur le plus court (où pour une certaine constante ) est difficile dans le pire des cas. ${\displaystyle \mathrm {SVP} _{\gamma <semantics><mrow><mstyle><msub><mrow><mi>S</mi><mi>V</mi><mi>P</mi></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathrm {SVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \gamma =n^{c <semantics><mrow><mstyle><mi>γ</mi><mo>=</mo><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \gamma =n^{c}}</annotation></semantics></math><img src=$ $0 c > 0$ 0

Les problèmes en cas moyen sont ceux qui sont difficiles à résoudre pour certaines instances choisies aléatoirement. En cryptographie, la complexité dans le pire des cas est insuffisante ; il est nécessaire de garantir la difficulté des constructions cryptographiques en se basant sur la complexité en cas moyen.

Réseaux

Un treillis de rang complet est un ensemble de combinaisons linéaires entières de vecteurs linéairement indépendants , appelé base : ${\displaystyle {\mathfrak {L}}\subset \mathbb {R} ^{n <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>⊂</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}\subset \mathbb {R} ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle \{b_{1},\ldots ,b_{n}\ <semantics><mrow><mstyle><mo>{</mo><msub><mi>b</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>b</mi><mrow><mi>n</mi></mrow></msub><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{b_{1},\ldots ,b_{n}\}}</annotation></semantics></math><img src=$

{\displaystyle {\mathfrak {L}}(b_{1},\ldots ,b_{n})=\left\{\sum _{i=1}^{n}z_{i}b_{i}:z_{i}\in \mathbb {Z} ight\}=\{B{\boldsymbol {z}}:{\boldsymbol {z}}\in \mathbb {Z} ^{n}\ <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>(</mo><msub><mi>b</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>b</mi><mrow><mi>n</mi></mrow></msub><mo>)</mo><mo>=</mo><mrow><mo>{</mo><mrow><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>z</mi><mrow><mi>je</mi></mrow></msub><msub><mi>b</mi><mrow><mi>je</mi></mrow></msub><mo>:</mo><msub><mi>z</mi><mrow><mi>je</mi></mrow></msub><mo>∈</mo><mrow><mi>Z</mi></mrow></mrow><mo>}</mo></mrow><mo>=</mo><mo>{</mo><mi>B</mi><mrow><mi>z</mi></mrow><mo>:</mo><mrow><mi>z</mi></mrow><mo>∈</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>}</mo></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}(b_{1},\ldots ,b_{n})=\left\{\sum _{i=1}^{n}z_{i}b_{i}:z_{i}\in \mathbb {Z} ight\}=\{B{\boldsymbol {z}}:{\boldsymbol {z}}\in \mathbb {Z} ^{n}\}}</annotation></semantics></math></span><img src=

où est une matrice dont les colonnes contiennent des vecteurs de base. ${\displaystyle B\in \mathbb {R} ^{n imes n <semantics><mrow><mstyle><mi>B</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle B\in \mathbb {R} ^{n imes n}}</annotation></semantics></math><img src=$

Remarque : Étant donné deux bases pour le treillis , il existe des matrices unimodulaires telles que . ${\displaystyle B_{1},B_{2 <semantics><mrow><mstyle><msub><mi>B</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>B</mi><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle B_{1},B_{2}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{ displaystyle { mathfrak {L}}}</annotation></semantics></math><img src=$ ${\displaystyle U_{1 <semantics><mrow><mstyle><msub><mi>U</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle U_{1}}</annotation></semantics></math><img src=$ ${\displaystyle B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1 <semantics><mrow><mstyle><msub><mi>B</mi><mrow><mn>1</mn></mrow></msub><mo>=</mo><msub><mi>B</mi><mrow><mn>2</mn></mrow></msub><msubsup><mi>U</mi><mrow><mn>1</mn></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msub><mi>B</mi><mrow><mn>2</mn></mrow></msub><mo>=</mo><msub><mi>B</mi><mrow><mn>1</mn></mrow></msub><msub><mi>U</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1}}</annotation></semantics></math><img src=$

réseau idéal

Définition : L’opérateur de décalage rotationnel sur est noté , et est défini comme suit : ${\displaystyle \mathbb {R} ^{n}(n\geq 2) <semantics><mrow><mstyle><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>(</mo><mi>n</mi><mo>≥</mo><mn>2</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {R} ^{n}(n\geq 2)}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {rot} <semantics><mrow><mstyle><mi>pourrir</mi></mstyle></mrow><annotation>{\displaystyle \operatorname {rot} }</annotation></semantics></math><img src=$

{\displaystyle \forall {\boldsymbol {x}}=(x_{1},\ldots ,x_{n-1},x_{n})\in \mathbb {R} ^{n}:\operatorname {rot} (x_{1},\ldots ,x_{n-1},x_{n})=(x_{n},x_{1},\ldots ,x_{n-1}) <semantics><mrow><mstyle><mi>∀</mi><mrow><mi>x</mi></mrow><mo>=</mo><mo>(</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi></mrow></msub><mo>)</mo><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>:</mo><mi>pourrir</mi><mo>⁡</mo><mo>(</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi></mrow></msub><mo>)</mo><mo>=</mo><mo>(</mo><msub><mi>x</mi><mrow><mi>n</mi></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \forall {\boldsymbol {x}}=(x_{1},\ldots ,x_{n-1},x_{n})\in \mathbb {R} ^{n}:\operatorname {rot} (x_{1},\ldots ,x_{n-1},x_{n})=(x_{n},x_{1},\ldots ,x_{n-1})}</annotation></semantics></math></span><img src=

Réseaux cycliques

Micciancio a introduit les treillis cycliques dans ses travaux de généralisation du problème du sac à dos compact aux anneaux quelconques. Un treillis cyclique est un treillis stable par translation rotationnelle. Formellement, les treillis cycliques sont définis comme suit :

Définition : Un réseau est cyclique si . ${\displaystyle {\mathfrak {L}}\subseteq \mathbb {Z} ^{n <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>⊆</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}\subseteq \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L <semantics><mrow><mstyle><mi>∀</mi><mrow><mi>x</mi></mrow><mo>∈</mo><mrow><mrow><mi>L</mi></mrow></mrow><mo>:</mo><mi>rot</mi><mo>⁡</mo><mo>(</mo><mrow><mi>x</mi></mrow><mo>)</mo><mo>∈</mo><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}}</annotation></semantics></math><img src=$

Exemples :

${\displaystyle \mathbb {Z} ^{n <semantics><mrow><mstyle><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$
Les réseaux correspondant à un idéal quelconque de l'anneau des polynômes quotients sont cycliques : ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}</annotation></semantics></math><img src=$

Considérons l'anneau des polynômes quotients , et soit un polynôme dans , c'est-à-dire où pour . ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}</annotation></semantics></math><img src=$ ${\displaystyle p(x) <semantics><mrow><mstyle><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle p(x)}</annotation></semantics></math><img src=$ ${\displaystyle R <semantics><mrow><mstyle><mi>R</mi></mstyle></mrow><annotation>{\displaystyle R}</annotation></semantics></math><img src=$ ${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i <semantics><mrow><mstyle><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}}</annotation></semantics></math><img src=$ ${\displaystyle a_{i}\in \mathbb {Z} <semantics><mrow><mstyle><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mrow><mi>Z</mi></mrow></mstyle></mrow><annotation>{\displaystyle a_{i}\in \mathbb {Z} }</annotation></semantics></math><img src=$ ${\displaystyle i=0,\ldots ,n-1 <semantics><mrow><mstyle><mi>i</mi><mo>=</mo><mn>0</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle i=0,\ldots ,n-1}</annotation></semantics></math><img src=$

Définissons l' isomorphisme de -module de coefficient d'immersion comme suit : ${\displaystyle \mathbb {Z} <semantics><mrow><mstyle><mrow><mi>Z</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} }</annotation></semantics></math><img src=$ ${\displaystyle ho <semantics><mrow><mstyle><mi>ρ</mi></mstyle></mrow><annotation>{\displaystyle ho }</annotation></semantics></math><img src=$

{\displaystyle {\begin{aligned}\quad ho :R& ightarrow \mathbb {Z} ^{n}\\[4pt]p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mspace></mspace><mi>ρ</mi><mo>:</mo><mi>R</mi></mtd><mtd><mi></mi><mo>→</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mtd></mtr><mtr><mtd><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup></mtd><mtd><mi></mi><mo>↦</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\quad ho :R& ightarrow \mathbb {Z} ^{n}\\[4pt]p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned}}}</annotation></semantics></math></span><img src=

Soit un idéal. Le réseau correspondant à l'idéal , noté , est un sous-réseau de , et est défini comme ${\displaystyle I\subset R <semantics><mrow><mstyle><mi>I</mi><mo>⊂</mo><mi>R</mi></mstyle></mrow><annotation>{\displaystyle I\subset R}</annotation></semantics></math><img src=$ ${\displaystyle I\subset R <semantics><mrow><mstyle><mi>I</mi><mo>⊂</mo><mi>R</mi></mstyle></mrow><annotation>{\displaystyle I\subset R}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L}}_{I <semantics><mrow><mstyle><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}_{I}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} ^{n <semantics><mrow><mstyle><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$

{\displaystyle {\mathfrak {L}}_{I}:= ho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I ight\}\subset \mathbb {Z} ^{n}. <semantics><mrow><mstyle><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub><mo>:=</mo><mi>ρ</mi><mo>(</mo><mi>I</mi><mo>)</mo><mo>=</mo><mrow><mo>{</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∣</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>∈</mo><mi>I</mi></mrow><mo>}</mo></mrow><mo>⊂</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}_{I}:= ho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I ight\}\subset \mathbb {Z} ^{n}.}</annotation></semantics></math></span><img src=

Théorème : est cyclique si et seulement si correspond à un idéal dans l'anneau des polynômes quotients . ${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>⊂</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>I</mi></mstyle></mrow><annotation>{\displaystyle I}</annotation></semantics></math><img src=$ ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}</annotation></semantics></math><img src=$

Preuve : Nous avons : ${\displaystyle \Leftarrow ) <semantics><mrow><mstyle><mo>⇐</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \Leftarrow )}</annotation></semantics></math><img src=$

{\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}:= ho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I ight\ <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>=</mo><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub><mo>:=</mo><mi>ρ</mi><mo>(</mo><mi>I</mi><mo>)</mo><mo>=</mo><mrow><mo>{</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∣</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>∈</mo><mi>I</mi></mrow><mo>}</mo></mrow></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}:= ho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I ight\}}</annotation></semantics></math></span><img src=

Soit un élément quelconque de . Définissons alors . Puisque est un idéal, on a . Donc, . Mais, . Par conséquent, est cyclique. ${\displaystyle (a_{0},\ldots ,a_{n-1}) <semantics><mrow><mstyle><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (a_{0},\ldots ,a_{n-1})}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}}</annotation></semantics></math><img src=$ ${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I <semantics><mrow><mstyle><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>∈</mo><mi>I</mi></mstyle></mrow><annotation>{\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>I</mi></mstyle></mrow><annotation>{\displaystyle I}</annotation></semantics></math><img src=$ ${\displaystyle xp(x)\in I <semantics><mrow><mstyle><mi>x</mi><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>∈</mo><mi>I</mi></mstyle></mrow><annotation>{\displaystyle xp(x)\in I}</annotation></semantics></math><img src=$ ${\displaystyle ho (xp(x))\in {\mathfrak {L}}_{I <semantics><mrow><mstyle><mi>ρ</mi><mo>(</mo><mi>x</mi><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>∈</mo><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle ho (xp(x))\in {\mathfrak {L}}_{I}}</annotation></semantics></math><img src=$ ${\displaystyle ho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I <semantics><mrow><mstyle><mi>ρ</mi><mo>(</mo><mi>x</mi><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>=</mo><mi>rot</mi><mo>⁡</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∈</mo><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle ho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I}}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}}</annotation></semantics></math><img src=$

${\displaystyle \Rightarrow ) <semantics><mrow><mstyle><mo>⇒</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \Rightarrow )}</annotation></semantics></math><img src=$

Soit un réseau cyclique. Donc . ${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>⊂</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L <semantics><mrow><mstyle><mi>∀</mi><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∈</mo><mrow><mrow><mi>L</mi></mrow></mrow><mo>:</mo><mi>rot</mi><mo>⁡</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∈</mo><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}}</annotation></semantics></math><img src=$

Définir l'ensemble des polynômes : ${\displaystyle I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}} ight\ <semantics><mrow><mstyle><mi>I</mi><mo>:=</mo><mrow><mo>{</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>∣</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∈</mo><mrow><mrow><mi>L</mi></mrow></mrow></mrow><mo>}</mo></mrow></mstyle></mrow><annotation>{\displaystyle I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}} ight\}}</annotation></semantics></math><img src=$

Puisqu'un treillis et donc un sous-groupe additif de , est un sous-groupe additif de . ${\displaystyle {\mathfrak {L <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} ^{n <semantics><mrow><mstyle><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle I\subset R <semantics><mrow><mstyle><mi>I</mi><mo>⊂</mo><mi>R</mi></mstyle></mrow><annotation>{\displaystyle I\subset R}</annotation></semantics></math><img src=$ ${\displaystyle R <semantics><mrow><mstyle><mi>R</mi></mstyle></mrow><annotation>{\displaystyle R}</annotation></semantics></math><img src=$
Puisque est cyclique, . ${\displaystyle {\mathfrak {L <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}}</annotation></semantics></math><img src=$ ${\displaystyle \forall p(x)\in I:xp(x)\in I <semantics><mrow><mstyle><mi>∀</mi><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>∈</mo><mi>I</mi><mo>:</mo><mi>x</mi><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>∈</mo><mi>I</mi></mstyle></mrow><annotation>{\displaystyle \forall p(x)\in I:xp(x)\in I}</annotation></semantics></math><img src=$

Par conséquent, est un idéal, et par conséquent, . ${\displaystyle I\subset R <semantics><mrow><mstyle><mi>I</mi><mo>⊂</mo><mi>R</mi></mstyle></mrow><annotation>{\displaystyle I\subset R}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I <semantics><mrow><mstyle><mrow><mrow><mi>L</mi></mrow></mrow><mo>=</mo><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}}</annotation></semantics></math><img src=$

réseaux idéaux

Source :

Soit un polynôme unitaire de degré . Pour les applications cryptographiques, on choisit généralement que soit irréductible. L'idéal engendré par est : ${\displaystyle f(x)\in \mathbb {Z} [x] <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>∈</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo></mstyle></mrow><annotation>{\displaystyle f(x)\in \mathbb {Z} [x]}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle f(x) <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f(x)}</annotation></semantics></math><img src=$ ${\displaystyle f(x) <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f(x)}</annotation></semantics></math><img src=$

{\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}. <semantics><mrow><mstyle><mo>(</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>:=</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>⋅</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mo>=</mo><mo>{</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mi>g</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>:</mo><mi>∀</mi><mi>g</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>∈</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mo>}</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}.}</annotation></semantics></math></span><img src=

L'anneau des polynômes quotients se partitionne en classes d'équivalence de polynômes de degré au plus : ${\displaystyle R=\mathbb {Z} [x]/(f(x)) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(f(x))}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} [x] <semantics><mrow><mstyle><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} [x]}</annotation></semantics></math><img src=$ ${\displaystyle n-1 <semantics><mrow><mstyle><mi>n</mi><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle n-1}</annotation></semantics></math><img src=$

{\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} ight\ <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>=</mo><mrow><mo>{</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>:</mo><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mrow><mi>Z</mi></mrow></mrow><mo>}</mo></mrow></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} ight\}}</annotation></semantics></math></span><img src=

où l'addition et la multiplication sont réduites modulo . ${\displaystyle f(x) <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f(x)}</annotation></semantics></math><img src=$

Considérons l' isomorphisme de -modules à coefficients d'immersion . Alors, chaque idéal de définit un sous-treillis de appelé treillis d'idéaux . ${\displaystyle \mathbb {Z} <semantics><mrow><mstyle><mrow><mi>Z</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} }</annotation></semantics></math><img src=$ ${\displaystyle ho <semantics><mrow><mstyle><mi>ρ</mi></mstyle></mrow><annotation>{\displaystyle ho }</annotation></semantics></math><img src=$ ${\displaystyle R <semantics><mrow><mstyle><mi>R</mi></mstyle></mrow><annotation>{\displaystyle R}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} ^{n <semantics><mrow><mstyle><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$

Définition : Le réseau associé à un idéal est appelé réseau idéal. Plus précisément, considérons un anneau de polynômes quotients , où est l’idéal engendré par un polynôme de degré . est un sous-réseau de et est défini comme : ${\displaystyle {\mathfrak {L}}_{I <semantics><mrow><mstyle><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}_{I}}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>I</mi></mstyle></mrow><annotation>{\displaystyle I}</annotation></semantics></math><img src=$ ${\displaystyle R=\mathbb {Z} [x]/(p(x)) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(p(x))}</annotation></semantics></math><img src=$ ${\displaystyle (p(x)) <semantics><mrow><mstyle><mo>(</mo><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (p(x))}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle p(x)\in \mathbb {Z} [x] <semantics><mrow><mstyle><mi>p</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>∈</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo></mstyle></mrow><annotation>{\displaystyle p(x)\in \mathbb {Z} [x]}</annotation></semantics></math><img src=$ ${\displaystyle {\mathfrak {L}}_{I <semantics><mrow><mstyle><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}_{I}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} ^{n <semantics><mrow><mstyle><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} ^{n}}</annotation></semantics></math><img src=$

{\displaystyle {\mathfrak {L}}_{I}:= ho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I ight\}\subset \mathbb {Z} ^{n}. <semantics><mrow><mstyle><msub><mrow><mrow><mi>L</mi></mrow></mrow><mrow><mi>I</mi></mrow></msub><mo>:=</mo><mi>ρ</mi><mo>(</mo><mi>I</mi><mo>)</mo><mo>=</mo><mrow><mo>{</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mn>0</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>)</mo><mo>∣</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>∈</mo><mi>I</mi></mrow><mo>}</mo></mrow><mo>⊂</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\mathfrak {L}}_{I}:= ho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I ight\}\subset \mathbb {Z} ^{n}.}</annotation></semantics></math></span><img src=

Remarque :

Il s'avère que même pour de petites valeurs de , le calcul est généralement aisé sur les réseaux idéaux. L'explication réside dans le fait que les symétries algébriques impliquent que la distance minimale d'un idéal se situe dans un intervalle étroit et facilement calculable. ${\displaystyle { ext{GapSVP}}_{\gamma <semantics><mrow><mstyle><msub><mrow><mtext>GapSVP</mtext></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle { ext{GapSVP}}_{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \gamma =\operatorname {poly(n)} <semantics><mrow><mstyle><mi>γ</mi><mo>=</mo><mrow><mi>p</mi><mi>o</mi><mi>l</mi><mi>y</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle \gamma =\operatorname {poly(n)} }</annotation></semantics></math><img src=$
En exploitant les symétries algébriques inhérentes aux réseaux idéaux, on peut convertir un vecteur court non nul en vecteurs linéairement indépendants de longueur (quasi) identique. Par conséquent, sur les réseaux idéaux, et sont équivalents à une perte négligeable. De plus, même pour les algorithmes quantiques , et sont considérés comme extrêmement difficiles à résoudre dans le pire des cas. ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle \mathrm {SVP} _{\gamma <semantics><mrow><mstyle><msub><mrow><mi>S</mi><mi>V</mi><mi>P</mi></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathrm {SVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \mathrm {SIVP} _{\gamma <semantics><mrow><mstyle><msub><mrow><mi>S</mi><mi>I</mi><mi>V</mi><mi>P</mi></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathrm {SIVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \mathrm {SVP} _{\gamma <semantics><mrow><mstyle><msub><mrow><mi>S</mi><mi>V</mi><mi>P</mi></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathrm {SVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \mathrm {SIVP} _{\gamma <semantics><mrow><mstyle><msub><mrow><mi>S</mi><mi>I</mi><mi>V</mi><mi>P</mi></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathrm {SIVP} _{\gamma }}</annotation></semantics></math><img src=$

Problème de solution entière courte

Le problème de la solution entière courte (SIS) est un problème de cas moyen utilisé dans les constructions cryptographiques sur réseau. La cryptographie sur réseau a vu le jour en 1996 grâce à un travail fondateur d'Ajtai qui a présenté une famille de fonctions à sens unique basées sur le problème SIS. Il a démontré que la sécurité est assurée dans le cas moyen si (où pour une certaine constante ) est difficile à atteindre dans le pire des cas. Outre ses applications en cryptographie classique, le problème SIS et ses variantes sont utilisés dans plusieurs schémas de sécurité post-quantiques, notamment CRYSTALS-Dilithium et Falcon . ${\displaystyle \mathrm {SVP} _{\gamma <semantics><mrow><mstyle><msub><mrow><mi>S</mi><mi>V</mi><mi>P</mi></mrow><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathrm {SVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \gamma =n^{c <semantics><mrow><mstyle><mi>γ</mi><mo>=</mo><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \gamma =n^{c}}</annotation></semantics></math><img src=$ $0 c > 0$ 0

SIS _{q , n , m , β}

Soit une matrice dont les coefficients appartiennent à et qui est composée de vecteurs aléatoires uniformes : . Trouver un vecteur non nul tel que pour une certaine norme : ${\displaystyle A\in \mathbb {Z} _{q}^{n imes m <semantics><mrow><mstyle><mi>A</mi><mo>∈</mo><msubsup><mrow><mi>Z</mi></mrow><mrow><mi>q</mi></mrow><mrow><mi>n</mi><mo>×</mo><mi>m</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle A\in \mathbb {Z} _{q}^{n imes m}}</annotation></semantics></math><img src=$ ${\displaystyle n imes m <semantics><mrow><mstyle><mi>n</mi><mo>×</mo><mi>m</mi></mstyle></mrow><annotation>{\displaystyle n imes m}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {Z} _{q <semantics><mrow><mstyle><msub><mrow><mi>Z</mi></mrow><mrow><mi>q</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathbb {Z} _{q}}</annotation></semantics></math><img src=$ ${\displaystyle m <semantics><mrow><mstyle><mi>m</mi></mstyle></mrow><annotation>{\displaystyle m}</annotation></semantics></math><img src=$ ${\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n <semantics><mrow><mstyle><mrow><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub></mrow><mo>∈</mo><msubsup><mrow><mi>Z</mi></mrow><mrow><mi>q</mi></mrow><mrow><mi>n</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}}</annotation></semantics></math><img src=$ ${\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}] <semantics><mrow><mstyle><mi>A</mi><mo>=</mo><mo>[</mo><mrow><msub><mi>a</mi><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>|</mo></mrow><mo>⋯</mo><mrow><mo>|</mo></mrow><mrow><msub><mi>a</mi><mrow><mi>m</mi></mrow></msub></mrow><mo>]</mo></mstyle></mrow><annotation>{\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]}</annotation></semantics></math><img src=$ ${\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m <semantics><mrow><mstyle><mrow><mi>x</mi></mrow><mo>∈</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m}}</annotation></semantics></math><img src=$ ${\displaystyle \|\cdot \| <semantics><mrow><mstyle><mo>‖</mo><mo>⋅</mo><mo>‖</mo></mstyle></mrow><annotation>{\displaystyle \|\cdot \|}</annotation></semantics></math><img src=$

${\displaystyle 0<\|{\boldsymbol {x}}\|\leq \beta <semantics><mrow><mstyle><mn>0</mn><mo><</mo><mo>‖</mo><mrow><mi>x</mi></mrow><mo>‖</mo><mo>≤</mo><mi>β</mi></mstyle></mrow><annotation>{\displaystyle 0<\|{\boldsymbol {x}}\|\leq \beta }</annotation></semantics></math><img src=$
${\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mi>A</mi></mrow></msub><mo>(</mo><mrow><mi>x</mi></mrow><mo>)</mo><mo>:=</mo><mi>A</mi><mrow><mi>x</mi></mrow><mo>=</mo><mrow><mn>0</mn></mrow><mo>∈</mo><msubsup><mrow><mi>Z</mi></mrow><mrow><mi>q</mi></mrow><mrow><mi>n</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}}</annotation></semantics></math><img src=$

Une solution au problème SIS sans la contrainte requise sur la longueur de la solution ( ) est facile à calculer à l'aide de la méthode d'élimination de Gauss . Nous exigeons également que , sinon la solution est triviale. ${\displaystyle \|{\boldsymbol {x}}\|\leq \beta <semantics><mrow><mstyle><mo>‖</mo><mrow><mi>x</mi></mrow><mo>‖</mo><mo>≤</mo><mi>β</mi></mstyle></mrow><annotation>{\displaystyle \|{\boldsymbol {x}}\|\leq \beta }</annotation></semantics></math><img src=$ ${\displaystyle \beta <q <semantics><mrow><mstyle><mi>β</mi><mo><</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle \beta <q}</annotation></semantics></math><img src=$ ${\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m <semantics><mrow><mstyle><mrow><mi>x</mi></mrow><mo>=</mo><mo>(</mo><mi>q</mi><mo>,</mo><mn>0</mn><mo>,</mo><mo>…</mo><mo>,</mo><mn>0</mn><mo>)</mo><mo>∈</mo><msup><mrow><mi>Z</mi></mrow><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}}</annotation></semantics></math><img src=$

Afin de garantir l'existence d'une solution courte et non triviale, nous exigeons : ${\displaystyle f_{A}({\boldsymbol {x}}) <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mi>A</mi></mrow></msub><mo>(</mo><mrow><mi>x</mi></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f_{A}({\boldsymbol {x}})}</annotation></semantics></math><img src=$

${\displaystyle \beta \geq {\sqrt {n\log q <semantics><mrow><mstyle><mi>β</mi><mo>≥</mo><mrow><msqrt><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>q</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle \beta \geq {\sqrt {n\log q}}}</annotation></semantics></math><img src=$
${\displaystyle m\geq n\log q <semantics><mrow><mstyle><mi>m</mi><mo>≥</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle m\geq n\log q}</annotation></semantics></math><img src=$

Théorème : Pour tout , tout , et tout suffisamment grand (pour toute constante ), résoudre avec une probabilité non négligeable est au moins aussi difficile que de résoudre et pour certains avec une probabilité élevée dans le pire des cas. ${\displaystyle m=\operatorname {poly} (n) <semantics><mrow><mstyle><mi>m</mi><mo>=</mo><mi>poly</mi><mo>⁡</mo><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle m=\operatorname {poly} (n)}</annotation></semantics></math><img src=$ $0 β > 0$ 0 ${\displaystyle q\geq \beta n^{c <semantics><mrow><mstyle><mi>q</mi><mo>≥</mo><mi>β</mi><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle q\geq \beta n^{c}}</annotation></semantics></math><img src=$ $0 c > 0$ 0 ${\displaystyle \operatorname {SIS} _{n,m,q,\beta <semantics><mrow><mstyle><msub><mi>SIS</mi><mrow><mi>n</mi><mo>,</mo><mi>m</mi><mo>,</mo><mi>q</mi><mo>,</mo><mi>β</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \operatorname {SIS} _{n,m,q,\beta }}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {GapSVP} _{\gamma <semantics><mrow><mstyle><msub><mi>GapSVP</mi><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \operatorname {GapSVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {SIVP} _{\gamma <semantics><mrow><mstyle><msub><mi>SIVP</mi><mrow><mi>γ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \operatorname {SIVP} _{\gamma }}</annotation></semantics></math><img src=$ ${\displaystyle \gamma =\beta \cdot O({\sqrt {n}}) <semantics><mrow><mstyle><mi>γ</mi><mo>=</mo><mi>β</mi><mo>⋅</mo><mi>O</mi><mo>(</mo><mrow><msqrt><mi>n</mi></msqrt></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \gamma =\beta \cdot O({\sqrt {n}})}</annotation></semantics></math><img src=$

R-SIS _{q , n , m , β}

Le problème SIS résolu sur un anneau idéal est également appelé problème Ring-SIS ou R-SIS. Ce problème considère un anneau de polynômes quotients tel que pour un certain entier et avec une certaine norme . Les cas où il existe un entier tel que , car cela restreint le quotient aux polynômes cyclotomiques, présentent un intérêt particulier . ${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x)) <semantics><mrow><mstyle><msub><mi>R</mi><mrow><mi>q</mi></mrow></msub><mo>=</mo><msub><mrow><mi>Z</mi></mrow><mrow><mi>q</mi></mrow></msub><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}</annotation></semantics></math><img src=$ ${\displaystyle f(x)=x^{n}-1 <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle f(x)=x^{n}-1}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle \|\cdot \| <semantics><mrow><mstyle><mo>‖</mo><mo>⋅</mo><mo>‖</mo></mstyle></mrow><annotation>{\displaystyle \|\cdot \|}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle n=2^{k <semantics><mrow><mstyle><mi>n</mi><mo>=</mo><msup><mn>2</mn><mrow><mi>k</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n=2^{k}}</annotation></semantics></math><img src=$

Nous définissons alors le problème comme suit :

Sélectionner des éléments aléatoires uniformément aléatoires et indépendants . Définir le vecteur . Trouver un vecteur non nul tel que : ${\displaystyle m <semantics><mrow><mstyle><mi>m</mi></mstyle></mrow><annotation>{\displaystyle m}</annotation></semantics></math><img src=$ ${\displaystyle a_{i}\in R_{q <semantics><mrow><mstyle><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><msub><mi>R</mi><mrow><mi>q</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle a_{i}\in R_{q}}</annotation></semantics></math><img src=$ ${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m <semantics><mrow><mstyle><mrow><mrow><mover><mi>a</mi><mo>→</mo></mover></mrow></mrow><mo>:=</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>m</mi></mrow></msub><mo>)</mo><mo>∈</mo><msubsup><mi>R</mi><mrow><mi>q</mi></mrow><mrow><mi>m</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}}</annotation></semantics></math><img src=$ ${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m <semantics><mrow><mstyle><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>:=</mo><mo>(</mo><msub><mi>z</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>z</mi><mrow><mi>m</mi></mrow></msub><mo>)</mo><mo>∈</mo><msup><mi>R</mi><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}</annotation></semantics></math><img src=$

${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta <semantics><mrow><mstyle><mn>0</mn><mo><</mo><mo>‖</mo><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>‖</mo><mo>≤</mo><mi>β</mi></mstyle></mrow><annotation>{\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }</annotation></semantics></math><img src=$
${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mrow><mover><mi>a</mi><mo>→</mo></mover></mrow></mrow></msub><mo>(</mo><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>)</mo><mo>:=</mo><msup><mrow><mrow><mover><mi>a</mi><mo>→</mo></mover></mrow></mrow><mrow><mi>T</mi></mrow></msup><mo>.</mo><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>.</mo><msub><mi>z</mi><mrow><mi>i</mi></mrow></msub><mo>=</mo><mn>0</mn><mo>∈</mo><msub><mi>R</mi><mrow><mi>q</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}}</annotation></semantics></math><img src=$

Rappelons que pour garantir l'existence d'une solution au problème SIS, nous exigeons . Cependant, le problème Ring-SIS offre une plus grande compacité et une meilleure efficacité : pour garantir l'existence d'une solution au problème Ring-SIS, nous exigeons . ${\displaystyle m\approx n\log q <semantics><mrow><mstyle><mi>m</mi><mo>≈</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle m\approx n\log q}</annotation></semantics></math><img src=$ ${\displaystyle m\approx \log q <semantics><mrow><mstyle><mi>m</mi><mo>≈</mo><mi>log</mi><mo>⁡</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle m\approx \log q}</annotation></semantics></math><img src=$

Définition : La matrice négativement circulante de est définie comme : ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$

{\displaystyle { ext{for}}\quad b=\sum _{i=0}^{n-1}b_{i}x^{i}\in 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 <semantics><mrow><mstyle><mrow><mtext>for</mtext></mrow><mspace></mspace><mi>b</mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>b</mi><mrow><mi>i</mi></mrow></msub><msup><mi>x</mi><mrow><mi>i</mi></mrow></msup><mo>∈</mo><mi>R</mi><mo>,</mo><mspace></mspace><mi>rot</mi><mo>⁡</mo><mo>(</mo><mi>b</mi><mo>)</mo><mo>:=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>b</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mo>−</mo><msub><mi>b</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub></mtd><mtd><mo>…</mo></mtd><mtd><mo>−</mo><msub><mi>b</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>b</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>b</mi><mrow><mn>0</mn></mrow></msub></mtd><mtd><mo>…</mo></mtd><mtd><mo>−</mo><msub><mi>b</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><mo>⋮</mo></mtd><mtd><mo>⋮</mo></mtd><mtd><mo>⋱</mo></mtd><mtd><mo>⋮</mo></mtd></mtr><mtr><mtd><msub><mi>b</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>b</mi><mrow><mi>n</mi><mo>−</mo><mn>2</mn></mrow></msub></mtd><mtd><mo>…</mo></mtd><mtd><msub><mi>b</mi><mrow><mn>0</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle { ext{for}}\quad b=\sum _{i=0}^{n-1}b_{i}x^{i}\in 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}}}</annotation></semantics></math></span><img src=

Lorsque l' anneau de polynômes quotients est pour , la multiplication d'anneaux peut être calculée efficacement en formant d'abord , la matrice néga-circulante de , puis en multipliant avec , le vecteur de coefficients d'immersion de (ou, alternativement avec , le vecteur de coefficients canonique. ${\displaystyle R=\mathbb {Z} [x]/(x^{n}+1) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>+</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(x^{n}+1)}</annotation></semantics></math><img src=$ ${\displaystyle n=2^{k <semantics><mrow><mstyle><mi>n</mi><mo>=</mo><msup><mn>2</mn><mrow><mi>k</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n=2^{k}}</annotation></semantics></math><img src=$ ${\displaystyle a_{i}.p_{i <semantics><mrow><mstyle><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>.</mo><msub><mi>p</mi><mrow><mi>i</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle a_{i}.p_{i}}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {rot} (a_{i}) <semantics><mrow><mstyle><mi>rot</mi><mo>⁡</mo><mo>(</mo><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {rot} (a_{i})}</annotation></semantics></math><img src=$ ${\displaystyle a_{i <semantics><mrow><mstyle><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle a_{i}}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {rot} (a_{i}) <semantics><mrow><mstyle><mi>rot</mi><mo>⁡</mo><mo>(</mo><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {rot} (a_{i})}</annotation></semantics></math><img src=$ ${\displaystyle ho (p_{i}(x))\in Z^{n <semantics><mrow><mstyle><mi>ρ</mi><mo>(</mo><msub><mi>p</mi><mrow><mi>i</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>∈</mo><msup><mi>Z</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle ho (p_{i}(x))\in Z^{n}}</annotation></semantics></math><img src=$ ${\displaystyle p_{i <semantics><mrow><mstyle><msub><mi>p</mi><mrow><mi>i</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle p_{i}}</annotation></semantics></math><img src=$ ${\displaystyle \sigma (p_{i}(x))\in Z^{n <semantics><mrow><mstyle><mi>σ</mi><mo>(</mo><msub><mi>p</mi><mrow><mi>i</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>∈</mo><msup><mi>Z</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \sigma (p_{i}(x))\in Z^{n}}</annotation></semantics></math><img src=$

De plus, le problème R-SIS est un cas particulier du problème SIS où la matrice du problème SIS est restreinte aux blocs négacirculants : . ${\displaystyle A <semantics><mrow><mstyle><mi>A</mi></mstyle></mrow><annotation>{\displaystyle A}</annotation></semantics></math><img src=$ ${\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})] <semantics><mrow><mstyle><mi>A</mi><mo>=</mo><mo>[</mo><mi>rot</mi><mo>⁡</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>1</mn></mrow></msub><mo>)</mo><mrow><mo>|</mo></mrow><mo>⋯</mo><mrow><mo>|</mo></mrow><mi>rot</mi><mo>⁡</mo><mo>(</mo><msub><mi>a</mi><mrow><mi>m</mi></mrow></msub><mo>)</mo><mo>]</mo></mstyle></mrow><annotation>{\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]}</annotation></semantics></math><img src=$

M-SIS _{q , n , d , m , β}

Le problème SIS résolu sur un treillis de modules est également appelé problème Module-SIS ou M-SIS. Comme le problème R-SIS, ce problème considère l'anneau des polynômes quotients et , avec un intérêt particulier pour les cas où est une puissance de 2. Soit alors un module de rang tel que et soit une norme quelconque sur . ${\displaystyle R=\mathbb {Z} [x]/(f(x)) <semantics><mrow><mstyle><mi>R</mi><mo>=</mo><mrow><mi>Z</mi></mrow><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R=\mathbb {Z} [x]/(f(x))}</annotation></semantics></math><img src=$ ${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x)) <semantics><mrow><mstyle><msub><mi>R</mi><mrow><mi>q</mi></mrow></msub><mo>=</mo><msub><mrow><mi>Z</mi></mrow><mrow><mi>q</mi></mrow></msub><mo>[</mo><mi>x</mi><mo>]</mo><mrow><mo>/</mo></mrow><mo>(</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}</annotation></semantics></math><img src=$ ${\displaystyle f(x)=x^{n}-1 <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle f(x)=x^{n}-1}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle M\subseteq R^{d <semantics><mrow><mstyle><mi>M</mi><mo>⊆</mo><msup><mi>R</mi><mrow><mi>d</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle M\subseteq R^{d}}</annotation></semantics></math><img src=$ ${\displaystyle \|\cdot \| <semantics><mrow><mstyle><mo>‖</mo><mo>⋅</mo><mo>‖</mo></mstyle></mrow><annotation>{\displaystyle \|\cdot \|}</annotation></semantics></math><img src=$ ${\displaystyle R_{q}^{m <semantics><mrow><mstyle><msubsup><mi>R</mi><mrow><mi>q</mi></mrow><mrow><mi>m</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle R_{q}^{m}}</annotation></semantics></math><img src=$

Nous définissons alors le problème comme suit :

Sélectionner des éléments aléatoires uniformément aléatoires et indépendants . Définir le vecteur . Trouver un vecteur non nul tel que : ${\displaystyle m <semantics><mrow><mstyle><mi>m</mi></mstyle></mrow><annotation>{\displaystyle m}</annotation></semantics></math><img src=$ ${\displaystyle a_{i}\in R_{q}^{d <semantics><mrow><mstyle><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><msubsup><mi>R</mi><mrow><mi>q</mi></mrow><mrow><mi>d</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle a_{i}\in R_{q}^{d}}</annotation></semantics></math><img src=$ ${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d imes m <semantics><mrow><mstyle><mrow><mrow><mover><mi>a</mi><mo>→</mo></mover></mrow></mrow><mo>:=</mo><mo>(</mo><msub><mi>a</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>m</mi></mrow></msub><mo>)</mo><mo>∈</mo><msubsup><mi>R</mi><mrow><mi>q</mi></mrow><mrow><mi>d</mi><mo>×</mo><mi>m</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d imes m}}</annotation></semantics></math><img src=$ ${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m <semantics><mrow><mstyle><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>:=</mo><mo>(</mo><msub><mi>z</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>z</mi><mrow><mi>m</mi></mrow></msub><mo>)</mo><mo>∈</mo><msup><mi>R</mi><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}</annotation></semantics></math><img src=$

${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta <semantics><mrow><mstyle><mn>0</mn><mo><</mo><mo>‖</mo><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>‖</mo><mo>≤</mo><mi>β</mi></mstyle></mrow><annotation>{\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }</annotation></semantics></math><img src=$
${\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}^{d <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mrow><mover><mi>a</mi><mo>→</mo></mover></mrow></mrow></msub><mo>(</mo><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>)</mo><mo>:=</mo><msup><mrow><mrow><mover><mi>a</mi><mo>→</mo></mover></mrow></mrow><mrow><mi>T</mi></mrow></msup><mo>.</mo><mrow><mrow><mover><mi>z</mi><mo>→</mo></mover></mrow></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><mo>.</mo><msub><mi>z</mi><mrow><mi>i</mi></mrow></msub><mo>=</mo><mn>0</mn><mo>∈</mo><msubsup><mi>R</mi><mrow><mi>q</mi></mrow><mrow><mi>d</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}^{d}}</annotation></semantics></math><img src=$

Bien que M-SIS soit une variante moins compacte de SIS que R-SIS, le problème M-SIS est asymptotiquement au moins aussi difficile que R-SIS et fournit donc une borne plus précise sur l'hypothèse de difficulté de SIS. Cela rend l'hypothèse de difficulté de M-SIS plus sûre, mais moins efficace, que celle de R-SIS.

Réseaux

réseau idéal

Réseaux cycliques

réseaux idéaux

Problème de solution entière courte

SIS q , n , m , β

R-SIS q , n , m , β

M-SIS q , n , d , m , β

SIS _{q , n , m , β}

R-SIS _{q , n , m , β}

M-SIS _{q , n , d , m , β}