短整数解問題

短整数解 (SIS) 問題とリング SIS問題は、格子ベースの暗号構築で使用される 2 つの平均ケース問題です。格子ベースの暗号は、SIS 問題に基づく一方向関数のファミリーを発表したMiklós Ajtai ^[1]による独創的な研究から 1996 年に始まりました。彼は、最短ベクトル問題(ある定数 に対して) が最悪のシナリオで困難である 場合、平均ケースでは安全であることを示しました。 ${\displaystyle \mathrm {SVP} _{\gamma }}$${\displaystyle \gamma =n^{c}}$${\displaystyle c>0}$

平均ケースの問題は、ランダムに選択されたいくつかのインスタンスに対して解決が困難な問題です。暗号化アプリケーションの場合、最悪のケースの複雑さだけでは不十分であり、平均ケースの複雑さに基づいて暗号化の構築が困難であることを保証する必要があります。

フルランク格子は 、基底と呼ばれる線形独立ベクトルの整数線形結合の集合です。 ${\displaystyle {\mathfrak {L}}\subset \mathbb {R} ^{n}}$${\displaystyle n}$${\displaystyle \{b_{1},\ldots ,b_{n}\}}$

${\displaystyle {\mathfrak {L}}(b_{1},\ldots ,b_{n})=\left\{\sum _{i=1}^{n}z_{i}b_{i}:z_{i}\in \mathbb {Z} \right\}=\{B{\boldsymbol {z}}:{\boldsymbol {z}}\in \mathbb {Z} ^{n}\}}$

ここで、は列に基底ベクトルを持つ行列です。 ${\displaystyle B\in \mathbb {R} ^{n\times n}}$

注意:格子 の 2 つの基底が与えられた場合、となるユニモジュラ行列が存在します。 ${\displaystyle B_{1},B_{2}}$${\displaystyle {\mathfrak {L}}}$${\displaystyle U_{1}}$${\displaystyle B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1}}$

定義:上の回転シフト演算子はで表され、次のように定義されます。 ${\displaystyle \mathbb {R} ^{n}(n\geq 2)}$${\displaystyle \operatorname {rot} }$

${\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})}$

ミチアンチョは、コンパクトナップサック問題を任意の環に一般化する研究の中で巡回格子を導入した。 ^[2]巡回格子は、回転シフト演算子の下で閉じた格子である。正式には、巡回格子は次のように定義される。

定義:格子が巡回的であるとは、次の場合です。 ${\displaystyle {\mathfrak {L}}\subseteq \mathbb {Z} ^{n}}$${\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}}$

例: ^[3]

1. ${\displaystyle \mathbb {Z} ^{n}}$それ自体は巡回格子です。
2. 商多項式環の任意のイデアルに対応する格子は巡回的である。${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$

商多項式環 を考え、 を内の何らかの多項式、つまりに対してとします。 ${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$${\displaystyle p(x)}$${\displaystyle R}$${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}}$${\displaystyle a_{i}\in \mathbb {Z} }$${\displaystyle i=0,\ldots ,n-1}$

埋め込み係数- モジュール同型を次のように定義します。 ${\displaystyle \mathbb {Z} }$${\displaystyle \rho}$

${\displaystyle {\begin{aligned}\quad \rho :R&\rightarrow \mathbb {Z} ^{n}\\[4pt]p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned}}}$

をイデアルとする。イデアル に対応する格子はの部分格子であり、次のように定義される。 ${\displaystyle I\subset R}$${\displaystyle I\subset R}$${\displaystyle {\mathfrak {L}}_{I}}$${\displaystyle \mathbb {Z} ^{n}}$

${\displaystyle {\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.}$

定理: が巡回的である場合、かつその場合のみ、商多項式環 内の何らかのイデアルに対応する。 ${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}$${\displaystyle {\mathfrak {L}}}$${\displaystyle I}$${\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}$

証明: 次のものがあります: ${\displaystyle \Leftarrow )}$

${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}}$

を の任意の要素とします。次に、 を定義します。しかし、 はイデアルなので、 が成り立ちます。このとき、です。しかし、 です。したがって、は巡回的です。 ${\displaystyle (a_{0},\ldots ,a_{n-1})}$${\displaystyle {\mathfrak {L}}}$${\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I}$${\displaystyle I}$${\displaystyle xp(x)\in I}$${\displaystyle \rho (xp(x))\in {\mathfrak {L}}_{I}}$${\displaystyle \rho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I}}$${\displaystyle {\mathfrak {L}}}$

${\displaystyle \Rightarrow )}$

を巡回格子とします。したがって。 ${\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}}$${\displaystyle \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}}$

多項式の集合を定義します。 ${\displaystyle I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}\right\}}$

1. は格子であり、したがって の加法部分群であるため、は の加法部分群です。${\displaystyle {\mathfrak {L}}}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle I\subset R}$${\displaystyle R}$
2. は巡回的であるため、.${\displaystyle {\mathfrak {L}}}$${\displaystyle \forall p(x)\in I:xp(x)\in I}$

したがって、は理想であり、結果として、 です。 ${\displaystyle I\subset R}$${\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}}$

を次数 の単項多項式とします。暗号化アプリケーションでは、は通常、既約になるように選択されます。 によって生成されるイデアルは次のようになります。 ${\displaystyle f(x)\in \mathbb {Z} [x]}$${\displaystyle n}$${\displaystyle f(x)}$${\displaystyle f(x)}$

${\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}.}$

商多項式環は、最大次数の多項式の同値類に分割されます。 ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$${\displaystyle \mathbb {Z} [x]}$${\displaystyle n-1}$

${\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} \right\}}$

ここで、加算と乗算は を法として簡約されます。 ${\displaystyle f(x)}$

埋め込み係数- モジュール同型を考えます。すると、 の各イデアルは、イデアル格子と呼ばれるのサブ格子を定義します。 ${\displaystyle \mathbb {Z} }$${\displaystyle \rho }$${\displaystyle R}$${\displaystyle \mathbb {Z} ^{n}}$

定義: イデアル に対応する格子 は、イデアル格子と呼ばれます。より正確には、商多項式環 を考えます。ここで、 は次数多項式によって生成されるイデアルです。 は の部分格子であり、次のように定義されます。 ${\displaystyle {\mathfrak {L}}_{I}}$${\displaystyle I}$${\displaystyle R=\mathbb {Z} [x]/(p(x))}$${\displaystyle (p(x))}$${\displaystyle n}$${\displaystyle p(x)\in \mathbb {Z} [x]}$${\displaystyle {\mathfrak {L}}_{I}}$${\displaystyle \mathbb {Z} ^{n}}$

${\displaystyle {\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.}$

備考: ^[5]

1. 理想格子では、が小さくても通常は容易であることがわかります。直感的には、代数的対称性により、理想の最小距離は狭く簡単に計算できる範囲内に収まると考えられます。${\displaystyle {\text{GapSVP}}_{\gamma }}$${\displaystyle \gamma =\operatorname {poly(n)} }$
2. 理想格子で提供される代数的対称性を利用することで、短い非ゼロベクトルを（ほぼ）同じ長さの線形独立ベクトルに変換することができます。したがって、理想格子では、およびは小さな損失で同等です。^[6]さらに、量子アルゴリズムの場合でも、およびは最悪のシナリオでは非常に困難であると考えられています。${\displaystyle n}$${\displaystyle \mathrm {SVP} _{\gamma }}$${\displaystyle \mathrm {SIVP} _{\gamma }}$${\displaystyle \mathrm {SVP} _{\gamma }}$${\displaystyle \mathrm {SIVP} _{\gamma }}$

短整数解 (SIS) 問題は、格子ベースの暗号構築で使用される平均ケース問題です。格子ベースの暗号は、1996 年に Ajtai ^[1]による独創的な研究から始まりました。Ajtai は、SIS 問題に基づく一方向関数のファミリーを発表しました。彼は、最悪のシナリオで(ある定数) が困難である場合、平均ケースでは安全であることを示しました。SIS 問題とその変種は、古典的な暗号への応用とともに、CRYSTALS-DilithiumやFalconなどのいくつかの量子耐性セキュリティ スキームで利用されています。^{[7] [8]}${\displaystyle \mathrm {SVP} _{\gamma }}$${\displaystyle \gamma =n^{c}}$${\displaystyle c>0}$

を、一様ランダムベクトルで構成される の要素を持つ行列とします。あるノルム に対して となる非ゼロベクトルを探します。 ${\displaystyle A\in \mathbb {Z} _{q}^{n\times m}}$${\displaystyle n\times m}$${\displaystyle \mathbb {Z} _{q}}$${\displaystyle m}$${\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}}$${\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]}$${\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m}}$${\displaystyle \|\cdot \|}$

• ${\displaystyle 0<\|{\boldsymbol {x}}\|\leq \beta }$、
• ${\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}}$。

解の長さ ( ) に関する必要な制約のない SIS の解は、ガウス消去法を使用して簡単に計算できます。 も必要です。そうでない場合は、は自明な解です。 ${\displaystyle \|{\boldsymbol {x}}\|\leq \beta }$${\displaystyle \beta <q}$${\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}}$

簡単ではない短い解決策 を保証するには、次のものが必要です。${\displaystyle f_{A}({\boldsymbol {x}})}$

• ${\displaystyle \beta \geq {\sqrt {n\log q}}}$、 そして
• ${\displaystyle m\geq n\log q}$

定理:任意の、任意の 、および十分に大きい任意の(任意の定数 に対して)について、無視できない確率で解くことは、最悪のシナリオで高い確率で およびを解くことと同じくらい困難です。${\displaystyle m=\operatorname {poly} (n)}$${\displaystyle \beta >0}$${\displaystyle q\geq \beta n^{c}}$${\displaystyle c>0}$${\displaystyle \operatorname {SIS} _{n,m,q,\beta }}$${\displaystyle \operatorname {GapSVP} _{\gamma }}$${\displaystyle \operatorname {SIVP} _{\gamma }}$${\displaystyle \gamma =\beta \cdot O({\sqrt {n}})}$

理想環上で解かれるSIS問題は、Ring-SIS問題またはR-SIS問題とも呼ばれます。^{[2] [9]}この問題は、ある整数に対して、あるノルムを持つ商多項式環を考慮します。特に興味深いのは、 となる整数が存在し、これが商を円分多項式に制限する場合です。^[10]${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}$${\displaystyle f(x)=x^{n}-1}$${\displaystyle n}$${\displaystyle \|\cdot \|}$${\displaystyle k}$${\displaystyle n=2^{k}}$

次に問題を次のように定義します。

独立した一様ランダム要素を選択します。ベクトルを定義します。次の条件を満たす非ゼロベクトルを見つけます。 ${\displaystyle m}$${\displaystyle a_{i}\in R_{q}}$${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}}$${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}$

• ${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }$、
• ${\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}}$。

SIS 問題の解の存在を保証するには、 が必要であることを思い出してください。ただし、リング SIS 問題はより簡潔で効率的です。リング SIS 問題の解の存在を保証するには、 が必要です。 ${\displaystyle m\approx n\log q}$${\displaystyle m\approx \log q}$

定義:の負循環行列は次のように定義されます。 ${\displaystyle b}$

${\displaystyle {\text{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}}}$

商多項式環が のとき、環の乗算は、まず の負巡回行列を形成し、次に の埋め込み係数ベクトル（または、代わりに正準係数ベクトル ） を乗算することによって効率的に計算できます。${\displaystyle R=\mathbb {Z} [x]/(x^{n}+1)}$${\displaystyle n=2^{k}}$${\displaystyle a_{i}.p_{i}}$${\displaystyle \operatorname {rot} (a_{i})}$${\displaystyle a_{i}}$${\displaystyle \operatorname {rot} (a_{i})}$${\displaystyle \rho (p_{i}(x))\in Z^{n}}$${\displaystyle p_{i}}$${\displaystyle \sigma (p_{i}(x))\in Z^{n}}$

さらに、R-SIS問題はSIS問題の特殊なケースであり、 SIS問題における行列は負の巡回ブロックに制限される。^[10]${\displaystyle A}$${\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]}$

モジュール格子上で解かれる SIS 問題は、モジュール SIS 問題または M-SIS 問題とも呼ばれます。R-SIS と同様に、この問題では、 が 2 の累乗である場合に特に注目して、 の商多項式環と を考慮します。次に、がとなるランクのモジュールとし、 が上の任意のノルムとします。 ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$${\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}$${\displaystyle f(x)=x^{n}-1}$${\displaystyle n}$${\displaystyle M}$${\displaystyle d}$${\displaystyle M\subseteq R^{d}}$${\displaystyle \|\cdot \|}$${\displaystyle R_{q}^{m}}$

次に問題を次のように定義します。

独立した一様ランダム要素を選択します。ベクトルを定義します。次の条件を満たす非ゼロベクトルを見つけます。 ${\displaystyle m}$${\displaystyle a_{i}\in R_{q}^{d}}$${\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d\times m}}$${\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}$

• ${\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta }$、
• ${\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}}$。

M-SISはR-SISほどコンパクトではないが、M-SISの問題は漸近的には少なくともR-SISと同じくらい困難であり、したがってSISの困難性仮定に対してより厳しい境界を与える。これにより、M-SISの困難性を仮定することは、R-SISと比較するとより安全ではあるが、効率の悪い基礎となる仮定となる。^[10]

• 格子ベースの暗号
• 準同型暗号
• エラーのあるリング学習と鍵交換
• 耐量子暗号
• 格子問題