RustでFHEの一種であるCKKS暗号を作るので、そのメモ書きをする。筆者の格子の理解がよわよわなので、おかしいところや疑問点があったら投稿よろしくお願いします！

基本的に参考サイト欄のサイトを参考にするが、ちょっとつまずいた点等をまとめる。

なぜRustか

SEALやPALISADEなどFHEのC++実装は多く有るが、Rustでの実装は見かけないため。また、wasmとFHEを組み合わせてみたいため。

使うクレート(現在)

rust-ndarray
rusr-ndarray-linalg

リポジトリ

https://github.com/senk8/RustCKKS

参考サイト

CKKS暗号の原論文

https://eprint.iacr.org/2016/421.pdf

Senk 2021/02/03に更新

現在までの進捗

Part1を参考にencodeとdecodeを実装した。src/ckks/encoder.rsに実装がある。

src/main.rs

    const E: f64 = 1e-10;
    #[test]
    fn test_encode_and_decode() {
        use ndarray_linalg::Norm;
        let encoder = CKKSEncoder::new(8);
        let x = array![c64::new(1f64,0f64),c64::new(2f64,0f64),c64::new(3f64,0f64),c64::new(4f64,0f64)];

        let ptxt = encoder.encode(x.clone());
        let xd = encoder.decode(ptxt);

        let diff = x - xd;
        assert!(diff.norm_l2() < E);
    }

のテストが通ることから、encodeとdecodeに成功していることが分かる。また、このencodeが同型写像になっていることは

src/main.rs

    #[test]
    fn test_multiplicative_homomorphic() {
        let encoder = CKKSEncoder::new(8);
        let x = array![c64::new(1f64,0f64),c64::new(2f64,0f64),c64::new(3f64,0f64),c64::new(4f64,0f64)];
        let y = array![c64::new(1f64,0f64),c64::new(2f64,0f64),c64::new(3f64,0f64),c64::new(4f64,0f64)];

        let ptxt1 = encoder.encode(x.clone());
        let ptxt2 = encoder.encode(y.clone());

        let xy = x * y;
        let ptxt12 = ptxt1 * ptxt2;

        let diff = xy - encoder.decode(ptxt12);
        assert!(diff.norm_l2() < E);
    }

のテストが通ることから確認できる。encode関数の終域の元は多項式になるので、encode結果を乗算する場合は内積ではなく畳み込み積で計算する。ここは現在実装の簡易化のために、ただの畳込み積にしているが将来的には高速フーリエ変換にしたい。あと複素ベクトル生成のマクロ化は必要そう。

Senk 2021/02/04に更新

参考資料のPART２について

根Xの複素共役もまた多項式の根になっていることから、

m(X)=m(\bar{X})

となっているはず。これにより、Xとその共役は $m(X)\in R$ において０になっているはず。
結局、半分の根は $R$ 上では同じになるので $σ(R)$ の濃度は $N$ ではなく $N/2$ になる（とみなせる）。

ここで、そのまま $z\in C^{N/2}$ に適用するには、サイズ $N/2$ だから足りないので共役をコピーして $C^N$ ベクトルにする。（たぶん、ここの解釈は深める必要がありそう）

ソースコードでは、リストのN番目までを持ってきて反転してくっつけてる。piとpi_inverseがやってることは

ls=[w1,w3,w5,w7]#w1とw7、w3とw5は複素共役

# ここからpiでやってること　σ(R)->C^N/2
res1=ls[:2]#res1=[w1,w3]

# ここからpi_inverseでやってること　C^N/2->σ(R)
res2=res1[::-1]#res2=[w3,w1]
res3=[np.conjugate(x) for x in res2]#res3=[w7,w5]

print(res1+res3)# [w1,w3,w7,w5]

ということになる。

Senk 2021/02/04に更新

PART2の続き

create_sigma_R_basisは多項式を格子点とみなしたときの格子基底を生成している。以下のようなヴァンデルモンド行列は一列一列がk-1次多項式(格子)とみなせる。

\left( \begin{array}{ccccc} 1 & x_1 & x_1^2 & \dots & x_1^{k-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{k-1} \\ 1 & x_3 & x_3^2 & \dots & x_3^{k-1} \\ \vdots　& \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{k-1} \\ \end{array} \right)

列が多項式、つまり格子点を表すので、結局、このヴァンデルモンド行列は行が格子を生成する基底というようにみなせる。なので、create_sigma_R_basisで内でヴァンデルモンド行列を生成したら、basisとしてみなすために転置を行う。これによりbasis[0]=[1,x,x^1,\dots,x^k-1]ではなく、basis[0]=[1,1,\dots,1]になる。

encoder.rs

let basis = CKKSEncoder::vandermonde(m, unity).t().to_owned()// unityは１の冪根です

座標wから格子を生成したい場合は、

let lattice=encoder.basis.t().dot(&w);

というように、転置してから内積を取る。

Senk 2021/02/10

PART2の続き

ここまでのencodeは複素ベクトル $C^N$ から $R=C[X]/X^n1$ への写像になっていた。しかし、CKKSでは整数係数多項式環を使う関係で係数を整数に変換して扱わないといけない。そのためにcoordinate-wise-roundingというものを使う。

手順としてはこう

複素ベクトル $z\in C^{N/2}$ をHにマッピングする。これを $\pi^-1(z)$ とする。
$\pi^{-1}(z)\in H$ を $\sigma(R)\subseteq H$ である $\sigma(R)$ に含まれるようにしたいので、coordinate-wise-roundingで $\sigma(R)$ に含まれるようにする。
$\sigma(R)$ に $\sigma$ の逆像を適用すると $R$ にマッピングされる。