RLWE_LPR10 - toyofuku/flp GitHub Wiki

https://eprint.iacr.org/2012/230.pdf

代数的数論は代数体の研究である。このセクションでは、必要な理論的背景を円分体を実例に取り上げ、数学と計算理論をみていく。円分体の特別な性質を2.4にまとめる。

代数体は、有理数体に抽象要素 ζ を添加した体の拡大 K = Q(ζ) として定義することができる。この ζ は、ある既約多項式 f(x) ∈ Q[x] で関係 f(ζ) = 0 を満足する。この多項式fは一般性を失うことなくモニックにできる。この多項式 f は ζ の最小多項式と呼ばれる。代数体の次数 n は f の次数である。 f(ζ) = 0 から、代数体 K は {1,ζ,...,ζ^(n-1)} を基底とする Q 上の n次元ベクトル空間とみなせる。これはKの"power basis"と呼ばれる。もちろん、ζ を不定元 x に関連づけると、K と Q[x]/f(x)の間の自然な同型写像がもたらされる。

注）モニック: 最高次係数が1の1変数多項式。

m を正の整数、ζ = ζ_m を位数 m の要素、すなわち1の原始n乗根とする。m次の円分体は K = Q(ζ) であり、ζ の最小多項式は次の m次円分多項式である。

Φ_m(x) = prod(x - ω^i_m) ∈ Z[x] for i in Z*_m

ここで ω_m ∈ C は1の原始m乗根となる複素数、つまり ω_m = exp(2*π*sqrt(-1)/m)である。Φ_m(x)の複素数根 ω^i_m は　C（複素数）における1の原始m乗根であり、Φ_m(x) の次数は n=φ(m) である(φはオイラーのφ関数)。この論文では、 (単項で)与えられたmに対してΦ_m(x) が多項式時間で計算される点を除けば、役割があるわけではない。

代数体の埋め込みについて説明する。埋め込みは代数体上の自然な(canonical)幾何学を誘導する。

次数nの代数体 K = Q(ζ) はn個の環埋め込み(単射な環準同型) σ_i: K -> C をもつ。これらの埋め込みは ζ をその最小多項式 f の複素数根に対応づける。f(σ_i(ζ)) = σ_i(f(ζ)) = 0 なので、KからCへの環埋め込みが一意であることは自明。像がRにある埋め込みは実埋め込みと呼ばれる(fの実根に対応)。fの複素数根は複素埋め込みと呼ばれる。f(x)の複素根は共役をもつので、複素埋め込みも同様である。実埋め込みの数をs1とし、複素埋め込みの組の数をs2とすると、n = s1 + 2 * s2 が成り立つ。実埋め込みを{σ_j} for j ∈ [s1]で記す。

σ_{s1+s2+j} = conjugate(σ_{s1+j}) for j ∈ [s2]

となるように複素埋め込みを整列する。標準埋め込み(canonical embedding) σ: K -> R^{s1} × C^{2*s2}は次のように定義される。

σ(x) = (σ_1(x),...,σ_n(x))

これは環準同型であり、乗法と加法はどちらも要素ごとに行われる。複素埋め込みは共役をもつので、σ は H への写像になる。

Kの要素をHへの標準埋め込みで識別すれば、これはK上の幾何学ノルム（ユークリッドノルムなど）と呼べる。H上のノルムをC^nからの誘導で定義したので、任意の x ∈ K と任意の p ∈ [1,∞] に対して、xのl_pノルムはp < ∞に対して

||x||_p = ||σ(x)||_p = ( Σ |σ_i(x)|^p for i ∈ [n] )^{1/p}

であり、l_∞ は max |σ_i(x)| for i ∈ [n] である。pが省略された場合は l_2 ノルムとする。埋め込まれた要素の乗法は（σは環準同型であるから）要素ごとに行われるので、任意の x,y ∈ Kと任意の p ∈ [1,∞]に対して

||x * y||_p <= ||x||_∞ * ||y||_p

が得られる。l_∞ ノルムはKの絶対値に相当し、乗法によって他の要素をどれだけ「拡大」するかを示す。

標準埋め込みを使えば、H上の r ∈ (R^+)^n のガウス分布 D_r 、あるいはHの格子における離散ガウス分布は、K上の分布と見なすことができる。厳密には分布 D_r はK上の分布ではなく、むしろ体上のテンソル積K_R = K ⊗_Q R上の分布であり、これはHと同型である。任意の要素 x ∈ K_R に対して x * D_r の分布はD_r'である。ここで r'_i = r_i * |σ_i(x)|とする（この分布は複素埋め込みの実部と虚部に同じ分散をもつことを使っている）。

抽象的には、x ∈ Kの（体の）トレースTr = Tr_{K/Q}: K -> Qと（体の）ノルムN = N_{K/Q}: K -> Qは、それぞれK（をQ上のベクトル空間とみなしたとき）の線型変換のトレースと行列式であり、xによる乗法を表現する。具体的には、トレースとノルムはそれぞれ埋め込みの総和と総乗で示すことができる。

Tr(x) = Σ σ_i(x) for i ∈　[n]
N(x)  = Π σ_i(x) for i ∈　[n]

どちらの定義を使っても、トレースとノルムはそれぞれ加法と乗法であることは容易に確認できる。 さらに、すべてのx, y ∈ Kに対して

Tr(x*y) = Σ σ_i(x)*σ_i(y) = <σ(x),conjugate(σ(y))> for i ∈ [n]

である。つまりTr(x*y)は、xとyの埋め込みの内積と類似した対称な双線型形式(bilinear form)をもつ。

sage: from sage.rings.polynomial.cyclotomic import cyclotomic_coeffs
sage: cyclotomic_polynomial(5)
x^4 + x^3 + x^2 + x + 1
sage: cyclotomic_value(5, 1/2)
31/16

代数的整数とは、有理数上の最小多項式が整数係数となる要素である。代数体Kに対してKの代数的整数の集合をO_k ⊂ Kと記す。この集合は（Kにおける加法と乗法の下で）代数体の整数環と呼ばれる環をつくる。代数的整数のノルムとトレースは、それ自体が有理整数である（つまりZに属す)。

O_Kはランクn（これはKの次数）である自由Zモジュラになる。つまり、ある基底B = {b1,...,bn} ⊂ O_KでのすべてのZ線型結合の集合である。このような集合は整数底と呼ばれ、KのQ基底（でありK_RのR基底）である。通常こうした基底はn>1のとき無限に存在する。

次数n=φ(m)のm番目の円分体K=Q(ζ_m)の例を続けると、Kの"power basis" {1,ζ_m,...ζ_n^(n-1)}もO_K=Z[ζ_m]であり、整数基底となる（一般に、代数体のpower basisが整数の環全体を生成することは珍しい）。

(整)イデアル I ⊆ O_K は自明でない加法部分群（つまりI ≠ φかつI ≠ {0}である）であり、Q_Kでの乗法において閉じている。つまり任意のr ∈ O_Kとx ∈ I^2に対してr*x ∈ Iである。O_KにおけるイデアルIは、g1,g2,... ∈ O_Kの線形結合の集合として有限生成される。これをI=<g1,g2,...>と記す。（実際には、常に2つの生成子があれば十分であることが知られている）。イデアルはランクnの自由Zモジュラでもある。つまり、ある基底{u1,...,u_n} ⊂ Q_KのあらゆるZ線形結合の集合として生成される。

イデアルIのノルムは、O_Kの加法部分群となる添字である。つまりN(I) = |O_K/I|。2つのイデアルの和I+Jは、x∈I,y∈Jにおけるすべてのx+yの集合であり、2つのイデアルの積はx∈I,y∈Jにおける項xyのすべての有限和の集合である。イデアルのノルムという概念は、上で定義した体ノルムを一般化する。任意のx∈O_Kに対してN()=|N(x)|でありN(IJ)=N(I)N(J)である。

2つのイデアルI,J ⊆ O_Kは、I+J=O_Kのとき互いに素と呼ばれる。イデアルP ⊂ O_Kは、あるa,b ∈ O_Kに対してつねにab ∈ pならばa ∈ Pあるいはb ∈ Pが成り立つとき素イデアルである。O_Kにおいては、イデアルPが極大イデアルの場合にのみ素イデアルである。つまり、Pを包含するイデアルはO_K自体しかないことを意味する。これは商環O_K/Pが位数N(P)の有限体であることを含意する。環O_Kにはイデアルの一意分解がある。つまり、イデアルI ⊆ O_Kは素イデアルの冪乗の総積として一意に表現することができる。

分数イデアルI ⊂ Kは、dI ⊆ O_Kがd ∈ O_Kに対する整イデアルとなる集合である。そのノルムはN(I) = N(dI) / |N(d)|と定義される。小数イデアルの集合は乗法群を作り、そのノルムはこの群上の乗法的同型写像である。

Kにおける（小数）イデアルが標準埋め込みの下で格子をどのように作るかを説明し、その性質を記述する。分数イデアルIはZ基底としてU={u_1,...,u_n}を持つ。このため、標準埋め込みσの下でイデアルは、基底{σ(u_1),...,σ(u_n)} ⊂ Hをもつランクnのイデアル格子σ(I)を作る。簡略のため、しばしばイデアルとその埋め込み格子を区別しない。イデアルの最小距離λ_1(I)といった言い方をする。

代数体Kの判別式（の絶対値）△_Kは、σ(O_K)の基本体積の平方根として定義される。このためb_1,...,b_nがO_Kの整数基底であるとき△_K = |det(Tr(b_i * b_j))|と同値である。このためイデアル格子σ(I)の基本体積はN(I)*sqrt(△_K)である。たとえば、次数n=φ(m)となるm番目の円分体K=Q(ζ_m)の判別式は

△_K = m^n / prod(p^{n/(p-1)} for prime p|m) <= n^n

ここで判別式における総乗は、mを割り切るすべての素数について計算する。この不等式は、mが2の冪乗のとき、つまりn=m/2のとき、等号が成り立つ。

次の古典的補題は、イデアル格子の最小距離の上界と下界を与える。上界はミンコウスキーの第1定理から直接帰結する。下界は総加総乗平均の不等式に従い、任意の非ゼロx ∈ Iに対して|N(x)| >= N(I)である。

補題2.9 次数がnとなる代数体Kの任意の分数イデアルは、p ∈ [1,∞]の任意のl_pノルムに対して、

n^{1/p} * N(I)^{1/n} <= λ_1(I) <= n^{1/p} * N(I)^{1/n} * sqrt(△_K^{1/n})

双対イデアルの概念を使って、逆イデアルと双対イデアルの間の密接な関係を説明する。

Kにおける任意の格子Lに対して（つまり、Kの任意のQ基底のZスパンに対して）、格子の双対を次のように定義する。

L^∨ = {x ∈ K : Tr(xL) ⊆ Z}

標準埋め込みの下では、L^∨は双対格子の複素共役、すなわちσ(L^∨) = conjugate(σ(L)^*)になる。これはTr(xy) = Σ σ_i(x)σ_i(y) = <σ(x), conjugate(σ(y))>から得られる。また(L^∨)^∨ = Lは容易に確認できる。もしLが分数イデアルであれば、L^∨は1になる。

自明な代数体K = Qを除いて、整数環R = O_Kは自己双対ではなく、Rとイデアルは互いに逆双対でもない。幸い、イデアル(I)とその逆(I^-1)は、環の双対イデアル(R^∨)との乗法で次のように関係付けられる： 任意の分数イデアル I に対して、双対イデアルはI^∨ = I^-1 * R^∨である（I = RのときR^-1 = Rなのでこれは自明）。因子R^∨の逆(R^∨)^-1は微分イデアルと呼ばれる。微分イデアルの積分が分数イデアルR^∨であり、ノルムがN((R^∨)^-1) = △_Kである。分数イデアルR^∨自体は余微分(codifferent)と呼ばれる。m = 2^kのとき次数n = φ(m) = m/2となるm番目の円分体は特別であり、この場合にはR^∨ = <n^-1>はRのスケールにすぎない。

ここでKとO_Kの上のオブジェクトがどのように表現され、アルゴリズムによってどう演算されるのかを一般的なケースで説明する。代数体Kの文脈における計算複雑性の量については、nの多項式、log(△_K)、任意の入力の総ビット長の意味で「多項式オーダー」とみなされる。（我々が使う具体的な代数体の族において、log(△_K)はnの小さな多項式である）。

O_Kはランクnの自由Zモジュラなので、環O_Kはある積分基底B = {b_1,...,b_n} ⊂ O_Kを基準に表現される。これはKについてのQ基底でもある。すなわち、要素x ∈ Kはベクトルx = (x_1,...,x_n) ∈ Q^nによって一意に表現される。ここでx = Σ x_i * b_i for i ∈ [n]とするとx_i ∈ Zの場合のみx ∈ O_Kである。

K（およびO_K）での加法は、単純に表現ベクトルの要素ごとの加法である。K(およびO_K)での乗法は、線形性によりi,j ∈ [n]に対する積b_i * b_j ∈ O_Kであると知っていれば十分である。これらの項の（通常はBを基準にした）表現は、多項式サイズの積分ベクトルであり、KとO_Kの全体を構築する。この記述が与えられていれば、乗法の逆を多項式時間で計算可能である。

積分イデアルI ⊆ O_K は、Iに対するZ基底で表現される。これはI = Σ Z * u_i for i ∈ [n] としたときの U_I = {u_1,...,u_n} ⊂ O_Kの集合である。（ここではつねに、u_iは固定された積分基底Bを基準に表現される）。 分数イデアルIは、分母 d ∈ O_K によって積分イデアルd*Iとしても表現できる。

これらの表現を使うと、

• 与えられた基底がイデアルIを生成しているかの検査
• Iのノルムの計算
• 逆イデアルI^-1と双対イデアルI^∨の計算
• Kにおける要素を与えられたIの基底に簡約する
• IのHNF(Hermite normal form)を計算
• 入力基底に対してHNFに関するユニモジュラ整数行列
• 2つのイデアルIとJが与えられると、積イデアルIJは決定的多項式時間で計算できる
• J ⊆ Iの場合、商群I/Jからランダム一様な要素を多項式時間で抽出できる
• I/Jを要素ごとに決定的多項式時間で列挙できる。

2.2.1より（標準埋め込みの下で）楕円ガウス分布D_rは、Hの直交基底ベクトルh_iにおける独立な1次元ガウス分布の積和に対応する。このため、K_R上のD_rからの（任意の精度での）サンプリングが多項式時間で可能である。与えれたrに対してBを基準にh_iを表現する。これは σ(B)はHへのpower basisの埋め込みであることを理解すれば十分である。

イデアル格子上の計算問題のうち次の3つを説明する。

• 最小ベクトル問題（SVP）
• 最小独立ベクトル問題(SIVP)
• Bounded-Distance Decoding(BDD)問題 一般性を損なうことなく、以下のスケーリングに従ってO_Kの積分イデアルになるように制約できる。 Iは分母d ∈ O_Kをもつ分数イデアルであるとき、N(d) ∈ <D>であるのでN(d) * I ⊆ O_Kがスケールされたイデアルになる。

定義2.10 (SVPとSIVP) 代数体Kはある幾何学ノルム（l_2ノルム）をもつとし、γ >= 1とする。与えられたノルムでのK-SVP_γ問題とは次の通り：K上の分数イデアルIが与えられたとき、||x|| <= γ * λ_1(I)となる非ゼロの x ∈ Iを探す。K-SIVP_γ問題も同様に定義される。このときノルムが高々 γ * λ_n(I)である線型独立なn個の要素をIから探す。

定義2.11 (BDD) 代数体Kはある幾何学ノルム(l_∞)をもつとし、IはK上の分数イデアルであり、d < λ_1(I)/2とする。与えられたノルムでのK-BDD_{I,d}問題とは次の通り：Iとx ∈ Iに対してy = x + eが与えられる。

代数体Kの整数環R = O_Kでの中国剰余定理(CRT)とその重要な帰結を示す。

補題 2.12 中国剰余定理 整数環Rにおける互いに素なイデアルをI_1,...,I_rをとし、I = prod(I_i) for i ∈ [r]とする。自然な環同型写像 R -> ⊕ (R/I_i) for i ∈ [r] は環準同型 R/I -> ⊕ (R/I_i) for i ∈ [r] を誘導する。

次の補題から、互いに素なイデアルI_1,...,T_rに対して「CRT基底」となるCを効率的に計算できることがわかる。すなわちすべての i!=j に対して c_i = 1 mod I_i かつ c_i = 0 mod I_j となる c_1,....,c_r ∈ R が得られる。このような基底では補題2.12で記述された準同型を逆にすることができる。任意の w = (w_1,...,w_r) ∈　⊕_i (R/I_i)が与えられたとき、v = Σ w_i * c_i mod I はR/Iにおける一意の要素であり、環準同型によるwに写像される。

補題 2.13 (Z基底で表現される)互いに素なイデアル I,J ⊆ R が与えられたとき、c = 1 mod I となる c ∈ J を出力する決定的多項式時間アルゴリズムが存在する。より一般化すると、与えられた互いに素なイデアル I_1,...,I_r に対してCRT基底 c_1,...,c_r ∈ R を出力する決定的多項式時間アルゴリズムが存在する。

証明 このアルゴリズムは整数Zでの拡張されたユークリッド互除法を一般化したものである。IとJに対してそれぞれ適当なZ基底B_IとB_Jが与えられたとき、I+J=R に対する（おそらく優決定された）基底を B＝B_I ∪ B_J とする。このBからRのエルミート標準基底 H = {h_1,...,h_n} を計算する。h_iの表現はBにおける要素のZ結合として計算される。要素 1 ∈ R をHにおける要素のZ結合、したがって B_I ∪ B_J の要素のZ結合として書く。これより x + y = 1 となる x ∈ I, y ∈ J が得られる。最後に要素 c = y = 1 - x ∈ J を出力する。これは 1 mod I である。この主張の後半については、各 c_i を計算するには I = I_i かつ J = prod(I_j) for j!=i を計算すればよい。

次の2つの補題を組み合わせると、任意の分数イデアルI,Jに対して商群I/qIとJ/qJの間の全単射（しかも環上の加群の準同型である）が効率的に計算できる。これは4.2に示すBDDからLWEへの帰着における適当なイデアルIを取り出す(clearing out)重要なツールになる（4.2では、より一般化して、イデアル格子に対する最悪時平均帰着を示す）。これらの補題はおそらく計算的数論の専門家には標準であるが、この文脈での応用は新しいと我々は信じている。

補題 2.14 IとJをRにおけるイデアルとする。イデアル t * I^-1 ⊆ R がJと互いに素となる t ∈ J が存在する。さらにIとJの素イデアル分解が与えられたとき、このようなtは効率的に見つけることができる。

証明 Jの素因子としてP1,...,Prが与えられているとする。i ∈ [r] に対してIを割り切るPiの最大の冪を e_i >= 0 とする。（e_iはlog(N(I))/log(N(Pi))を超えないので、e_iは試行的除算と二分探索によって効率的に計算できる。）i ∈ [r] に対して、Pi^{e_i+1}ではない適当な t_i ∈ Pi^e_i を選ぶ。中国剰余定理により、次を満たす t ∈ R が存在する。

t = 0 mod (I/prod(Pi^r_i) for i ∈ [r]) かつ ∀i ∈ [r], t = t_i mod Pi^{e_i + 1}

（このイデアルは互いに素であることに注意。）それだけでなく、このtはイデアルPi^{e_i+1}とI/prod(Pi^{ei} for i）に対するCRT基底を使うと効率的に見つけることができる。ここでtはすべてのPi^{e_i}を割り切るので、t ∈ Iが従う。

最後に t * I^-1がどのPiでも割り切れないことを示す必要がある。この否定であるPi*I|<t>が成り立つと仮定すると、Pi^{e_i+1}|Pi*Iなので、t ∈ Pi^{e_i+1}が得られる。しかしt = t_i != 0 mod Po^{e_i+1}となり矛盾。

次の補題をはじめて読むときは、イデアルMを乗法的単位元(multiplicative identity)と考えてほしい（すなわち環R全体）。

補題 2.15 IとJをRにおけるイデアルとする。t*I^-1がJと互いに素になるようなtを選ぶ。Kにおける任意の分数イデアルをMとする。このとき関数 Θ_t: K -> K は、環上の加群(R-modules)として M/JM から IM/IJM への準同型を誘導するΘ_t(u) = t*uとして定義される。この準同型は、与えられた I、J、M、t を効率的に逆にするかもしれない[this isomorphism may be efficiently inverted given I,J,M,t]。

証明 Θ_tはt ∈ Rの乗法で表現されるので、Θ_tは環上の加群と同型になる。

この関数は定義域Mと範囲IM/IJMをもつΘ_tから得られると仮定する。このカーネルはJMであるので、

1. Θ_t(JM) = t * JM ⊆ IJM
2. u ∈ M に対して Θ_t(u) = 0 ならば、t*u ∈ IJM であり、(t*I^-1)*(u*M^-1)⊆Jを含意する。

t*I^-1とJはRにおける互いに素なイデアルであるので、u*M^-1 ⊆ J => u ∈ JMが得られる。Θ_tから得られるM/JMからIM/IJMへの関数は単射である。あとはこれが全射であることを示すだけだ。（実際には、どちらの商群も基数N(J)であるので、全射であることはわかるが、効率よく可逆性を示すために構成的証明を与える。）

ν ∈ IMを適当にとる。仮定より、t*T^-1とJは互いに素なので、補題2.13のアルゴリズムを使って、c = 1 mod Jとなるc ∈ t*I^-1を計算できる。このときa = c*ν ∈ t*Mとすると、a - ν = ν * (c-1) ∈ IJMが得られる。ω = a/t ∈　Mとすると、Θ_t(ω) = t*(a/t) = ν mod IJMなので、ω mod JMはν mod IJMの現像(preimage)である。

円分体の重要な性質を示す。5.1では探索問題から判定問題への帰着にこれを使う。ζ = ζ_mに対してK=Q(ζ)を第m円分体とする。これは次数n=φ(m)の最小多項式Φ_m(x)をもつ。R=O_K=Z[ζ]とする。

代数体Kはn個の自己同型 τ_k : K -> Kをもつ。これはk ∈ Z*_mに対するτ_k(ζ)=ζ^kによって定義される。τ_kは自己同型であるので、これが環同型写像であり逆をもつことは容易に確かめられる。自己同型は標準埋め込みの座標を置換する、これは重要な性質である。より正確には、任意のi,k∈Z*_mに対してσ_i(τ_k(ζ)) = σ_{ik}(ζ)であるので、σ ○ τ_kはその座標のある固定された置換におけるσにすぎない。

整数環q ∈ Zに対して、イデアル<q> = q*Rの分解は次のようになる。q'をmを割る最大の冪とする。e = φ(q')とし、fをq mod m/q'の乗数的位数(multiplicative order)とする。次にQiをn/<ef>個の素イデアルとすると<q>=prod(Qi^e)が成り立つ。具体的には、これらのイデアルはQi=<q,Fi(ζ)>で与えられる。ここでΦ_m(x) = prod(Fi(x))^eは、円分多項式Φ_m(x) mod q(すなわちZ_q[x])からモニック既約多項式Fi(x)への分解である。（この分解は効率的に計算できる点に注意。）

特に、整数においては素数qは1 mod mと合同なので、e = f = 1が得られる。体Z_qは単元ωのm次根(primitive m-th root of unity omwga)をもつ（なぜならZ_qの乗法群は位数q-1で巡回する）。Z_q[x]でΦ_m(x)はΦ(x) = prod(x - ω^i) for i ∈ Z*_mに分解される。イデアル<q>は、n個の主イデアルに完全に分解される。Qi = <q, ζ-ω^i>が素でありノルムqをもつ。

次の補題は、自己同型τ_kが素イデアルQ_i上で「推移的」であると主張する。すなわち、ある自己同型τ_kによってQiはQjに置換される。この補題は、円分体がQのガロア拡張であることから直接得られる。ここでは基本的な証明を示す。

補題 2.16 上の表記を使うと、任意のi,j ∈ Z*_mに対してτ_j(Qi) = Q_{i/j}が得られる。

証明 定義からτ_j(qi) = τ_j(<q, ζ - ω^i>) = <q, ζ^j - ω^i>であり、次が得られる。

ζ^j - ω^i = ζ^j - (ω^{i/j})^j = (ζ - ω^{i/j})*(ζ^{j-1} + ω^{i/j} * ζ^{j-2} + ... + (ω^{i/j})^{j-1}) mod q

ここで右の合計は O_K で計算される。つまりτ_j(Qi) ⊆ <q, ζ - ω^{i/j}> = Q_{i/j}である。

同様にζ - ω^{i/j} = (ζ^j)^{1/j} - (ω^i)^{1/j}はζ^j - ω^iの倍数として分解されるので、Q_{i/j} ⊆ <q, ζ^j - ω^i> = τ_j(Qi)が成り立つ。