TFHE実装入門

3.TRGSW & CMUX

松岡　航太郎

説明内容のHomNANDでの位置づけ

  • CMUXは次回説明するBlind Rotateで中心的役割を果たす

TRGSWとは

  • Torus Ring-GSWの略
  • GSWは考案者のCraig Gentry, Amit Sahai, and Brent Watersの頭文字を取ったもの
  • GSWは完全準同型暗号の一種で、それをTorus係数多項式に拡張したのがTRGSW
  • TRGSWを理解することがTFHEを理解する上で特に重要

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

  • いきなりTRGSWの具体的構成をみてもモチベーションがわからない
  • TRGSWを使ってやりたい演算を構成していくことでTRGSWを導出する
  • 以下のような演算を復号せずにやりたい(準同型暗号上の多項式乗算)
    • 加法ができることは既に見ている
    • 簡単のためここではk=2k=2を仮定する
  • この行列の部分をどうにかして暗号文にしたのがTRGSW

μ[X]∈ZN[X]μ[X]⋅(a0[X],a1[X],b[X])=(a0[X],a1[X],b[X])⋅(μ[X]000μ[X]000μ[X])\begin{aligned} μ[X]&∈\mathbb{Z}_N[X]\\ μ[X]⋅(a_0[X],a_1[X],b[X])&=(a_0[X],a_1[X],b[X])⋅ \left( \begin{array}{ccc} μ[X] & 0 & 0\\ 0 & μ[X] & 0\\ 0 & 0 & μ[X]\\ \end{array} \right) \end{aligned}

スケーリング

  • TRGSWの構成には３つ重要なアイデアがあり、１つがスケーリング
  • TFHEで考える暗号文は整数係数多項式をそのまま平文にすることはできない
  • 行列の方をTorus係数にしてその分をTRLWEに押し付けて整数係数に丸める
    • 丸めの分だけノイズが増えることに注意
  • Bg∈Z,Bg>μ[X],er[X]∈TN[X]Bg\in\mathbb{Z},Bg>μ[X],e_r[X]∈\mathbb{T}_N[X]
  • er[X]e_r[X]は丸めによるノイズ
  • ノイズがμ[X]μ[X]倍されることに留意
    ⌈Bg⋅(a0[X],a1[X],b[X])⌋⋅(μ[X]Bg00μ[X]Bg000μ[X]Bg)=(a0r[X],a1r,br[X])≈μ[X]⋅(a0[X],a1[X],b[X])br[X]−ar[X]⋅s[X]=μ[X](b[X]−a[X]⋅s[X]+er[X])\begin{aligned} ⌈Bg⋅(a_0[X],a_1[X],b[X])⌋⋅& \left( \begin{array}{ccc} \frac{μ[X]}{Bg} & 0 \\ 0 & \frac{μ[X]}{Bg} & 0\\ 0 & 0 & \frac{μ[X]}{Bg} \end{array} \right)=(a_0^r[X],a_1^r,b^r[X])\\ &≈μ[X]⋅(a_0[X],a_1[X],b[X])\\ b^r[X]-\mathbf{a}^r[X]⋅\mathbf{s}[X] &= μ[X](b[X] - \mathbf{a}[X]⋅\mathbf{s}[X]+e_r[X]) \end{aligned}

零行列加算

  • 行列に0を暗号化したTRLWEを加算することで行列を隠す(暗号文でマスクする)
    • 足した後の行列はTRLWEのベクトルとして解釈できる
  • (ai[X],bi[X])(\mathbf{a}_i[X],b_i[X])は0を暗号化したTRLWE
  • つまり、bi[X]−ai[X]⋅s[X]=0+ei[X]b_i[X]-\mathbf{a}_i[X]⋅s[X]=0+e_i[X]
    • 0の暗号文を定数倍し足しても0の暗号でノイズが増えるだけ

⌈Bg⋅(a[X],b[X])⌋⋅[(μ[X]Bg090μ[X]Bg000μ[X]Bg)+(a0[X]b0[X]a1[X]b1[X]a2[X]b2[X])]≈μ[X]⋅(a[X],b[X])+⌈Bg⋅a0[X]⌋⋅(a0[X],b0[X])+⌈Bg⋅a1[X]⌋⋅(a1[X],b1[X])+⌈Bg⋅b[X]⌋⋅(a2[X],b2[X]) ⌈Bg⋅(\mathbf{a}[X],b[X])⌋⋅[ \left( \begin{array}{ccc} \frac{μ[X]}{Bg} & 0 & 9\\ 0 & \frac{μ[X]}{Bg} & 0\\ 0 & 0 & \frac{μ[X]}{Bg} \end{array} \right)+ \left( \begin{array}{cc} \mathbf{a}_0[X] & b_0[X] \\ \mathbf{a}_1[X] & b_1[X] \\ \mathbf{a}_2[X] & b_2[X] \end{array} \right)]\\ ≈μ[X]⋅(\mathbf{a}[X],b[X])+⌈Bg⋅a_0[X]⌋⋅(\mathbf{a}_0[X],b_0[X])\\ +⌈Bg⋅a_1[X]⌋⋅(\mathbf{a}_1[X],b_1[X])+⌈Bg⋅b[X]⌋⋅(\mathbf{a}_2[X],b_2[X])

何をしているか

BgBgに関するトレードオフ

  • ⌈Bg⋅a[X]⌋,⌈Bg⋅b[X]⌋⌈Bg⋅a[X]⌋,⌈Bg⋅b[X]⌋の係数の最大値はBgBg
  • つまりBgBgを大きくすると0の暗号文由来のノイズが大きく影響する
  • しかしBgBgを小さくすると丸めによるノイズが大きくなる
  • このトレードオフから逃れるのがDecomposition

Decomposition(一般的定義)

  • TRLWEを丸めるときにBgBgを基数とみなしてll桁に分解する
    • BgBgを大きくせずに丸めによるノイズを減らせる
  • Decompositionは多項式a[x]∈TN[X]a[x]∈T_N[X]を入力にとる
  • 出力として多項式のベクトルaˉ[X]∈(ZN[X])l\mathbf{ā}[X]∈(\mathbb{Z}_N[X])^lを返す
    • 要素となる多項式の係数は入力となる多項式の係数の一桁を抜き出したもの
    • TorusをBgBg進表現したときの１番上の桁を集めたもの、次の桁という具合でベクトルの要素は並ぶ
  • aˉijā_{ij}はarg minaˉij∑j=0N−1(aj−∑i=1laˉijBgi)2 s.t. aˉij∈[−Bg2,Bg2)\mathop{\rm arg~min}\limits_{ā_{ij}} ∑^{N-1}_{j=0}(a_j-∑_{i=1}^{l}\frac{ā_{ij}}{Bg^i})^2\ s.t.\ ā_{ij}∈[-\frac{Bg}{2},\frac{Bg}{2})を満たすとする
    • [0,Bg)[0,Bg)でなく[−Bg2,Bg2)[-\frac{Bg}{2},\frac{Bg}{2})にとるのはノイズを小さくしたいから
  • aˉi[X]ā_i[X]を0≤j≤N−10≤j≤N-1次の係数がaˉijā_{ij}である多項式とする
  • 多項式のベクトルaˉ[X]\mathbf{ā}[X]の1≤i≤l1≤i≤l番目の要素をaˉi[X]ā_i[X]として返す

Decompositionでつくるもの

  • 逆操作を先に見ることでイメージを得よう
    • スペースの都合でk=1の場合にしている
  • ⌈Bg⋅(a[X],b[X])⌋⌈Bg⋅(a[X],b[X])⌋はl=1l=1の場合のDecompositionになっている

(a[X],b[X])≈(aˉ1[X],...,aˉl[X],bˉ1[X],...,bˉl[X])(1Bg01Bg20⋮⋮1Bgl001Bg01Bg2⋮⋮01Bgl) (a[X],b[X])≈ (ā_1[X],...,ā_l[X],b̄_1[X],...,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(具体的構成)

  • aˉi[X]ā_i[X]を具体的に与えるアルゴリズムを示していく
    • 簡単のためBg=2BgbitBg=2^{Bgbit}と書ける場合に限定する
    • Torusはuint32_tで表現されているものとする
  • [−Bg2,Bg2)[-\frac{Bg}{2},\frac{Bg}{2})だと係数が負になる場合を考える必要がある
  • 各桁にBg2\frac{Bg}{2}をたすことで[0,Bg)[0,Bg)にずらす
  • こうするとbitマスクで取り出すだけで良くなる
  • 最後に各係数からBg2\frac{Bg}{2}を引いて元に戻す

Decomposition(基本的アイデア)

  • 前提としてもし各桁を[0,Bg)[0,Bg)の範囲で取るならmaskだけで良い
    • [0,Bg)[0,Bg)にとる場合をa^âとする
    • つまりa^ij=(((aᵢ+232−Bgbit⋅l−1)>>(32−Bgbit⋅i))&(Bg−1))â_{ij}=(((aᵢ+2^{32-Bgbit⋅l-1})>>(32-Bgbit⋅i))\&(Bg-1))
    • 232−Bgbit⋅l−12^{32-Bgbit⋅l-1}は四捨五入のための定数
    • これはarg mina^ij∑j=0N−1(aj−∑i=1la^ijBgi)2 s.t. a^ij∈[0,Bg)\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)を満たす
  • a[X]からa^[X]a[X]から\mathbf{â}[X]を経由したaˉ[X]\mathbf{ā}[X]への変換を考える
    • 以下のような関係が成り立つようにaˉijā_{ij}を決めることができる(要は桁上がりをしている)

a^ij={Bg+aˉijifa^ij≥Bg2aˉijotherwiseâ_{ij} = \begin{cases} Bg+ā_{ij}\qquad if\quad â_{ij}≥\frac{Bg}{2}\\ ā_{ij}\qquad otherwise\end{cases}

Decomposition(疑似コード)

  • このアイデアをナイーブに実装した場合の疑似コードを示そう
    • やっていることはほぼ繰り上がり計算なので加算機にそれを任せる最適化が可能だが複雑になりすぎるのでここでは説明しない
    • Torusは32bit固定小数点表現されていることを仮定している
Decomposition(a[X])
  roundoffset = 1 << (32 - l * Bgbit - 1)
  for i from 1 to l
    for j from 0 to N-1
      âᵢⱼ=(((aⱼ+roundoffset)>>(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]

TRGSWの具体的構成(平文がZN[X]\mathbb{Z}_N[X]の場合)

  • DecompostionをTRLWEに施して掛け算をすると考えるとk=1k=1の暗号文は以下
    • 実際は平文空間はB\mathbb{B}だけでもHomNANDはつくれる
      (μ[X]Bg0μ[X]Bg20⋮⋮μ[X]Bgl00μ[X]Bg0μ[X]Bg2⋮⋮0μ[X]Bgl)+(a1[X]b1[X]a2[X]b2[X]⋮⋮al[X]bl[X]al+1[X]bl+1[X]al+2[X]bl+2[X]⋮⋮a2l[X]b2l[X]) \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

  • TRLWEとTRGSWの積のこと
  • TRGSWをC\mathbf{C}としてk=2k=2の場合を書く(Decomp\mathrm{Decomp}はDecomposition\mathrm{Decomposition}の略記)
  • ちなみにInternal ProductはTRGSW同士の積を指すが使わないので省略
    C⊡(a[X],b[X]):=(Decomp(a0[X]),Decomp(a1[X]),Decomp(b[X]))⋅C \mathbf{C}⊡ (\mathbf{a}[X],b[X]):=(\mathrm{Decomp}(a_0[X]),\mathrm{Decomp}(a_1[X]),\mathrm{Decomp}(b[X]))⋅\mathbf{C}

llに関するトレードオフ

  • llを増やせば丸めのノイズを減らすことができる
  • llを増やすと0の暗号文由来のノイズが増える
  • llは丸めには指数で効き0の暗号文由来には線形で効く
  • llを増やすほどExternal Productの多項式乗算が増えて重くなる
  • トレードオフの出方がBgBgと違う

CMUX

  • Controlled MUXの略らしい
  • External Productを使うことで、マルチプレクサを作ることができる
    • TRGSW(C\mathbf{C})の平文空間をB\mathbb{B}とする
    • TRGSWの平文が0なら(a0[X],b0[X])(a_0[X],b_0[X])、1なら(a1[X],b1[X])(a_1[X],b_1[X])が選ばれる
  • CMUXをするたびにノイズが増えるので回数には制限がある
  • これだけでもWeighted Finite Automataが作れたりするが省略

C⊡[(a1[X],b1[X])−(a0[X],b0[X])]+(a0[X],b0[X])\mathbf{C}⊡ [(\mathbf{a}_1[X],b_1[X])-(\mathbf{a}_0[X],b_0[X])]+(\mathbf{a}_0[X],b_0[X])

TRGSWのパラメータについて

  • k=2,Bgbit=8,l=2k=2,Bgbit=8,l=2
    • kkはTRLWEと一致しないといけないことに注意
  • TRGSWの行ごとの平文に相関があることを利用した攻撃は知られていない
  • 現状の安全性は行毎のTRLWEの安全性で評価されている
    • 結局Integer LWEに落ちる

TRGSWで最低限実装すべきもの

  • 平文をB\mathbb{B}としたTRGSWの暗号化(復号は必要ない)
  • External Product
  • CMUX

page_number: true