TFHE実装入門

6.HomNAND

松岡　航太郎

HomNANDとは

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

width:1200px

Visual Image(Blind Rotateによる写像)

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

w:500px

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

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

HomNANDの具体的構成

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

他の２入力ゲート

  • 入力の暗号文をca,cbca,cbとする
  • Blind Rotateに入る暗号文をscale⋅(ca+cb)+offsetscale⋅(ca+cb)+offsetとする
    • NOTは符号反転するだけ
AND OR XOR
scalescale 11 11 22
offsetoffset −18-\frac{1}{8} 18\frac{1}{8} 14\frac{1}{4}

MUXについて

  • 2入力ゲートはすべてHomNANDと同じように作れる
  • 3入力ゲートはMUXだけ工夫によって計算量が減らせる
  • 3つの入力をs,d1,d0s,d1,d0とする
  • MUXは(d1∧s)∨(d0∧¬s)(d1∧s)∨(d0∧\lnot s)
  • (d1∧s)(d1∧s)と(d0∧¬s)(d0∧\lnot s)のいずれかは必ずゼロ
  • そのため、∨∨をトーラスのベクトルの足し算に置き換えられる
    • (d1∧s)+(d2∧¬s)+(0,18)(d1∧s)+(d2∧\lnot s)+(\mathbf{0},\frac{1}{8})

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

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

page_number: true