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

スケーリング

  • TRGSWの構成には３つ重要なアイデアがあり、１つがスケーリング
  • TFHEで考える暗号文は整数係数多項式をそのまま平文にすることはできない
  • 行列の方をTorus係数にしてその分をTRLWEに押し付けて整数係数に丸める
    • 丸めの分だけノイズが増えることに注意
  • は丸めによるノイズ
  • ノイズが倍されることに留意

零行列加算

  • 行列に0を暗号化したTRLWEを加算することで行列を隠す(暗号文でマスクする)
    • 足した後の行列はTRLWEのベクトルとして解釈できる
  • は0を暗号化したTRLWE
  • つまり、
    • 0の暗号文を定数倍し足しても0の暗号でノイズが増えるだけ

何をしているか

に関するトレードオフ

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

Decomposition(一般的定義)

  • TRLWEを丸めるときにを基数とみなして桁に分解する
    • を大きくせずに丸めによるノイズを減らせる
  • Decompositionは多項式を入力にとる
  • 出力として多項式のベクトルを返す
    • 要素となる多項式の係数は入力となる多項式の係数の一桁を抜き出したもの
    • Torusを進表現したときの１番上の桁を集めたもの、次の桁という具合でベクトルの要素は並ぶ
  • はを満たすとする
    • でなくにとるのはノイズを小さくしたいから
  • を次の係数がである多項式とする
  • 多項式のベクトルの番目の要素をとして返す

Decompositionでつくるもの

  • 逆操作を先に見ることでイメージを得よう
    • スペースの都合でk=1の場合にしている
  • はの場合のDecompositionになっている

Decomposition(具体的構成)

  • を具体的に与えるアルゴリズムを示していく
    • 簡単のためと書ける場合に限定する
    • Torusはuint32_tで表現されているものとする
  • だと係数が負になる場合を考える必要がある
  • 各桁にをたすことでにずらす
  • こうするとbitマスクで取り出すだけで良くなる
  • 最後に各係数からを引いて元に戻す

Decomposition(基本的アイデア)

  • 前提としてもし各桁をの範囲で取るならmaskだけで良い
    • にとる場合をとする
    • つまりᵢ
    • は四捨五入のための定数
    • これはを満たす
  • からを経由したへの変換を考える
    • 以下のような関係が成り立つようにを決めることができる(要は桁上がりをしている)

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の具体的構成(平文がの場合)

  • DecompostionをTRLWEに施して掛け算をすると考えるとの暗号文は以下
    • 実際は平文空間はだけでもHomNANDはつくれる

に関するトレードオフ

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

External Product

  • TRLWEとTRGSWの積のこと
  • TRGSWをとしての場合を書く(はの略記)
  • ちなみにInternal ProductはTRGSW同士の積を指すが使わないので省略

CMUX

  • Controlled MUXの略らしい
  • External Productを使うことで、マルチプレクサを作ることができる
    • TRGSW()の平文空間をとする
    • TRGSWの平文が0なら、1ならが選ばれる
  • CMUXをするたびにノイズが増えるので回数には制限がある
  • これだけでもWeighted Finite Automataが作れたりするが省略

TRGSWのパラメータについて

    • はTRLWEと一致しないといけないことに注意
  • 実はに適用するとに適用するは別にすると良いことが知られている
  • TRGSWの行ごとの平文に相関があることを利用した攻撃は知られていない
  • 現状の安全性は行毎のTRLWEの安全性で評価されている
    • 結局Integer LWEに落ちる

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

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

page_number: true