TFHE実装入門

6.HomNAND

松岡　航太郎

HomNANDとは

  • 復号をせずにNANDを演算することができる
  • 今まで作ってきたものを組み合わせれば作ることができる

Visual Image(Blind Rotateによる写像)

  • Blind Rotateのスライドでも載せた図
    • 1に写したいものを右半面に0に写したいものを左半面に持ってくればいい

Visual Image(ノイズ無しでの加算の全パターン)

  • から入力２つの和を引くと両方が1のときだけ左半面にあることになる
  • 両方が1のときだけ0になるのはまさしくNAND
    • 最初の加減算の符号と定数の値はこうやって決められている
    • 他の２入力の論理ゲートも同じように選ぶことで作ることができる

HomNANDの具体的構成

HomNAND((𝐚₀,b₀),(𝐚₁,b₁),𝐁𝐊,𝐊𝐒)
  tlwelvl0 = (0,μ)-(𝐚₀,b₀)-(𝐚₁,b₁)
  tlwelvl1 = GateBootstrappingTLWEtoTLWE(tlwelvl0,𝐁𝐊)
  return IdentityKeySwitch(tlwelvl1,𝐊𝐒)

他の２入力ゲート

  • 入力の暗号文をとする
  • Blind Rotateに入る暗号文をとする
    • NOTは符号反転するだけ
AND OR XOR

MUXについて

  • 2入力ゲートはすべてHomNANDと同じように作れる
  • 3入力ゲートはMUXだけ工夫によって計算量が減らせる
  • 3つの入力をとする
  • MUXは
  • とのいずれかは必ずゼロ
  • そのため、をトーラスのベクトルの足し算に置き換えられる

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

  • HomNANDそのもの
    • 他のゲートも余力があれば作ると良い
  • 今まで説明してきたものを順番に呼び出すだけでほぼ作れる

page_number: true