TFHE実装入門

4.Blind Rotate

松岡　航太郎

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

Blind Rotateとは

  • 多項式(TRLWE)を"回転"させる準同型演算
    • "回転"とは要はのべき乗をかけるということ
    • べき乗の指数はTLWElvl0によって決まる
  • 入力としてTRLWEとTLWElvl0を1つずつの他に個のTRGSWをとる
    • 入力となるTRLWEは特別にTest Vectorと呼ぶ
    • この個のTRGSWはlvl0の秘密鍵を1bitずつ暗号化したものでBootstrapping Keyと呼ぶ
  • Test Vectorをうまく選ぶことでTLWElvl0からTRLWEへの関数を作れる
    • Sample Extract Indexも合わせればTLWElvl0からTLWElvl1への関数が作れる
    • ∵Blind RotateによってTLWElvl0の値に応じてTRLWEの係数の位置と符号が変化するので、Sample Extract Indexで取り出す値が変わる

TLWEの丸め

  • べき乗の指数は整数でないと困るのでTLWEを丸める必要がある
    • 指数として意味がある範囲は
      • ∵
    • ∴TLWEを倍して各係数をに丸めると意味のある数値がとれそう
  • で元に戻るので、丸めた値はを法とする剰余環上の値とみなせる
  • を使いたいが秘密鍵は漏らせない
    • 床関数なのは、に丸まる値をにするため
    • は計算可能なのでとの積が計算できればは計算可能
      図はの場合の例

Blind Rotateのアイデア

  • 実現したい演算は与えられたTRLWEを倍すること
    • 負符号がついているのはその方が綺麗というだけ
    • のときに次の項が定数次にくる
  • 秘密鍵を教えずにを計算したい
    • TRGSWに秘密鍵を暗号化し(Bootstrapping Key)CMUXで各bitの値を反映

Blind Rotateの具体的アルゴリズム

  • とする(この講義のパラメータでは)
BlindRotaete((𝐚,b),𝐁𝐊,(𝐚[X],b[X]))
  b̃= b >> (32-Nbit-1)) //ここはfloor
  trlwe = X⁻ᵇ̃⋅(𝐚[X],b[X])
  for i from 0 to n-1
    ã=(aᵢ + (1<<(31-Nbit-1)) ) >> (32-Nbit-1) //足し算は四捨五入をするため
    trlwe = CMUX(𝐁𝐊ᵢ,Xᵃ̃⋅trlwe,trlwe)//Dec(𝐁𝐊ᵢ)?Xᵃ̃⋅trlwe:trlwe
  return trlwe

GateBootstrapping TLWE to TLWE(概略)

  • 平文の全ての係数がであるようなTRLWEを入力としたBlind Rotateを行い、その出力の定数項をSample Extract Indexで取り出す操作の名前
    • のとき、のときが定数項に来る
    • これはある種の符号関数(暗号文の復号そのもの)
  • 出力となるTLWElvl1のノイズはTLWElvl0のノイズにかかわらず一定になる
    • ∵TLWElvl1のノイズは回のCMUXによるノイズのみで固定(Bootstrapping)
    • あとはTLWElvl1からTLWElvl0に変換しないといけないが、その方法は次回

自明な暗号文

  • でを、でを取り出せるようなTRLWE(Test Vector)は平文の係数が全てであるような暗号文
    • これを普通に暗号化して送ると平文がわかっている暗号文を送ってしまうことになるし、無駄にノイズも増える
  • 実はを平文のTorus係数多項式そのままとしをとしても有効な暗号文
    • 秘密鍵も乱数生成器もなしで生成できる暗号文なので自明な暗号文と呼ぶ
    • もちろん情報を守ることはできないので使いどころは限られる
  • これを定義する変わりに平文との演算を定義してもよい

GateBootstrapping TLWE to TLWE(疑似コード)

GateBootstrappingTLWEtoTLWE((𝐚,b),𝐁𝐊)
  testvec = (0,0)
  for i from 0 to N-1
    testvec += (0,μXⁱ)
  trlwe = BlindRotate((𝐚,b),𝐁𝐊,testvec)
  return SampleExtractIndex(trlwe,0)

なぜlvl0とlvl1が必要なのか

  • 原理的にはlvl1だけで構成することは可能
  • はBlindRotateでのCMUXの個数なのでこれを減らしたい
    • 計算量的な都合
  • BlindRotateではTorusをに丸める
    • この丸め誤差が個入るがこれは一般に暗号文のノイズに比して大きい
      • 側は更に秘密鍵で増幅される
    • Bootstrappingの誤り確率を抑えるためにを小さくしたい

Blind Rotateで最低限実装するべきもの

  • GateBootstrapping TLWE to TLWE
    • 任意のTRLWEをとるBlind Rotateを実装する必要はない
      • とはいえ特殊化しても知る限り大した性能メリットはない
      • Blind Rotateは工夫のしがいがあるので自由に選べたほうが良い

page_number: true