TFHE実装入門

9.CKKS

松岡　航太郎

CKKSとは

• 第４世代FHE
• 著者のCheon Jung Hee, Kim Andrey, Kim Miran, Song Yongsooの頭文字
  • ソウル大の人々
  • Song Yongsoo先生は未だにソウル大で論文を出しているので名前を見かける
    • Double Decompositionもこの先生
• 固定小数点演算をサポートする準同型暗号
  • Packingする場合は固定小数点表記の複素数の場合も
• 基本的にはBFVの平文の表現を変更したもの
  • そういう意味では第２世代なきもしている
  • しかし乗算のアルゴリズムがちょっと違う

多項式を平文とするCKKS

• は平文の小数点の位置を決めるパラメータ
• 暗号化は以下の通り

• ほぼBFV
  • ただしがに比べてかなり小さい値を取ることが多い
  • BFVでは上からだけ下がったところにを置く
    • CKKSでは下からだけ上がったところにを置く
      • と下の方のbitがかぶさることも許容される
      • 固定小数点と言う言い回しを使うのはこれが原因
      • approximateと言う単語が使われることもある

平文の位置のイメージ図

CKKSの乗算

• 加算はTFHEと同じなので割愛

• BFVと違ってでわる必要がない
  • を十分小さく取っていれば
    • オーバフローを起こさないので割らなくてもいい
      • で割ってはいけない理由もない気もしないでもないのだが割らないほうが主流という認識
        • 個人的には割ったほうがノイズの増加が遅い気がするのだが......?
• はどんどん大きくなっていくのでも乗算回数に影響を及ぼす
• Relinearlizationも同じ

Rescale

• 高速化とノイズを抑えるために係数の桁を落とすだけの操作
  • ノイズが大きくなってくると下の方の桁を保持する意味がない
  • 桁が小さければ大抵の場合計算も高速
  • 桁の大きさがそのままノイズの増幅率になるのでそれも抑えたい
• 各係数のbitの下から何bitかを丸めて捨てる
  • 大体の場合くらい捨てれば良い

Packing

• CKKSのPackingはFFTをベースにしている
  • 固定小数点が扱えるので, FFTをした結果に値を埋め込むことができる

• この場合は複素数係数として再解釈されるので複素数のベクトルを平文とする暗号文になる
  • 実数としてはしか埋め込めない
  • BFVでの分解の仕方は剰余環に対するものなのでCKKSでは扱いづらい
    • Rescaleで下のbitを破壊するのが非線形な変換をかけてしまう場合がある
    • Rescaleの仕方を工夫すればできる気がする？

Slot2Coeff/Coeff2Slot, Bootstrapping

• BFVではNTTだったのがFFTになっただけなのでSlot2CoeffとCoeff2Slotもだいたい同じ
  • 複素数の計算をしないといけないのでちょっと面倒だったはずだが
• Bootstrappingはほとんど何も知らない......
  • 確かSin関数を評価するのが一番ベーシックだったはずだが
  • CKKSのBootstrappingは実装しようとしたことがない
  • 最近高精度化が進んでいるらしいので持っている知識は多分古い

Residual Number System (RNS)

• BFVと共通の話
• を十分小さく取るにはを十分大きく取らないといけない
  • 数百bitオーダになることも
• を中国剰余定理で複数の素数に分解することで計算を高速化する
  • この方法をRNSと呼ぶ
  • なぜCRTじゃないのかはよくわからない
• RelinealizationのときはExtarnalProductと同様に基数で分解する
  • RNSの表現からの表現に変換してから計算する
  • これが地味に面倒なのでこのコストを下げようとする研究を見た記憶はある

RNSでのRescale

• RNSの場合, 下から何bitか捨てるという操作が定義しづらい
  • 基数表現ではないため
• RNSでのRescaleはを分解した法のうち一つを捨てる
  • での表現に変換して捨てる法をとすると倍して丸めで剰余をとる
• これをするためには大体くらいの大きさの法に分解できるように選ぶ

参考文献

• Introduction to CKKS
• CKKS Deep Dive
• Yongsoo Song先生のスライド