突貫で書いてしまった部分もあるので、大いに誤りを含む可能性があります。誤字・脱字レベルでも構いませんので、ご指摘ください。
また、予告なしに内容の加筆や構成の変更を行うことがありますが、読みやすくするためのものですので、ご容赦ください
自己紹介
秘密計算のスタートアップで働いている社会人３年目です
普段は、秘密計算の研究や社会実装を行なっています
最近は、外部に向けた勉強会もやっています
第1回 EAGLYS暗号勉強会
第2回 EAGLYS暗号勉強会
第3回 EAGLYS暗号勉強会
第4回 EAGLYS暗号勉強会
学生時代は、耐量子計算機暗号（特に符号ベース暗号）を研究していました
今でも細々と続けています
Qiita だけでなく、X や Zenn でも活動しています、もしよろしければ
X のアカウント
Zenn のアカウント
前回の内容
準同型暗号 CKKS 方式の理論と実装 基本編（0. イントロダクション）
前回は、
- 本連載記事の構成（セクションと特定のサブセクションから構成される）
- 各セクションの読み方（全ての方に全てのトピックを読んでいただくことは想定していない）
- 本連載記事の目次
- CKKS 方式の概要
について触れました
今回から、いよいよ本題に入っていきます
今回の関連アウトプット
数学の準備
ここに記載の定義は、間違ったことは書いていないものの、厳密性を欠く場合が多いです
都度補足はしますが、詳細は、代数学などの教科書を紐解いてみてください
整数環
まずは環の定義と、その具体例として整数環を紹介します
定義1と定義2は、基盤になる概念で、例3で、環の具体例として整数環を導入しています
＊定義1と定義2は、こう書いていますが、正直とばしてもOKです
群や環といった代数構造は、どのような集合か？その集合にどのような演算が定まっているのか？の2点を意識する（っていうかそれが定義）と良いです
例3で、さらっと「$\mathbb{Z}$ は環になる」と書いていますが、これの証明をしたことない方はやってみましょう（定義2で書いた6つの条件を満たすかを確認するだけです）
以降では、整数環をベースとして考えていきます
続いて、整数環の剰余環の定義とその具体例を確認していきましょう
定義4が整数環の定義で、注意5で整数環と整数環の剰余環の違いについて説明し、例6で整数環の剰余環の具体例を紹介しています
＊剰余類が〜とか well-defined が〜とかは、割愛するため、この辺りが気になる方は、代数学の教科書を読んでみてください
計算機科学的な視点による、剰余環を考える意義を紹介します
計算機にはリソースが限られているため、「無限に大きい」数は扱えません
そこで、剰余環を考えて、整数の「大きさ」に制約を持たせることで、計算機上で扱えるようにします
多項式環
定義7で多項式、定義8で一変数多項式環（以降、多項式環）の定義をそれぞれ紹介しています
ここでは、あえて、一般の環 $R$ による定義を導入しています
多項式環における積では、多項式の長さ（次数）が大きくなることに注意しましょう
円分多項式
定義9で、円分多項式を導入し、以降では、この多項式をメインとします（これは、次数が $2 n$ 次の場合に限った定義なので、一般性は欠きます）
定義10では、多項式環の剰余環を定義しています
注意11・注意12では、一見すると、定義10の積で何をやっているのか分かりづらい部分を、補足的に説明しています
多項式環の剰余環を考えるモチベーションは、整数環の剰余環を考えるのと同じで、計算機には有限のリソースしかないから、というのが1つの理由です
注意11・注意12を見てもよくわからない方は、次の具体例を手を動かして考えてみましょう:
例13・注意14では、例15を考える上でのセッティングです
例15で、具体的な計算をしています
例15では、注意11の関係を使って直接計算していますが、これが何をやっているのかわからない方は、まず、「普通に」展開してみましょう
すると、4, 5, 6 次の多項式が出てくるはずです
それらの項に対して、便宜的に $x^4 = - 1$ として、計算してみると答えが一致するはずですし、$c_0^{\prime \prime}, c_1^{\prime \prime}, c_2^{\prime \prime}$ のマイナスの項の意味も分かると思います
Coeff 方式 encode/decode
概要
まず初めに、CKKS における cleartext, plaintext, ciphertext の関連性を示します。
＊CKKS explained: Part 1, Vanilla Encoding and Decoding より引用
CKKS におけるそれぞれの text がどのような type になっているかを確認します:
- cleartext: 長さが $N/2$ の複素数のベクトル
- plaintext: 長さが $N$ の整数係数多項式
- ciphertext: 長さが $N$ の整数係数多項式の組
cleartext では長さが $N / 2$ なのに、plaintext, ciphertext では長さが $N$ になっていたりとか、
plaintext では、多項式1つなのに、ciphertext では、2つになっていたりとか、
色々と疑問に思うところはあるかもしれませんが、それは、今後明らかになっていきます
今回の記事では encode に注目するので、複素ベクトルから整数係数多項式にどうやって変換するのか？を考えればOKです
Coeff Encode
実は、CKKS の Encode には、代表的なアルゴリズムが2つあり、今回扱うのは Coeff Encode と呼ばれるものになります
＊もう1つは、第4回で、Slot Encode というものを扱います
先ほど「複素ベクトルから整数係数多項式にどうやって変換するのか？」と書きましたが、難しそう・・・と思うかもしれません
が、Coeff Encode を図に起こすと、下記のようになります:
$N = 4$ の場合の図で、長さ2の複素ベクトル（cleartext）から、長さ4の整数係数多項式へと移しています
cleartext の情報が、そのまま多項式の係数に埋め込まれている、この背景から Coeff（Coefficient, 係数）Encode と呼ばれます
前提
後で出てくる記号を整理します
$\mathbb{C}$ を複素数全体の集合を表し、$N$ を2べき（1, 2, 4, 8, 16, 32, ...）とします
理論的枠組み
Encode では
長さが $N / 2$ の複素ベクトル $z = (z_0, z_1, \ldots, z_{N / 2 - 1})$ が与えられ、長さが $N$ の整数係数多項式 $m = m_0 + m_1 X + \cdots + m_{N - 1} X^{N - 1}$ を返す
ことが目標です
Decode は、上記の逆操作を行います
Encode
Step1: 複素ベクトルの各複素数を実数成分に分解する
$0 \leq i \leq N / 2 - 1$ に対して、$z_i = a_i + b_i \sqrt{-1}$ と分解します
Step2: スケーリング係数を掛けて、四捨五入をする
Step1 より、$0 \leq i \leq N / 2 - 1$ に対して、$a_i^{\prime} = \lfloor a_i \cdot \mathrm{scale} \rceil, \ b_i^{\prime} = \lfloor b_i \cdot \mathrm{scale} \rceil$ を計算します
あとは、これらをまとめれば良いです
Decode
Step1: 多項式の各係数をスケーリング係数で割る
plaintext $m = m_0 + m_1 X + \cdots + m_{N - 1} X^{N - 1}$ に対して、全ての係数を $\mathrm{scale}$ で割ります
Step2: 多項式の係数である実数の組を複素数へ戻す
$0 \leq i \leq N / 2 - 1$ に対して、$m_{2 i} + m_{2 i + 1} \sqrt{-1}$ なる変換を考えます
具体例
せっかくなので、「概要」で用いた例で確認してみましょう
Encode
cleartext として $[3 + 4 \sqrt{-1}, \ 2 - \sqrt{-1}]$ が与えられたとします
また、scale $= 2^6$ とします
Step1: 複素ベクトルの各複素数を実数成分に分解する
各複素数に対して、実数成分に分解します
$3 + 4 \sqrt{-1}$ という複素数を $(3, 4)$ という実数の組に移し、
$2 - \sqrt{-1}$ という複素数を $(2, -1)$ という実数の組に移しましょう
Step2: スケーリング係数を掛けて、四捨五入をする
Step1 で $(3, 4), (2, -1)$ という組（の組）が得られました
それぞれに対して、scale $= 2^6$ をかけることで、$(192, 256), (128, -64)$ という組が出てきます
今回は全て整数なので、四捨五入の操作は飛ばします
あとは、これらを多項式の係数と見て $192 + 256 X + 128 X^2 - 64 X^3$ となります
Decode
plaintext として $192 + 256 X + 128 X^2 - 64 X^3$ が与えられたとします
また、scale $= 2^6$ とします
Step1: 多項式の各係数をスケーリング係数で割る
plaintext の各係数を scale $= 2^6$ で割ると、$3 + 4 X + 2 X^2 - X^3$ となります
Step2: 多項式の係数である実数の組を複素数へ戻す
多項式の係数を2個ずつの塊で見ていき、$3 + 4 \sqrt{-1}, 2 - \sqrt{-1}$ となります
まとめ
cleartext に対して、Encode→Decode の順で操作を行うと、値が元に戻ってくることを確認しました
今回の記事「Coeff 方式 encode/decode」の概要で
cleartext では長さが $N / 2$ なのに、plaintext, ciphertext では長さが $N$ になっていたり
と書きましたが、複素数を実数の組とみなす操作があるため、長さが倍になる、ということです
アルゴリズム
「理論的枠組み」のstepをまとめます
アルゴリズムの計算量としては、どちらも複素ベクトルの長さにしか依存しないため、非常に速いと判断できます
Encode
Decode
実装
numpy には、Polynomial モジュールがあるため、今回の実装ではこれを使います
from numpy.polynomial import Polynomial
Encode
def coeff_encode(
z: list,
scale: int,
) -> Polynomial:
"""Converts a complex vector into a integer coefficient polynomial."""
coef = []
for z_i in z:
# Step1
scaled_zi = scale * z_i
# Step2
coef.append(np.round(np.real(scaled_zi)).astype(int))
coef.append(np.round(np.imag(scaled_zi)).astype(int))
return Polynomial(coef)
Decode
def coeff_decode(
p: Polynomial,
scale: int,
) -> np.array:
"""Converts a integer coefficient polynomial into a complex vector."""
"""Inverse operation of coeff_encode"""
rescaled_p = []
for i in range(len(p.coef) // 2):
# Step1 and Step2
rescaled_p.append(p.coef[2 * i] / scale + 1j * (p.coef[2 * i + 1]) / scale)
return rescaled_p
具体例チェック
「具体例」で手計算したものをテストケースとして、上記の実装を確認してみましょう
# メッセージを入力する
cleartext1 = [3 + 4j, 2 - 1j]
print("メッセージ1:", cleartext1)
cleartext2 = [5 - 2j, 3 + 4j]
print("メッセージ2:", cleartext2)
print()
# plaintext を生成する
plaintext1 = coeff_encode(cleartext1, scale)
print("plaintext1:", plaintext1)
plaintext2 = coeff_encode(cleartext2, scale)
print("plaintext2:", plaintext2)
print()
# plaintext を decode する
decoded_plaintext1 = coeff_decode(plaintext1, scale)
print("plaintext1 の decode 結果: ", decoded_plaintext1)
decoded_plaintext2 = coeff_decode(plaintext2, scale)
print("plaintext2 の decode 結果: ", decoded_plaintext2)
上記を実行すると
メッセージ1: [(3+4j), (2-1j)]
メッセージ2: [(5-2j), (3+4j)]
plaintext1: 192.0 + 256.0·x + 128.0·x² - 64.0·x³
plaintext2: 320.0 - 128.0·x + 192.0·x² + 256.0·x³
plaintext1 の decode 結果: [(3+4j), (2-1j)]
plaintext2 の decode 結果: [(5-2j), (3+4j)]
のようになり、確かに、cleartext に対して、Encode→Decode をすると、値が元に戻ってきています
理論詳細
今回書くことではないのですが、
- Coeff_Encode によって、複素数を無理に実数へ落としているため、複素数の構造の情報が失われているように見えるが、それは良いのか？
- Coeff_Encode では、実質、ベクトル（配列）を多項式と見ていて、両者の構造が異なるが、それは良いのか？
と思われた方もいらっしゃるかもしれませんが、その辺りの詳細は第4回で回収します（結論としては、どちらもNG）
なぜ cleartext の定義域が複素数なのか
＊あくまで一解釈です
CKKS の前に提案されたイデアル格子暗号方式において、すでに、円分整数などの概念があったことから、それに紐づけて、cleartext の定義域が複素数、という説明はもちろんできます
ここでは、cleartext の定義域が複素数だと嬉しい点をメインに解説することにします
＊とは言いつつも、数学的にはかなり大雑把な説明になるので、気になる方は、複素関数の教科書を見てみると良いかもです
一般に、複素関数は、1回でも任意の点で微分可能であれば、任意の回数だけ微分可能であることが知られています（正則関数、とかでググってみてください）
そして、任意の回数だけ微分可能であるため、冪級数展開が可能になります
冪級数展開ができる、ということは、例えば、0の周りでは
$f(z) = f(0) + f^{\prime}(0) z + \frac{1}{2!} f^{\prime \prime}(0) z^2 + \cdots + \frac{1}{n!} f^{(n)}(0) z^n + \cdots +$
という表示が可能になります
- 微分係数を用いたスカラー倍
- $z$ の冪乗
- これらの足し算
ができれば、右辺を適当なタイミングで打ち切ることで $f(z)$ を近似できることに注意しましょう
例えば、$f(z)$ を $f(0) + f^{\prime}(0) z + \frac{1}{2!} f^{\prime \prime}(0) z^2 + + \frac{1}{3!} f^{(3)}(0) z^3$ でそれなりに近似できる場合を考えます
このとき、$z$ の係数に相当する部分（微分係数とか階乗で割ってる部分）は、事前に計算できるので、$z^2, z^3$ および $z$ に関する足し算さえできれば、$f(z)$ を計算できたことになります
そして、これは複素平面上で成り立つだけでなく、$z$ を暗号文と見た際の暗号文空間でも同様の事実が成り立ちますね
つまり、連続関数 $f$ に対して、$f(z)$ を直接計算する代わりに、$f(0) + f^{\prime}(0) z + \frac{1}{2!} f^{\prime \prime}(0) z^2 + + \frac{1}{3!} f^{(3)}(0) z^3$ を計算することを考えるわけです
裏を返すと、複素平面上で、任意の点で1階微分可能でなければ、上記のようなことはできません
有名どころだと、絶対値関数とか、ニューラルネットでよく使う ReLU 関数とかですかね
このような関数に対して、適当な連続関数で近似してから、上記のような Taylor 展開の表示を使って計算することが多いです
この辺りの詳細は第6回で説明します
スケーリング係数の役割
結論から書くと、cleartext と coeff_decode(coeff_encode(cleartext)) との誤差を小さくするための役割を持ちます
実験してみる
今までの具体例では、cleartext として、整数を取っていたので、恩恵は少ないのですが、例えば、
scale = 64
# メッセージを入力する
cleartext = [3.14 + 4.0233j, 2.621 - 1.002j]
print("メッセージ:", cleartext)
print()
# plaintext を生成する
plaintext = coeff_encode(cleartext, scale)
# plaintext を decode する
decoded_plaintext = coeff_decode(plaintext, scale)
print("plaintext の decode 結果: ", decoded_plaintext)
の場合だと、
メッセージ: [(3.14+4.0233j), (2.621-1.002j)]
plaintext の decode 結果: [(3.140625+4.015625j), (2.625-1j)]
のように出力され、小数点第2位までしか一致していないなぁと思うわけです
そこで、
scale = 2**20
# メッセージを入力する
cleartext = [3.14 + 4.0233j, 2.621 - 1.002j]
print("メッセージ:", cleartext)
print()
# plaintext を生成する
plaintext = coeff_encode(cleartext, scale)
# plaintext を decode する
decoded_plaintext = coeff_decode(plaintext, scale)
print("plaintext の decode 結果: ", decoded_plaintext)
というように、cleartext の値はそのままに、scale の値のみを大きくします
すると、
メッセージ: [(3.14+4.0233j), (2.621-1.002j)]
plaintext の decode 結果: [(3.140000343322754+4.0233001708984375j), (2.621000289916992-1.001999855041504j)]
のように、かなりの精度で一致することがわかります
なぜ scale の値を増やすと、精度が良くなるのか
上記の実験結果を簡単に説明します
＊納得いかない方は、scale の値を $2^1$ から $2^{20}$ まで試してみると、なんとなく言わんとすることが分かるはずです
簡単のため、scale を $2^n$ とします
このとき、$2^n$ を掛ける、という操作は、n bit 左へシフトさせることに相当します（2倍することと 1 bit 左にシフトさせることは同じ）
一方、四捨五入を取る、という操作は、その時点の実数において、整数部分の情報のみを取り出すことを意味します
よって、$2^n$ を掛けてから四捨五入をとる、というのは、元の実数の小数点 $n$ 桁までの情報を取り出すことに相当します
このような背景があるので、scale の値が大きいほど、encode→decode の誤差が小さくなります
まとめ
振り返ってみると、ある程度は暗号の知識とかがある人向けになってしまった・・・
ですが、理論と実装をバランスよく書けたかなと思います
個人的な感覚として、CKKS は、TFHE と比べて、背景となる数学を知っていたら、すんなり理解できるものが多いです（逆に、知らないと厳しいものが多い）
必要な数学は、必要になったら、必要な分だけ解説するスタイルで進めますので、知らないトピックは、都度調べていただけたらと思います
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！