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),𝐊𝐒)
  roundoffset = 1 << (32 - (1 + basebit * t)) //四捨五入のため
  b̄=b
  𝐚̄ = 0⃗
  for i from 0 to t-1
    for j from 0 to kN - 1
      âᵢⱼ = ((aⱼ+roundoffset)>> (32 - (i+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1)
  for i from t-1 to 0
    for j from 0 to kN-1
      if âᵢⱼ ≥ 2ᵇᵃˢᵉᵇⁱᵗ⁻¹
        âᵢⱼ -= 2ᵇᵃˢᵉᵇⁱᵗ
        â₍ᵢ₋₁₎ⱼ += 1
      (𝐚̄,b̄) -= âᵢⱼ ⋅ KSᵢⱼ
  return (𝐚̄,b̄)

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

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

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

IdentityKeySwitching((𝐚,b),𝐊𝐒)
  roundoffset = 1 << (32 - (1 + basebit * t)) //四捨五入のため
  b̄=b
  𝐚̄ = 0⃗
  for i from 0 to t-1
    for j from 0 to kN - 1
      âᵢⱼ = ((aⱼ+roundoffset)>> (32 - (i+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1)
  for i from t-1 to 0
    for j from 0 to kN-1
      if âᵢⱼ ≥ 2ᵇᵃˢᵉᵇⁱᵗ⁻¹
        âᵢⱼ -= 2ᵇᵃˢᵉᵇⁱᵗ
        â₍ᵢ₋₁₎ⱼ += 1
      k = abs(âᵢⱼ)
      if âᵢⱼ > 0
        (𝐚̄,b̄) -= KSᵢⱼₖ
      else if âᵢⱼ < 0
        (𝐚̄,b̄) += KSᵢⱼₖ
  return (𝐚̄,b̄)

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

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

IKSに適用可能なoptimization

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

page_number: true