BFV
FHEスキームの一種
主な概念と特徴
リング-LWE問題
リング学習誤差問題は、LWE（Learning With Errors）問題の一般化であり、多項式リング上で定義されます。この問題の難しさは、多項式の係数に小さな誤差を加えた状態で、元の多項式を推測することが困難であることに基づいています。
アルゴリズム
鍵生成(KeyGen)
2つの整数環$ R = Z[X]/(X^{N} + 1) , $ Rq= R/qRを定義する(qは奇素数)
Rqにおける短ベクトルsを選ぶ(秘密鍵)
公開鍵$ pk = (-a*s + e) modqを計算する(aは乱数、eは誤差)
鍵をできるだけ小さなノルムに保つことができる
秘密鍵の係数は -1, 0, +1 から選ばれることが多い。セキュリティ、効率、エラー管理のバランスを取る上で有効なアプローチらしい？
エンコーディングはどうするのか？
暗号化(Encrypt)
メッセージは多項式に変換される
平文mをRqに埋め込む: $ m' = mmodqR
乱数u, f, gを選び、暗号文を計算する: $ c = (c0, c1) = (u*pk + f + m'*q, g)
加算(Add)
2つの暗号文$ (c_0, c_1), (d_0, d_1)に対し、加算は$ (c_0 + d_0, c_1 + d_1)で計算できる
乗算(Mult)
2つの暗号文$ (c_0, c_1), (d_0, d_1)に対し、乗算は以下の手順で行う:
1. $ (c_0d_0, c_0d+1 + c_1d_0, c_1d_1) を計算
2. 2つの係数を1つにまとめる: (c'0, c'1) = (c0d0, c0d1 + c1d0 + \floor(c1d1/q)*q)
復号(Decrypt)
秘密鍵sを用いて$ c'0 - c'1*s modqを計算する
この結果から平文mを復元できる
Relinearization
乗算演算後の再線形化の工程
参考文献