Computational problem used in cryptography
短整数解（SIS） 問題と 環SIS問題は、 格子ベース暗号の 構築において用いられる 2つの 平均ケース問題です。格子ベース暗号は、1996年に ミクローシュ・アジタイ [1] による独創的な研究から始まりました。 彼はSIS問題に基づく一方向性関数の族を提示しました。彼は、 最短ベクトル問題 （ ある定数 に対して ）が最悪のケースで困難であれば、平均ケースでは安全であることを示しました。 S V P γ {\displaystyle \mathrm {SVP} _{\gamma }} γ = n c {\displaystyle \gamma =n^{c}} c > 0 {\displaystyle c>0}
平均ケース問題とは、ランダムに選択されたいくつかのインスタンスに対して解くのが困難な問題です。暗号アプリケーションにおいては、最悪ケースの複雑さだけでは不十分であり、平均ケースの複雑さに基づいて暗号構築が困難であることを保証する必要があります。
格子 フル ランク 格子 は、基底 と呼ばれる 線形独立ベクトル の整数線形結合の集合です 。 L ⊂ R n {\displaystyle {\mathfrak {L}}\subset \mathbb {R} ^{n}} n {\displaystyle n} { b 1 , … , b n } {\displaystyle \{b_{1},\ldots ,b_{n}\}}
L ( b 1 , … , b n ) = { ∑ i = 1 n z i b i : z i ∈ Z } = { B z : z ∈ Z 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}\}} ここで 、は列に基底ベクトルを持つ行列です。 B ∈ R n × n {\displaystyle B\in \mathbb {R} ^{n\times n}}
注意: 格子 の 2 つの基底 が与えられている場合、 となる ユニモジュラ行列が存在します 。 B 1 , B 2 {\displaystyle B_{1},B_{2}} L {\displaystyle {\mathfrak {L}}} U 1 {\displaystyle U_{1}} B 1 = B 2 U 1 − 1 , B 2 = B 1 U 1 {\displaystyle B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1}}
理想的な格子 定義: 上の回転シフト演算子 は で表され 、次のように定義されます。 R n ( n ≥ 2 ) {\displaystyle \mathbb {R} ^{n}(n\geq 2)} rot {\displaystyle \operatorname {rot} }
∀ x = ( x 1 , … , x n − 1 , x n ) ∈ R n : rot ( x 1 , … , x n − 1 , x n ) = ( x n , x 1 , … , x n − 1 ) {\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] 巡回格子とは、回転シフト作用素に関して閉じた格子である。正式には、巡回格子は以下のように定義される。
定義: 格子 が巡回的である場合 。 L ⊆ Z n {\displaystyle {\mathfrak {L}}\subseteq \mathbb {Z} ^{n}} ∀ x ∈ L : rot ( x ) ∈ L {\displaystyle \forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}}
例: [3]
Z n {\displaystyle \mathbb {Z} ^{n}} それ自体は巡回格子である。 商多項式環の任意のイデアルに対応する格子は 巡回的である。 R = Z [ x ] / ( x n − 1 ) {\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)} 商多項式環 を考え 、 を 内の何らかの多項式 、 すなわち に対してとします 。 R = Z [ x ] / ( x n − 1 ) {\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)} p ( x ) {\displaystyle p(x)} R {\displaystyle R} p ( x ) = ∑ i = 0 n − 1 a i x i {\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}} a i ∈ Z {\displaystyle a_{i}\in \mathbb {Z} } i = 0 , … , n − 1 {\displaystyle i=0,\ldots ,n-1}
埋め込み係数 - モジュール同型を 次のように定義します。 Z {\displaystyle \mathbb {Z} } ρ {\displaystyle \rho }
ρ : R → Z n p ( x ) = ∑ i = 0 n − 1 a i x i ↦ ( a 0 , … , a n − 1 ) {\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}}} をイデアルとする 。イデアル に対応する格子 は の部分格子であり 、次のように定義される。 I ⊂ R {\displaystyle I\subset R} I ⊂ R {\displaystyle I\subset R} L I {\displaystyle {\mathfrak {L}}_{I}} Z n {\displaystyle \mathbb {Z} ^{n}}
L I := ρ ( I ) = { ( a 0 , … , a n − 1 ) ∣ ∑ i = 0 n − 1 a i x i ∈ I } ⊂ 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}.} 定理: が巡回的である場合、かつその場合のみ、 商多項式環 内の 何らかのイデアルに対応する 。 L ⊂ Z n {\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}} L {\displaystyle {\mathfrak {L}}} I {\displaystyle I} R = Z [ x ] / ( x n − 1 ) {\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}
証明: 以下があります: ⇐ ) {\displaystyle \Leftarrow )}
L = L I := ρ ( I ) = { ( a 0 , … , a n − 1 ) ∣ ∑ i = 0 n − 1 a i x i ∈ I } {\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\}} を の任意の元とします 。 次に、 を定義します 。しかし、 はイデアルなので、 が成り立ちます 。そして、 です 。しかし、 です。したがって、 は巡回的です。 ( a 0 , … , a n − 1 ) {\displaystyle (a_{0},\ldots ,a_{n-1})} L {\displaystyle {\mathfrak {L}}} p ( x ) = ∑ i = 0 n − 1 a i x i ∈ I {\displaystyle p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I} I {\displaystyle I} x p ( x ) ∈ I {\displaystyle xp(x)\in I} ρ ( x p ( x ) ) ∈ L I {\displaystyle \rho (xp(x))\in {\mathfrak {L}}_{I}} ρ ( x p ( x ) ) = rot ( a 0 , … , a n − 1 ) ∈ L I {\displaystyle \rho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I}} L {\displaystyle {\mathfrak {L}}}
⇒ ) {\displaystyle \Rightarrow )}
を巡回格子とします。 したがって 。 L ⊂ Z n {\displaystyle {\mathfrak {L}}\subset \mathbb {Z} ^{n}} ∀ ( a 0 , … , a n − 1 ) ∈ L : rot ( a 0 , … , a n − 1 ) ∈ L {\displaystyle \forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}}
多項式の集合を定義する ： I := { ∑ i = 0 n − 1 a i x i ∣ ( a 0 , … , a n − 1 ) ∈ L } {\displaystyle I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}\right\}}
は格子であり、したがって の加法部分群である ため 、 は の加法部分群です 。 L {\displaystyle {\mathfrak {L}}} Z n {\displaystyle \mathbb {Z} ^{n}} I ⊂ R {\displaystyle I\subset R} R {\displaystyle R} は巡回的である ため、 . L {\displaystyle {\mathfrak {L}}} ∀ p ( x ) ∈ I : x p ( x ) ∈ I {\displaystyle \forall p(x)\in I:xp(x)\in I} したがって、 は理想であり、結果として、 です 。 I ⊂ R {\displaystyle I\subset R} L = L I {\displaystyle {\mathfrak {L}}={\mathfrak {L}}_{I}}
理想的な格子 出典: [4]
を次数 の 単項多項式 とする 。 暗号アプリケーションでは、 は通常、既約となるように選択される。 によって生成されるイデアルは 以下である。 f ( x ) ∈ Z [ x ] {\displaystyle f(x)\in \mathbb {Z} [x]} n {\displaystyle n} f ( x ) {\displaystyle f(x)} f ( x ) {\displaystyle f(x)}
( f ( x ) ) := f ( x ) ⋅ Z [ x ] = { f ( x ) g ( x ) : ∀ g ( x ) ∈ Z [ x ] } . {\displaystyle (f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}.} 商多項式環は、 最大次数の多項式の同値類に 分割されます 。 R = Z [ x ] / ( f ( x ) ) {\displaystyle R=\mathbb {Z} [x]/(f(x))} Z [ x ] {\displaystyle \mathbb {Z} [x]} n − 1 {\displaystyle n-1}
R = Z [ x ] / ( f ( x ) ) = { ∑ i = 0 n − 1 a i x i : a i ∈ Z } {\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} \right\}} ここで、加算と乗算は を法として約されます 。 f ( x ) {\displaystyle f(x)}
埋め込み係数 - 加群同型を考える 。すると、 の各イデアルは、 イデアル格子 と呼ばれる の部分格子を定義する 。 Z {\displaystyle \mathbb {Z} } ρ {\displaystyle \rho } R {\displaystyle R} Z n {\displaystyle \mathbb {Z} ^{n}}
定義： イデアル に対応する格子 は イデアル格子と呼ばれます。より正確には、商多項式環 を考えます。 ここでは次数 多項式 によって生成されるイデアルです 。 は の部分格子 であり 、次のように定義されます。 L I {\displaystyle {\mathfrak {L}}_{I}} I {\displaystyle I} R = Z [ x ] / ( p ( x ) ) {\displaystyle R=\mathbb {Z} [x]/(p(x))} ( p ( x ) ) {\displaystyle (p(x))} n {\displaystyle n} p ( x ) ∈ Z [ x ] {\displaystyle p(x)\in \mathbb {Z} [x]} L I {\displaystyle {\mathfrak {L}}_{I}} Z n {\displaystyle \mathbb {Z} ^{n}}
L I := ρ ( I ) = { ( a 0 , … , a n − 1 ) ∣ ∑ i = 0 n − 1 a i x i ∈ I } ⊂ 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]
イデアル格子上では、たとえ小さな値であっても、通常は容易に計算できること がわかります 。直感的には、代数対称性により、イデアルの最小距離は狭く、容易に計算できる範囲内に収まると考えられます。 GapSVP γ {\displaystyle {\text{GapSVP}}_{\gamma }} γ = p o l y ( n ) {\displaystyle \gamma =\operatorname {poly(n)} } 理想格子に備わっている代数的対称性を利用することで、短い非零ベクトルを （ほぼ）同じ長さの線形独立ベクトルに変換することができます。したがって、理想格子上では、、 およびは わずかな損失で同値です。 [6]さらに、 量子アルゴリズム においても 、、 およびは 最悪のシナリオでは非常に困難であると考えられています。 n {\displaystyle n} S V P γ {\displaystyle \mathrm {SVP} _{\gamma }} S I V P γ {\displaystyle \mathrm {SIVP} _{\gamma }} S V P γ {\displaystyle \mathrm {SVP} _{\gamma }} S I V P γ {\displaystyle \mathrm {SIVP} _{\gamma }}
短整数解問題 短整数解（SIS）問題は、格子暗号の構築に用いられる 平均 ケース問題である。格子暗号は、1996年にAjtai [1] による独創的な研究から始まった。彼はSIS問題に基づく一方向性関数の族を提示した。彼は、 （ ある定数に対して ）が最悪のシナリオで困難である場合、平均ケースではSIS問題が安全であることを示した。SIS問題とその変種は、古典暗号への応用に加え、 CRYSTALS-Dilithium や Falcon など、いくつかの量子耐性セキュリティ方式にも利用されている。 [7] [8] S V P γ {\displaystyle \mathrm {SVP} _{\gamma }} γ = n c {\displaystyle \gamma =n^{c}} c > 0 {\displaystyle c>0}
シス q 、 n 、 m 、 β を の要素とし、一様乱数ベクトル で構成される 行列 とします 。 ある ノルム に対して となる 非ゼロベクトルを求めます 。 A ∈ Z q n × m {\displaystyle A\in \mathbb {Z} _{q}^{n\times m}} n × m {\displaystyle n\times m} Z q {\displaystyle \mathbb {Z} _{q}} m {\displaystyle m} a i ∈ Z q n {\displaystyle {\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}} A = [ a 1 | ⋯ | a m ] {\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]} x ∈ Z m {\displaystyle {\boldsymbol {x}}\in \mathbb {Z} ^{m}} ‖ ⋅ ‖ {\displaystyle \|\cdot \|}
0 < ‖ x ‖ ≤ β {\displaystyle 0<\|{\boldsymbol {x}}\|\leq \beta } 、 f A ( x ) := A x = 0 ∈ Z q n {\displaystyle f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}} 。 SISの解は、解の長さ（ ）に関する必要な制約なしに、 ガウス消去 法 を用いて簡単に計算できます。また、 も必要です。 そうでなければ、 は自明な解です。 ‖ x ‖ ≤ β {\displaystyle \|{\boldsymbol {x}}\|\leq \beta } β < q {\displaystyle \beta <q} x = ( q , 0 , … , 0 ) ∈ Z m {\displaystyle {\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}}
非自明で短い解決策 を保証するには、次のものが必要です。 f A ( x ) {\displaystyle f_{A}({\boldsymbol {x}})}
β ≥ n log q {\displaystyle \beta \geq {\sqrt {n\log q}}} 、 そして m ≥ n log q {\displaystyle m\geq n\log q} 定理: 任意の、任意の 、および十分に大きい任意の (任意の定数 に対して ) について、無視できない確率で解くことは、 最悪のシナリオで高い確率で およびを解くことと 同じ くらい少なくとも困難です。 m = poly ( n ) {\displaystyle m=\operatorname {poly} (n)} β > 0 {\displaystyle \beta >0} q ≥ β n c {\displaystyle q\geq \beta n^{c}} c > 0 {\displaystyle c>0} SIS n , m , q , β {\displaystyle \operatorname {SIS} _{n,m,q,\beta }} GapSVP γ {\displaystyle \operatorname {GapSVP} _{\gamma }} SIVP γ {\displaystyle \operatorname {SIVP} _{\gamma }} γ = β ⋅ O ( n ) {\displaystyle \gamma =\beta \cdot O({\sqrt {n}})}
R-SIS q 、 n 、 m 、 β 理想環上で解かれるSIS問題は、Ring-SIS問題またはR-SIS問題とも呼ばれます。 [2] [9] この問題は、ある整数に対して の商多項式環 と あるノルム を持つ 商多項式環を考えます 。特に興味深いのは、 となる整数 が存在する場合で 、これが商を円分多項式に制限する場合です。 [10] R q = Z q [ x ] / ( f ( x ) ) {\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))} f ( x ) = x n − 1 {\displaystyle f(x)=x^{n}-1} n {\displaystyle n} ‖ ⋅ ‖ {\displaystyle \|\cdot \|} k {\displaystyle k} n = 2 k {\displaystyle n=2^{k}}
次に、問題を次のように定義します。
独立な一様ランダム要素 を選択する 。ベクトルを定義する。 次を満たす 非ゼロベクトルを求める。 m {\displaystyle m} a i ∈ R q {\displaystyle a_{i}\in R_{q}} a → := ( a 1 , … , a m ) ∈ R q m {\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}} z → := ( z 1 , … , z m ) ∈ R m {\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}
0 < ‖ z → ‖ ≤ β {\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta } 、 f a → ( z → ) := a → T . z → = ∑ i = 1 m a i . z i = 0 ∈ R q {\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問題の解の存在を保証するには が必要です 。 m ≈ n log q {\displaystyle m\approx n\log q} m ≈ log q {\displaystyle m\approx \log q}
定義: の 負循環行列は 次 のように定義されます。 b {\displaystyle b}
for b = ∑ i = 0 n − 1 b i x i ∈ R , rot ( b ) := [ b 0 − b n − 1 … − b 1 b 1 b 0 … − b 2 ⋮ ⋮ ⋱ ⋮ b n − 1 b n − 2 … b 0 ] {\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}}} 商多項式環が のとき 、環の乗算は 、まず の負循環行列を形成し 、次に の 埋め込み係数ベクトル （または、 標準係数ベクトル ） を乗算する ことによって効率的に計算できます。 R = Z [ x ] / ( x n + 1 ) {\displaystyle R=\mathbb {Z} [x]/(x^{n}+1)} n = 2 k {\displaystyle n=2^{k}} a i . p i {\displaystyle a_{i}.p_{i}} rot ( a i ) {\displaystyle \operatorname {rot} (a_{i})} a i {\displaystyle a_{i}} rot ( a i ) {\displaystyle \operatorname {rot} (a_{i})} ρ ( p i ( x ) ) ∈ Z n {\displaystyle \rho (p_{i}(x))\in Z^{n}} p i {\displaystyle p_{i}} σ ( p i ( x ) ) ∈ Z n {\displaystyle \sigma (p_{i}(x))\in Z^{n}}
さらに、R-SIS問題はSIS問題の特殊なケースであり、SIS問題における 行列は負の巡回ブロックに制限される 。 [10] A {\displaystyle A} A = [ rot ( a 1 ) | ⋯ | rot ( a m ) ] {\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]}
M-SIS q 、 n 、 d 、 m 、 β モジュール格子上で解かれるSIS問題は、モジュールSIS問題またはM-SIS問題とも呼ばれます。R-SIS問題と同様に、この問題は、が2のべき乗 である場合に特に注目して、 の 商多項式環 とを考えます。 次に、 が 階数のモジュールであって となるものとし 、 が 上の任意のノルムであるとします 。 R = Z [ x ] / ( f ( x ) ) {\displaystyle R=\mathbb {Z} [x]/(f(x))} R q = Z q [ x ] / ( f ( x ) ) {\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))} f ( x ) = x n − 1 {\displaystyle f(x)=x^{n}-1} n {\displaystyle n} M {\displaystyle M} d {\displaystyle d} M ⊆ R d {\displaystyle M\subseteq R^{d}} ‖ ⋅ ‖ {\displaystyle \|\cdot \|} R q m {\displaystyle R_{q}^{m}}
次に、問題を次のように定義します。
独立な一様ランダム要素 を選択する 。ベクトルを定義する。 次を満たす 非ゼロベクトルを求める。 m {\displaystyle m} a i ∈ R q d {\displaystyle a_{i}\in R_{q}^{d}} a → := ( a 1 , … , a m ) ∈ R q d × m {\displaystyle {\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d\times m}} z → := ( z 1 , … , z m ) ∈ R m {\displaystyle {\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}}
0 < ‖ z → ‖ ≤ β {\displaystyle 0<\|{\vec {\boldsymbol {z}}}\|\leq \beta } 、 f a → ( z → ) := a → T . z → = ∑ i = 1 m a i . z i = 0 ∈ R q d {\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]
参照
参考文献 ^ ab Ajtai, Miklós. [格子問題の困難なインスタンス生成] 第28回ACMコンピューティング理論シンポジウム議事録. ACM, 1996. ^ ab Micciancio, Daniele. [一般化されたコンパクトナップサック、巡回格子、そして最悪ケースの計算量仮定に基づく効率的な一方向性関数。] Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on. IEEE, 2002. ^ Fukshansky, Lenny, Xun Sun. [巡回格子の幾何学について] Discrete & Computational Geometry 52.2 (2014): 240–259. ^ Craig Gentry. 理想格子を用いた完全準同型暗号化. 第41回ACMコンピューティング理論シンポジウム（STOC） , 2009年. ^ ペイカート、クリス。[格子暗号の10年] Cryptology ePrint Archive、レポート2015/939、2015年。 ^ Peikert, Chris, and Alon Rosen. [巡回格子における最悪ケース仮定に基づく効率的な衝突耐性ハッシュ法] 暗号理論. Springer Berlin Heidelberg, 2006. 145–166. ^ 白、史;デュカス、レオ。キルツ、アイク。ルポイント、タンクレード。リュバシェフスキー、ヴァディム。シュワーベ、ピーター。ザイラー、グレゴ4;ダミアン・シュテーレ（2020年10月1日）。 「CRYSTALS-Dilithium:アルゴリズム仕様とサポートドキュメント」 (PDF) 。 PQ-Crystals.org 。 2023 年 11 月 13 日 に取得 。 {{cite web }}: CS1 maint: numeric names: authors list (link )^ Fouque, Pierre-Alain; Hoffstein, Jeffrey; Kirchner, Paul; Lyubashevsky, Vadim; Pornin, Thomas; Prest, Thomas; Ricosset, Thomas; Seiler, Gregor; Whyte, William; Zhang, Zhenfei (2020年10月1日). 「Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU」 . 2023年 11月13日 閲覧 。 ^ Lyubashevsky, Vadim, et al. [SWIFFT: FFTハッシュのための控えめな提案。] 高速ソフトウェア暗号化。Springer Berlin Heidelberg、2008年。 ^ abc Langlois, Adeline, Damien Stehlé. [モジュール格子の最悪ケースから平均ケースへの縮約] Designs, Codes and Cryptography 75.3 (2015): 565–599.
![{\displaystyle R=\mathbb {Z} [x]/(x^{n}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5dbcc85b76943545f4c60ded35b5748d9baaa65)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b19ef05928355e61a925130e56f50ce32cae8b4)
![{\displaystyle f(x)\in \mathbb {Z} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb8266c32dfc2904dc4331ea8906ad341a05ce1c)
![{\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)
![{\displaystyle R=\mathbb {Z} [x]/(f(x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cff04a320199577d049d268772b9ff80b3f7919)
![{\displaystyle \mathbb {Z} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d4da3ac703cc7721ebba91a53f6752de7157124)
![{\displaystyle R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} \right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a93ba3d1d81e47803821bcde400820a3f39cef90)
![{\displaystyle R=\mathbb {Z} [x]/(p(x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0cbb1fc048ee6ee33cc951fdd57a63a5b61771a)
![{\displaystyle p(x)\in \mathbb {Z} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6eb44fd7ae38db591820a0c9c939c1a7f3d0038a)
![{\displaystyle A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb0b879ee77261eca27b6d7f024c6a6bdd31a8f3)
![{\displaystyle R_{q}=\mathbb {Z} _{q}[x]/(f(x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e2c371303cca07ba0ab4699422357da1f051d66)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a9663affde7dc867475147d16af19f77f691c05)
![{\displaystyle R=\mathbb {Z} [x]/(x^{n}+1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cf3edc35924ffa32d7bede76021d86741f78638)
![{\displaystyle A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/485989a638e349ec007ea9e2e0c3ddd8f2293061)
