TFHE実装入門

5.Identity Key Switching

松岡　航太郎

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

Identity Key Switchingとは

• "Key Switching"は一般に暗号文を復号せずに秘密鍵を変更することを言う
  • 一般には秘密鍵の変更と同時にリプシッツ連続な関数を適用する
    • まぁ大体は線形な関数のこと
• ここでの"Identity Key Switching"はTLWElvl1をTLWElvl0に切り替える操作のこと
  • lvl1とlvl0は鍵が違う
  • 恒等関数を適用するので"Identity"

Identity Key Switchingのアイデア

• ここではTLWElvl1の鍵をと書く(の係数のベクトル)
• TLWElvl1のをTLWEWlvl0を使って暗号上で計算する
• つまりを出力となるTLWElvl0として以下を満たすようにする
  
  • これはTLWElvl0と平文がノイズを除いて一致するようにするということ

Identity Key Switchingの素朴な実装法(スケーリングのみ)

• 論文とはずれるが、TRGSWと同じ流れで説明をしよう
  • 実のところが2のべきならExternalProductとSampleExtractIndexでもできる
    • パラメータ選定の自由度が著しく下がる(BFVやCKKSでは使う)
  • TRGSWではなくTGSWを使ってると考えるならExtarnal Productそのもの
• はExternal Productのにあたるもの
  • スケーリングが2のべきである必要はないがここでも簡単のため仮定する
• をがを平文とするTLWElvl0であるとする
  • がベクトルの次元、が多項式の係数側
    
  • これでを準同型的に演算できるが、ノイズが大きすぎる

Identity Key SwitchingにおけるDecomposition的基数展開

• TRGSWと同じように、スケーリングだけだとだめなのでDecompositionもする
  • 桁数をとする(に相当する)

IdentityKeySwitching((𝐚,b),𝐊𝐒)
  b̃=b
  for i from 0 to n
    ãᵢ = 0
  prec_offset = 1 << (32 - (1 + basebit * t)) //四捨五入のため
  for i from 0 to k-1
    for j from 0 to N-1
      āᵢⱼ = aᵢⱼ+prec_offset //四捨五入
      for m from 0 to t-1
        âᵢⱼₘ= (āᵢⱼ >> (32 - (m+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1)
        (𝐚̃,b̃) -= âᵢⱼₘ ⋅ KSᵢⱼₘ
  return (𝐚̃,b̃)

Identity Key Switchingの具体的実装(乗算を要素選択に置換)

• 前のスライドのものでもだめなわけではない
  • External Productと違ってスカラー整数との積なので取れる値が限られている
• をがを平文とするTLWElvl0と定義し直す()
  • のデータサイズは倍になる
  • 乗算がなくなってノイズの増加が抑えられるのでそれとのトレードオフ
• の場合に関しては足す必要がないので保持しなくていい

Identity Key Switchingの具体的実装(疑似コード)

IdentityKeSwitching((𝐚,b),𝐊𝐒)
  b̃=b
  for i from 0 to n
    ãᵢ = 0
  prec_offset = 1 << (32 - (1 + basebit * t)) //四捨五入のため
  for i from 0 to k-1
    for j from 0 to N-1
      āᵢⱼ = aᵢⱼ+prec_offset //四捨五入
      for m from 0 to t-1
        o = (āᵢⱼ >> (32 - (m+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1) //unicodeだとâᵢⱼₘを下付きにできないので
        if o != 0
          (𝐚̃,b̃) -= KSᵢⱼₘₒ
  return (𝐚̃,b̃)

Identtity Key Switchingのパラメータと最低限実装するべきもの

• Identity Key Switchingはここで説明したものが最低限

IKSに適用可能なoptimization

• lvl1の鍵の一部をlvl0の鍵にすると計算が簡単になる
  • なのでの次までの係数をlvl0の鍵にする
  • 差分だけIKSで計算すれば良くなる
• この方式は攻撃法が見つかっていないだけで安全かは不明