TFHE実装入門

5.Identity Key Switch

松岡　航太郎

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

Identity Key Switchとは

  • "Key Switch"は一般に暗号文を復号することなしに秘密鍵を変更することを言う
  • ここでの"Identity Key Switch"はTLWElvl1をTLWElvl0に切り替える操作のこと

Identity Key Switchのアイデア

  • ここでは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 Switchの素朴な実装法(スケーリングのみ)

  • 論文とはずれるが、TRGSWと同じ流れで説明をしよう
  • スケーリングが2のべきである必要はないが実装が簡単になるので仮定する
  • basebit∈Z+basebit∈\mathbb{Z}^+はExternal ProductのBgbitBgbitにあたるもの
  • 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 Switchにおける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 //ここでTorusから整数に変わっていると考えていい
  for j from 0 to t-1
    âᵢⱼ= (āᵢ >> (32 - (j+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1)
    (𝐚̃,b̃) -= âᵢⱼ ⋅ KSᵢⱼ
return (𝐚̃,b̃)

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

  • 前のスライドのものでもだめなわけではない
  • 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 Switchの具体的実装(疑似コード)

IdentityKeSwitch((𝐚,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 //ここでTorusから整数に変わっていると考えていい
    for j from 0 to t-1
      k = (āᵢ >> (32 - (j+1)⋅basebit))&(2ᵇᵃˢᵉᵇⁱᵗ - 1) //unicodeだとâᵢⱼを下付きにできないので
      if k != 0
        (𝐚̃,b̃) -= KSᵢⱼₖ
  return (𝐚̃,b̃)

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

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

page_number: true