(完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX

目次

1. (完全)準同型暗号の最前線1（入門編)
2. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #1 TLWE
3. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #2 TRLWE & SampleExtarctIndex
4. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX←イマココ
5. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #4 Blind Rotate
6. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #5 Identity Key Switching

初めに

気づいたらもう３月も中旬ですね。卒論とかに追われてたらいつの間にかこんな時期に......TRGSWはやっぱ重かった......ですますに全部直そうかと思ったけど諦めました()

全体の中での位置づけ

TRGSWはBootstrapping Keyと呼ばれる鍵を構成する暗号文形式です。Bootstrapping KeyはHomNANDを構成する上で(厳密には完全準同型暗号を構成する上で、ともいえるが同じ名前なだけでその実態は暗号形式によって異なる)重要な役割を果たす鍵で、公開されるが暗号化に利用するには不十分で一般的な暗号における公開鍵とは異なります。日本語では評価鍵とも呼ばれます。
この記事では次回説明するBlind Rotateという関数の中核的操作であるCMUXについても説明します。

TRGSWとは

Torus Ring-GSWの略でTorus版のRing版GSWという意味です。GSWは格子暗号をベースとする完全準同型暗号の一種で、考案者であるCraig Gentry, Amit Sahai, and Brent Watersの頭文字から来ている。このTRGSWがTFHEの中核といってよく、この暗号文形式を理解することがTFHEを理解する上で重要です。

整数多項式対角行列とTRLWEの積

TRGSWの構成は少々トリッキーなため、いきなりTRGSWの構成を示してもわからないかと思います。実際著者はTFHEの原論文・コードを見てもしばらくわかりませんでした。そこでこの記事ではセキュキャンの講義と同様、TRGSWで達成したい演算を先に定義し、その演算を暗号のままノイズの増加が少ないまま達成するために工夫を加えていくことでTRGSWを構成するという形をとります。
TLWEもTRGSWも加算は暗号のままできるので、完全準同型暗号を構成するには乗算を定義しなければいけません。しかし、Torus同士の乗算は原理上定義できないため、TFHEでは整数とTorus、より正確には整数係数多項式とTorus係数多項式の乗算を暗号上で達成しようと考えます。$(a[X],b[X])$を$m[X]\in\mathbb{T}_N[X]$を平文とするTRLWEとし、$\mu[X]\in\mathbb{Z}_N[X]$とする。すると、以下の演算が定義できることは今まで説明したことから明らかである。
$$\mu[X]\cdot(a[X],b[X])=(\mu[X]\cdot a[X],\mu[X]\cdot b[X])$$
この演算の結果の復号の一部をすることでこれが平文を$\mu[X]$倍する演算と準同型である($\mu[X]$が平文のままなのでその意味では不完全であるが)ことを確認しよう。
$$\mu[X]\cdot b[X]-\mu[X]\cdot a[X]\cdot s[X]=\mu[X]\cdot(b[X]-a[X]\cdot s[X]) \approx \mu[X]\cdot m[X]$$
この演算を$\mu[X]$を暗号に隠して達成するのがTRGSWという暗号形式の目的である。そのために、スケーリング、零行列加算、Decompositionの３つの工夫を加えることでTRGSWを構成する。

スケーリング

今まで見てきたTLWEとTRLWEでは整数係数多項式を平文にとることはできなかった。そこで$\mu[X]$をTorus係数多項式にしてしまい、代わりにTRLWEの方を整数係数多項式にすることで乗算を定義しようというのがスケーリングである。
$Bg\in\mathbb{Z}$が$\mu[X]$のいずれの係数よりも大きいパブリックな定数であるとしよう。(これはTRGSWを構成する際にはとりうる$\mu[X]$の空間を制限するようなパラメータを公開しなければならないということも意味する。)
$Bg\in\mathbb{Z}$をパブリックな定数とする。これで$\mu[X]$の各係数を割ってやることで小数部分をTorusにしようというのが基本的アイデアである。($\mu[X]$のいずれの係数よりも大きいという要件は過剰であった......あくまで整数をそのまま掛けるのと結果が丸め誤差を除いて同じになれば十分である)
実数(Torusは実数に含まれる)を整数に丸める演算(具体的な実装はノイズの評価が変わるだけなので四捨五入でも切り捨てでも銀行丸めでもいい。TRLWEを渡した場合、多項式の係数それぞれに施される)を$\lceil\cdot\rfloor$とする。$\lceil\cdot\rfloor$の中の乗算ではTorusを実数として捉え直すとすると、下のような関係が成立することがわかる。
$\frac{\mu[X]}{Bg}\cdot\lceil Bg\cdot(a[X],b[X])\rfloor\approx\mu[X]\cdot(a[X],b[X])$
$\frac{\mu[X]}{Bg}\in\mathbb{T}_N[X]$であるので、これで平文をTorus係数多項式にすることができた。$Bg$は公開されるパラメータであるので、TRLWEに施す$Bg$倍して丸めるという操作は演算をするタイミングで施すことができる。

零行列加算

$\frac{\mu[X]}{Bg}$がTorus係数多項式だからといってこれをTRLWEに普通に暗号化すればそれで終わりというわけではないのは明らかである。(そうであればTRGSWなんぞ要らないわけであるし)そこで、先の式と全く等価だが、Torus係数多項式を対角行列へと変形する。TRLWEをこの一連の記事では多項式をスカラーとする行ベクトルと考えていることに留意されたし。

\lceil Bg\cdot(a[X],b[X])\rfloor\cdot
\begin{pmatrix}
\frac{\mu[X]}{Bg} & 0 \\
0 & \frac{\mu[X]}{Bg}
\end{pmatrix}=\frac{\mu[X]}{Bg}\cdot\lceil Bg\cdot(a[X],b[X])\rfloor

これによって平文は$\frac{\mu[X]}{Bg}$から

\begin{pmatrix}
\frac{\mu[X]}{Bg} & 0 \\
0 & \frac{\mu[X]}{Bg}
\end{pmatrix}

に変わったこれがTRGSWの平文になる。これを暗号化する、つまり隠すために導入されるのが零行列加算(という名前は著者が適当につけたものだが)である。今、$(a_1[X],b_[X]),(a_2[X],b_[X])$をどちらも(バイナリではなくTorusとしての)$0$を暗号化したTRLWEとする。(乱数を使って暗号化するので当然同じ暗号文ではない)これらを使うと以下の式が成り立つ。

\lceil Bg\cdot(a[X],b[X])\rfloor\cdot
\left(
\begin{pmatrix}
\frac{\mu[X]}{Bg} & 0 \\
0 & \frac{\mu[X]}{Bg}
\end{pmatrix}+
\begin{pmatrix}
a_1[X] & b_1[X]\\
a_2[X] & b_2[X]
\end{pmatrix}
\right)\approx\frac{\mu[X]}{Bg}\cdot\lceil Bg\cdot(a[X],b[X])\rfloor

この式を理解するための基本的発想は$0$の暗号文を定数倍してたしたものはやはり$0$の暗号文であるということである。つまり、今追加した$0$を暗号化したTRLWEを並べて作った多項式を要素とする行列はノイズを増やすだけで計算結果として得られる暗号文の平文($\mu[X]\cdot m[X]$)は変えないことである。

もう少し明示的に書くと、以下は$0$の暗号文である。

\lceil Bg\cdot a[X]\rfloor\cdot (a_1[X], b_1[X]) + \lceil Bg\cdot b[X]\rfloor\cdot (a_2[X], b_2[X])

こうして$0$の暗号文の行列を追加した、

\begin{pmatrix}
\frac{\mu[X]}{Bg} & 0 \\
0 & \frac{\mu[X]}{Bg}
\end{pmatrix}+
\begin{pmatrix}
a_1[X] & b_1[X]\\
a_2[X] & b_2[X]
\end{pmatrix}

はいうなれば$0$の暗号文で平文をマスクしたような形になっている。これを一つの行列にくっつけると、

\begin{pmatrix}
\frac{\mu[X]}{Bg}+a_1[X] & b_1[X]\\
a_2[X] & \frac{\mu[X]}{Bg}+b_2[X]
\end{pmatrix}

となる。下の行が$\frac{\mu[X]}{Bg}$を平文とするTRLWEであるのは明らかである。上の行は、平文がTRLWEの秘密鍵の定数項を$S_0$として$\frac{\mu[X]}{Bg}\cdot S_0$を平文とするTRLWEになっていることは復号処理において$b[X]-a[X]\cdot S[X]$をすることから明らかである。

つまりこれによって複数のTRLWEとして平文を隠すことができる。

Bgに関するトレードオフ

スケーリングでは、$Bg$倍して整数に丸める際に、丸め誤差が発生する。$Bg$が大きければ大きいほど、より多くの桁を整数に取り入れることができるため、丸め誤差は小さくなる。しかし、$Bg$を大きくすればするほど、

\lceil Bg\cdot a[X]\rfloor\cdot (a_1[X], b_1[X]) + \lceil Bg\cdot b[X]\rfloor\cdot (a_2[X], b_2[X])

という0の暗号文に起因するノイズが大きくなる。

Decomposition

Decompositionは前に述べたトレードオフを逃れる形でノイズを減少させるためのテクニックである。これはGSWの根幹となっているアイデアである。
アイデアを端的に述べると、スケーリングでやったように$Bg$倍して1つの整数係数多項式に丸めるのではなく、$Bg$を基数とみなして$l$個の整数係数多項式に丸めるというものである。(つまり、前に説明したスケーリングは$l=1$の場合に相当する)
こうすることに依って、0の暗号文に起因するノイズは$Bg$によって決まるが、丸めによる誤差の方は$Bg^l$に依って決まるようにすることができる。
$l$を増やせば丸めのノイズを減らすことができるが、$l$を増やすと0の暗号文由来のノイズが増えるのでその意味では$Bg$と同様に限界はある。しかし、$l$は丸めには指数で効き0の暗号文由来のノイズには線形で効くため、$Bg$のみを動かすよりノイズを小さく取れる。(実際には、$l$を大きくすると、あとにみるExternal Productにおける多項式乗算の回数も増加して計算量が著しく増加するので、ノイズと計算量のトレードオフも発生する)
Decompositionの逆の操作を見ることでイメージをつけよう。Decompositionによって得たいのは$(\bar a_1[X],...,\bar a_l[X],\bar b_1[X],...,\bar b_l[X])$の部分である。

(a[X],b[X])≈ (\bar a_1[X],...,\bar a_l[X],\bar b_1[X],...,\bar b_l[X])
\left(
    \begin{array}{cc}
      \frac{1}{Bg} & 0 \\
      \frac{1}{Bg^2} & 0 \\
      ⋮ & ⋮\\
      \frac{1}{Bg^l} & 0 \\
      0 & \frac{1}{Bg}\\
      0 & \frac{1}{Bg^2}\\
      ⋮&⋮\\
      0 & \frac{1}{Bg^l}\\
    \end{array}
\right)

これを見ると明らかなように、DecompositionはTRLWEに対する操作というよりは、多項式に対する操作である。つまり、$\mathrm{Decomposition}(a[X])=(\bar a_1[X],...,\bar a_l[X])$のように$a[X]$に関する部分を計算するときは$b[X]$に依存しない演算である。
$\bar a_i[X]$の$j$次の係数を$\bar a_{ij}$とすると、Decompositionでは$\bar a_{ij}$を以下の式に依って定める。つまり、各係数の丸め誤差が最小になるように定める。

\mathop{\rm arg~min}\limits_{ā_{ij}} ∑^{N-1}_{j=0}(a_j-∑_{i=1}^{l}\frac{ā_{ij}}{Bg^i})^2\ s.t.\ ā_{ij}\in[-\lceil \frac{Bg}{2}\rceil,\lfloor\frac{Bg}{2}\rfloor)

ここで$ā_{ij}\in[-\lceil \frac{Bg}{2}\rceil,\lfloor\frac{Bg}{2}\rfloor)$としていて$[0,Bg)$でないのは、0の暗号文に起因するノイズはこれらの絶対値に比例して増加するためである。

Bgが2の冪であるときのDecompositionの具体的アルゴリズム

$Bg=2^{Bgbit}$のように2の冪で書ける時のDecompositionのアルゴリズムは特に単純であるため、そのような場合について説明しよう。このような場合では、以下を満たす$\hat{a}_{ij}$を構成することは比較的容易である。

\mathop{\rm arg~min}\limits_{\hat{a}_{ij}} ∑^{N-1}_{j=0}(a_j-∑_{i=1}^{l}\frac{\hat{a}_{ij}}{Bg^i})^2\ s.t.\ \hat{a}_{ij}\in[0,Bg)

また、$\hat{a}_{ij}, \bar a_{ij}$の間に以下のような関係が明らかに成り立つ。

â_{ij} = \begin{cases} Bg+ā_{ij}\qquad if\quad â_{ij}\geq\frac{Bg}{2}\\ ā_{ij}\qquad otherwise\end{cases}

$Bg+ā_{ij}$という表現は、いうなれば一つ上の桁を$1$増やしてそこからの差分で持って表現するので、繰り上がりに近い処理である。
$\hat{a}_{ij}$をまず構成し、上の関係式から$\bar a_{ij}$を構成すると言うアイデアをナイーブに実装すると以下のようになる。

2021年5月追記　四捨五入のための加算をしないと丸めにバイアスがついてしまって演算によってはノイズが偏って死ぬので修正した。このバグは原著者実装に存在するものなのでそれを真似たものは全て持っているはずである。私の実装とVSPで使っているcuFHEのフォークでは修正済みである。

Decomposition(a[X])
  for j from 0 to N-1
    roundeda = aⱼ+(1<<(32-Bgbit*l-1)) //四捨五入のための加算
    for i from 1 to l
      âᵢⱼ= (roundeda>>(32-Bgbit*i))&(Bg-1)
  for i from l to 1
    for j from 0 to N-1
      if âᵢⱼ ≥ Bg/2
        āᵢⱼ = âᵢⱼ - Bg
        â₍ᵢ₋₁₎ⱼ += 1
      else
        āᵢⱼ = âᵢⱼ
  return 𝐚̄[X]

実際の実装では、「$Bg+ā_{ij}$という表現は繰り上がりに近い」というのを実際に加算器の繰り上がりで計算させてif文をなくすのだが、理論を理解するという意味ではこの疑似コードで十分であろう。

TRGSWの具体的構成

ここまで説明した３つのアイデアを組み合わせると、TRGSWは具体的には以下のような形をした暗号文として定義すれば良い。

\left( \begin{array}{cc} \frac{μ[X]}{Bg} & 0 \\
\frac{μ[X]}{Bg^2} & 0 \\
 ⋮ & ⋮\\
 \frac{μ[X]}{Bg^l} & 0 \\
 0 & \frac{μ[X]}{Bg}\\
 0 & \frac{μ[X]}{Bg^2}\\
 ⋮&⋮\\
 0 & \frac{μ[X]}{Bg^l}\\
\end{array} \right)
+
\left( \begin{array}{cc}
a_1[X] & b_1[X] \\
 a_2[X] & b_2[X] \\
 ⋮ & ⋮\\
 a_l[X] & b_l[X] \\
 a_{l+1}[X] & b_{l+1}[X]\\
 a_{l+2}[X] & b_{l+2}[X]\\
 ⋮&⋮\\
 a_{2l}[X] & b_{2l}[X]\\
 \end{array} \right)

External Product

Decompositionを施したTRLWEとTRGSWの積をこのように呼ぶ。これによって、暗号化したまま整数係数多項式とTorus係数多項式の積を計算することができる。
TRGSWを$\mathbf{C}$とすると、このような演算がExtranal Product($\boxdot$)はこのようにかける。

\mathbf{C}\boxdot (a[X],b[X]):=\mathrm{Decomposition}((a[X],b[X]))⋅\mathbf{C}

TRGSWはTRLWEのベクトルのようにみなせるから、自然にTRGSWとTRGSWの積も考えることができる(Internal Productと呼ばれる)が、HomNANDの構成には使わないため省略する。余談だが、歴史的には、Internal Productの方がGSWで先に提案されたものである。

平文空間に関する注意

ここまで一般性を保つために$\mu[X]\in\mathbb{Z}_N[X]$としていたが、HomNANDを構成する範囲では、$\mu[X]$ではなく$\mu\in\mathbb{B}$で十分である。次のCMUXの説明を含め、以降はTRGSWの平文は$\mathbb{B}$、つまり0か1であるとして話をする。

CMUX

CMUXはControlled MUXの略である。External Productを用いてMUXを構成することができるというのがここで話すことである。アイデアは単純で、以下に示す具体的な構成のみで十分であろう。

\mathbf{C}⊡ [(a_1[X],b_1[X])-(a_0[X],b_0[X])]+(a_0[X],b_0[X])

TRGSWの平文が0なら$(a_0[X],b_0[X])$、1なら$(a_1[X],b_1[X])$が選ばれる。当然External Productも加減算もノイズが増加するために、CMUXを行える回数には限度がある。

次回

この鬼門を乗り越えると、TFHEが非線形演算を得意とする所以であるBlind Rotateの話をすることができます。まぁ執筆はゆっくりになりそうですが......