TFHE実装入門

8.BFV

松岡　航太郎

BFVとは

  • Brakerski-Fan-Vercauteren の略
  • 剰余環上の計算を行う
    • CKKS方式の直接の祖先なので構成がかなり似ている
  • BFVとよく似た方式にBGVが存在する
    • MSB側に平文を乗っけるかLSB側に平文を乗っけるかの違いしかない
      • 相互にノイズの増大があるだけで変換できることが知られている
    • 歴史的にはBGVが先
      • 第２世代に分類される

BFVの構成

  • 実はBFVとTFHEの間にはほとんど差がない
    • 先にBFVをやった方が良さそうである理由の一つ
      • BFVから変換するとCKKSは理解できる
  • もっとも単純な構成では, のTRLWEをBFVとみなせる
    • 多項式を暗号化ているBFV
  • BFV(やCKKS)ではを用いて平文空間を表現する
    • 係数の法を, 平文の法をt$$とすると
  • 暗号文はとなる
    • 平文の周りにroundを付ける流派とを整数にしておく流派があるがこっちのほうがノイズが小さかったはず

BFVの乗算

  • 加算はTFHEと同じなので割愛

  • ということは新しい暗号文として を与えれば乗算になる
    • で割るので乗算は剰余を取らずに実数として考えて実行する
      • Torusでも剰余環でもない値で除算計算していいのかというのは微妙
        • 実際それで計算できてしまうので見逃されている感じがある

Relinearlization

  • 見ての通り出力の暗号文は次元がになってしまう
    • 乗算をこのまま続けていくとどんどん次元が増えてしまう
  • 乗算で増えてしまった次数を減らすのがRelinearlization
    • 実体としてはKeySwitchingと同じ
  • が計算できれば次数が元に戻る
    • を計算するにはをで暗号化して送ってやればいい
      • 乗算によるノイズ増加のトレードオフはTRGSWのExternalProductと一緒
        • S[X]を平文とするTRGSWの下半分(の部分がなので)だけ用意すればいい

Packing

  • Canonical Embeddingと呼ばれることもある
    • Embeddingは日本語で言えば埋め込みでwikiによると数学的構造間の構造を保つような単射のことらしい
  • BFVの特徴としてよく言われるもの
    • (CKKSもだが)一般にはこちらの方式がよく使われる
  • Packingは平文のエンコーディング方法の一つ
    • 暗号文の演算としては変わらない
  • RLWEに見られる性質として, 加算に関しては係数ごとに並列な演算ができる
    • 乗算に関しても独立な計算ができたら便利そう
      • を法とするNTTをかけてやればこれが達成できる
        • とかがよくつかわれる
      • CKKSだとFFT
      • 厳密には次全てを使うのでなければNTTとして完全に分解できる必要はないのでをとかにとってもよい
        • の下でが分解できる式の数が並列で扱えるスカラーの数

Slot2Coeff/Coeff2Slot

  • Packingで値を詰めた場合の各値のことをSlotと呼ぶ
    • たぶんSIMDレジスタ的な気持ち
  • しかしBootstrappingなどをするときには多項式の係数に対して考えたほうが楽な場合が多い
    • 平文がNTTがかかってる状態のやつを暗号上でINTTをかけて係数に平文が来るようにしたい
  • Nai"eveな実装はとても簡単
    • NTTやINTTは行列(Vandermonde matrix)とベクトルの積として書ける
      • これをKeySwitchingとしてやればよい

Lifting

  • Bootstrappingをするにはノイズを消去する必要がある
    • SampleExtractIndexしてTFHEでBootsrapingする方法も知られてはいる
  • BFV固有のBootstrappingのアイデアとしてLiftingがある
    • 平文を基数で分解できる()ものとして最下位を得る演算
      • 最下位を得られればそれを引けば最下位が消去できる
  • 最も単純なものはの場合
    • 乗して引くことを繰り返すだけ

Liftingの疑似コード

Digit Extraction(z,e)
w₀,₀ ← z
For k ← 0 to e-1
  y ← z
  For j ← 0 to k
    wⱼ,ₖ₊₁ ← (wⱼ,ₖ)ᵖ
    y ← (y - wⱼ,ₖ₊₁)/p
  wₖ₊₁,ₖ₊₁
return wₑ,ₑ

Hat Encoding

参考文献

page_number: true