TFHE実装入門

5.Identity Key Switching

松岡　航太郎

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

Identity Key Switchingとは

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

Identity Key Switchingのアイデア

  • ここではTLWElvl1の鍵をS\mathbf{S}と書く(s[X]s[X]の係数のベクトル)
  • TLWElvl1のb−a⋅Sb-\mathbf{a}⋅ \mathbf{S}をTLWEWlvl0を使って暗号上で計算する
  • つまり(a~,b~)(\mathbf{ã},b̃)を出力となるTLWElvl0として以下を満たすようにする
    b~−a~⋅s≈b−a⋅Sb̃-\mathbf{ã}⋅\mathbf{s} ≈ b-\mathbf{a}⋅ \mathbf{S}
    • これはTLWElvl0と平文がノイズを除いて一致するようにするということ

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

  • 論文とはずれるが、TRGSWと同じ流れで説明をしよう
    • 実のところnnが2のべきならExternalProductとSampleExtractIndexでもできる
      • パラメータ選定の自由度が著しく下がる(BFVやCKKSでは使う)
  • basebit∈Z+basebit∈\mathbb{Z}^+はExternal ProductのBgbitBgbitにあたるもの
    • スケーリングが2のべきである必要はないがここでも簡単のため仮定する
  • KS\mathbf{KS}をKSijKS_{ij}がSij2basebit\frac{S_{ij}}{2^{basebit}}を平文とするTLWElvl0であるとする
    • iiがベクトルの次元、jjが多項式の係数側
      (a~,b~)=(0,b)−∑i=0N−1⌈2basebit⋅ai⌋⋅KSi(\mathbf{ã},b̃) = (\mathbf{0},b)-∑^{N-1}_{i=0}⌈2^{basebit}⋅a_i⌋⋅KS_i
    • これでb−a⋅Sb-\mathbf{a}⋅ \mathbf{S}を準同型的に演算できるが、ノイズが大きすぎる

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

  • TRGSWと同じように、スケーリングだけだとだめなのでDecompositionもする
    • 桁数をttとする(llに相当する)
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と違ってスカラー整数との積なので取れる値が限られている
  • KS\mathbf{KS}をKSijoKS_{ijo}がo⋅Si2(j+1)basebit\frac{o⋅S_i}{2^{(j+1)basebit}}を平文とするTLWElvl0と定義し直す(o∈[1,2basebit−1]o ∈ [1,2^{basebit} - 1])
    • KS\mathbf{KS}のデータサイズは2basebit−12^{basebit}-1倍になる
    • 乗算がなくなるってノイズの増加が抑えられるのでそれとのトレードオフ
  • o=0o=0の場合に関しては足す必要がないので保持しなくていい

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 k != 0
          (𝐚̃,b̃) -= KSᵢⱼₘₒ
  return (𝐚̃,b̃)

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

  • t=5,basebit=2t = 5,basebit = 2
  • Identity Key Switchingはここで説明したものが最低限

page_number: true