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でもできる
      • パラメータ選定の自由度が著しく下がる
  • basebit∈Z+basebit∈\mathbb{Z}^+はExternal ProductのBgbitBgbitにあたるもの
    • スケーリングが2のべきである必要はないがここでも簡単のため仮定する
  • KS\mathbf{KS}をKSiKS_iがSi2basebit\frac{S_i}{2^{basebit}}を平文とするTLWElvl0であるとする
    (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に相当する)
b̃=b
for i from 0 to n
  ãᵢ = 0
prec_offset = 1 << (32 - (1 + basebit * t)) //四捨五入のため
for i from 0 to N-1
  āᵢ = aᵢ+prec_offset //四捨五入
  for j from 0 to t-1
    âᵢⱼ= (āᵢ >> (32 - (j+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1)
    (𝐚̃,b̃) -= âᵢⱼ ⋅ KSᵢⱼ
return (𝐚̃,b̃)

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

  • 前のスライドのものでもだめなわけではない
    • External Productと違ってスカラー整数との積なので取れる値が限られている
  • KS\mathbf{KS}をKSijkKS_{ijk}がk⋅Si2(j+1)basebit\frac{k⋅S_i}{2^{(j+1)basebit}}を平文とするTLWElvl0と定義し直す(k∈[1,2basebit−1]k ∈ [1,2^{basebit} - 1])
    • こうしてもKS\mathbf{KS}のデータサイズは2basebit−12^{basebit}-1倍にしかならない
    • 乗算がなくなるのでノイズの増加が抑えられる
  • k=0k=0の場合に関しては足す必要がないので保持しなくていい

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

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

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

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

page_number: true