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を導出する
  • 以下のような演算を復号せずにやりたい(準同型暗号上の乗算)
  • これができると暗号文のママ復号に相当する計算ができる
  • この行列の部分をどうにかして暗号文にしたのがTRGSW

μ[X]∈ZN[X]μ[X]⋅(a[X],b[X])=(a[X],b[X])⋅(μ[X]00μ[X])\begin{aligned} μ[X]&∈\mathbb{Z}_N[X]\\ μ[X]⋅(a[X],b[X])&=(a[X],b[X])⋅ \left( \begin{array}{cc} μ[X] & 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⋅(a[X],b[X])⌋⋅(μ[X]Bg00μ[X]Bg)=(ar[X],br[X])≈μ[X]⋅(a[X],b[X])br[X]−ar[X]⋅s[X]=μ[X](b[X]−a[X]⋅s[X]+er[X])\begin{aligned} ⌈Bg⋅(a[X],b[X])⌋⋅ \left( \begin{array}{cc} \frac{μ[X]}{Bg} & 0 \\ 0 & \frac{μ[X]}{Bg} \end{array} \right)&=(a_r[X],b_r[X])\\ &≈μ[X]⋅(a[X],b[X])\\ b_r[X]-a_r[X]⋅s[X] = μ[X](b[X] - &a[X]⋅s[X]+e_r[X]) \end{aligned}

零行列加算

  • 行列に0を暗号化したTRLWEを加算することで行列を隠す(暗号文でマスクする)
  • 足した行列の下の行は普通のTRLWE、上もTRLWEとして解釈できる
  • (a1[X],b1[X]),(a2[X],b2[X])(a_1[X],b_1[X]),(a_2[X],b_2[X])は0を暗号化したTRLWE
  • つまり、b1[X]−a1[X]⋅s[X]=0+e1[X]b_1[X]-a_1[X]⋅s[X]=0+e_1[X]
  • 0の暗号文を定数倍し足しても0の暗号文のためノイズが増えるだけで結果の平文は同じ

⌈Bg⋅(a[X],b[X])⌋⋅[(μ[X]Bg00μ[X]Bg)+(a1[X]b1[X]a2[X]b2[X])]≈μ[X]⋅(a[X],b[X])+⌈Bg⋅a[X]⌋⋅(a1[X],b1[X])+⌈Bg⋅b[X]⌋⋅(a2[X],b2[X]) ⌈Bg⋅(a[X],b[X])⌋⋅[ \left( \begin{array}{cc} \frac{μ[X]}{Bg} & 0 \\ 0 & \frac{μ[X]}{Bg} \end{array} \right)+ \left( \begin{array}{cc} a_1[X] & b_1[X] \\ a_2[X] & b_2[X] \end{array} \right)]\\ ≈μ[X]⋅(a[X],b[X])+⌈Bg⋅a[X]⌋⋅(a_1[X],b_1[X])+⌈Bg⋅b[X]⌋⋅(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})を満たすとする
  • 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]として返す
  • [0,Bg)[0,Bg)でなく[−Bg2,Bg2)[-\frac{Bg}{2},\frac{Bg}{2})にとるのはノイズを小さくしたいから

Decompositionでつくるもの

  • 逆操作を先に見ることでイメージを得よう
  • ⌈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(疑似コード)

Decomposition(a[X])
  offset = 0 //各桁にBg/2を足すための定数をつくる
  for i form 1 to l
    offset += Bg / 2 * (1 << (32 - i * Bgbit))
  for i form 0 to N-1
    ãᵢ = aᵢ+offset //ここで繰り上がりがあるからoffsetをつくる
  for i from 1 to l
    for j from 0 to N-1
      //2進でBgbit桁(最大Bg-1)を取り出してBg/2を引く
      āᵢⱼ=((ãⱼ>>(32-Bgbit*i))&(Bg-1))-Bg/2 //&はbit演算のAND
  return 𝐚̄[X]

offsetでうまく行くことの証明(方針)

  • offsetを桁の数だけ作らずにひとつだけでいいことは直感的でない
  • 前提としてもし各桁を[0,Bg)[0,Bg)の範囲で取るならmaskだけで良い
  • a^ij=((aᵢ>>(32−Bgbit∗i))&(Bg−1))â_{ij}=((aᵢ>>(32-Bgbit*i))\&(Bg-1))としよう
  • a[X]からa^[X]a[X]から\mathbf{â}[X]を経由したaˉ[X]\mathbf{ā}[X]への変換を考える
  • これが結局前の疑似コードと一致することを示す

offsetでうまく行くことの証明(基本的アイデア)

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}

となるようにaˉijā_{ij}を決めることができる(要は桁上がりをしている)

offsetでうまく行くことの証明(疑似コード)

  • このアイデアをナイーブに実装した場合の疑似コードを示そう
Decompositionhat(a[X])
  for i from 1 to l
    for j from 0 to N-1
      âᵢⱼ=((aⱼ>>(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]

offsetでうまく行くことの証明(ちょっと最適化)

  • 前のスライドのコードをbit演算でちょっと最適化すると以下のようになる
  • これを見るとBg/2を足してBg以上になったら上の桁に繰り上がっている
  • この繰り上がり処理を加算器に任せようと思うとoffsetになる
Decompositionhatopt(a[X])
  for i from 1 to l
    for j from 0 to N-1
      âᵢⱼ=((aᵢ>>(32-Bgbit*i))&(Bg-1))
  for i from l to 1
    for j from 0 to N-1
      temp = âᵢⱼ + Bg/2
      â₍ᵢ₋₁₎ⱼ += temp>>Bgbit //temp > Bgなら1
      āᵢⱼ = (temp & (Bg-1)) - Bg/2 //マスクからはみ出たところは上の桁に行っている
  return 𝐚̄[X]

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

  • DecompostionをTRLWEに施したのと掛け算をすると考えると暗号文はこうなる
  • 実際は平文空間は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

  • DecompositionされたTRLWEとTRGSWの積のこと
  • TRGSWをC\mathbf{C}とする
  • ちなみにInternal ProductはTRGSW同士の積を指すが使わないので省略
    C⊡(a[X],b[X]):=Decomposition((a[X],b[X]))⋅C \mathbf{C}⊡ (a[X],b[X]):=\mathrm{Decomposition}((a[X],b[X]))⋅\mathbf{C}

CMUX

  • External Productを使うことで、マルチプレクサを作ることができる
  • TRGSWの平文空間を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をするたびにノイズが増えるので回数には制限がある
  • これだけでもDeterministic Finite Automataが作れるのでいろいろできるがここでは省略

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

llに関するトレードオフ

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

TRGSWのパラメータについて

  • Bgbit=6,Bg=64,l=3Bgbit=6,Bg=64,l=3
  • TRGSWの行ごとの平文に相関があることを利用した攻撃は知られていない
  • 現状の安全性は行毎のTRLWEの安全性で評価されている

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

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

page_number: true