最終回です．前回定義した暗号方式が足し算・掛け算で閉じていることを確認します．
全３回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 1の3乗根
- 3分整数
- p分整数
- m分整数
- イデアル
- 衝突困難関数とSVP
第1.5回
- 記号の整理
- 衝突困難関数の構成
- 衝突困難関数の簡単な例
- 構成の証明の方針
- 構成の正当性の証明
第２回
- 記号の整理
- 準同型暗号とは
- Ring-LWE問題
- Ring-LWE問題の具体例
- Ring-LWE問題を使った準同型暗号
- Ring-LWE問題を使った準同型暗号の具体例
第３回
- 暗号文同士の足し算
- 暗号文同士の足し算の具体例
- 暗号文同士の掛け算
- 暗号文同士の掛け算の修正版
- 暗号文同士の掛け算の具体例
今回は第３回です．
具体的な内容としては，次のようになります:
- 暗号文同士の足し算
- 暗号文同士の足し算の具体例
- 暗号文同士の掛け算
- スイッチ鍵
- 暗号文同士の掛け算の修正版
- 暗号文同士の掛け算のアルゴリズム
- アルゴリズムのまとめ
暗号文同士の足し算
\underline{\mathrm{Def(暗号文同士の足し算)}}
公開鍵 pk を固定して，平文 p に対して，Encrypt(pk) を実行して得られる暗号文を c = (c_0, c_1) とする．同様に平文 p^{\prime} の暗号文を c^{\prime} = (c_0^{\prime}, c_1^{\prime}) とする．
このとき，d = (c_0 + c_0^{\prime}, c_1 + c_1^{\prime}) を復号すると，p + p^{\prime} に対応する．
なぜそうなるかというと，第２回「Ring-LWE問題を使った準同型暗号」 を思い返すと，c_0 - s c_1 を \mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] で考えると，p に一致するのでした．また，c_0^{\prime} - s c_1^{\prime} を \mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] で考えると，p^{\prime} に一致します．
よって，(c_0 + c_0^{\prime}) - s(c_1 + c_1^{\prime}) を \mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] で考えると，p + p^{\prime} に一致するかどうかを確認すればOKです．
\begin{align*}
c_0 & = b v + 2 e_0 + p + c_{0 q neg}, c_1 = a v + 2 e_1 + c_{1 q neg}, \\
c_0^{\prime} & = b v^{\prime} + 2 e_0^{\prime} + p^{\prime} + c_{0 q neg}^{\prime}, c_1 = a v^{\prime} + 2 e_1^{\prime} + c_{1 q neg}^{\prime}
\end{align*}
とします（公開鍵は固定されているので，a, b の値は共通です）．ただし，ある c_{0, 0}, c_{0, 1}, \cdots, c_{0, n - 1}, c_{1, 0}, c_{1, 1}, \cdots, c_{1, n - 1}, c_{0, 0}^{\prime}, c_{0, 1}^{\prime}, \cdots, c_{0, n - 1}^{\prime}, c_{1, 0}^{\prime}, c_{1, 1}^{\prime}, \cdots, c_{1, n - 1}^{\prime} \in \mathbb{Z}^{(q)} を使って，
c_{0 q neg} = q c_{0, n - 1} \zeta_m^{n - 1} + \cdots + q c_{0, 1} \zeta_m + q c_{0, 0}
c_{1 q neg} = q c_{1, n - 1} \zeta_m^{n - 1} + \cdots + q c_{1, 1} \zeta_m + q c_{1, 0}
c_{0 q neg}^{\prime} = q c_{0, n - 1}^{\prime} \zeta_m^{n - 1} + \cdots + q c_{0, 1}^{\prime} \zeta_m + q c_{0, 0}^{\prime}
c_{1 q neg}^{\prime} = q c_{1, n - 1}^{\prime} \zeta_m^{n - 1} + \cdots + q c_{1, 1}^{\prime} \zeta_m + q c_{1, 0}^{\prime}
としています．
\begin{align*}
\displaystyle
(c_0 + c_0^{\prime}) - s(c_1 + c_1^{\prime})
& = \left( (b v + 2 e_0 + p + c_{0 q neg}) + (b v^{\prime} + 2 e_0^{\prime} + p^{\prime} + c_{0 q neg}^{\prime}) \right) - s \left( (a v + 2 e_1 + c_{1 q neg}) + (a v^{\prime} + 2 e_1^{\prime} + c_{1 q neg}^{\prime}) \right) \\
& = \left( b (v + v^{\prime}) + 2 (e_0 + e_0^{\prime}) + (p + p^{\prime}) + (c_{0 q neg} + c_{0 q neg}^{\prime}) \right) - s \left( a (v + v^{\prime}) + 2 (e_1 + e_1^{\prime}) + (c_{1 q neg} + c_{1 q neg}^{\prime}) \right) \\
& = (b - a s) (v + v^{\prime}) + 2 ( (e_0 + e_0^{\prime}) - s (e_1 + e_1^{\prime}) ) + ( (c_{0 q neg} + c_{0 q neg}^{\prime}) - s(c_{1 q neg} + c_{1 q neg}^{\prime}) ) + (p + p^{\prime}) \\
& = (2 e + b_{q neg}) (v + v^{\prime}) + 2 ( (e_0 + e_0^{\prime}) - s (e_1 + e_1^{\prime}) ) + ( (c_{0 q neg} + c_{0 q neg}^{\prime}) - s(c_{1 q neg} + c_{1 q neg}^{\prime}) ) + (p + p^{\prime}) \\
& = 2 ( e(v + v^{\prime}) + (e_0 + e_0^{\prime}) - s (e_1 + e_1^{\prime}) ) + ( b_{q neg} (v + v^{\prime}) + (c_{0 q neg} + c_{0 q neg}^{\prime}) - s(c_{1 q neg} + c_{1 q neg}^{\prime}) ) + (p + p^{\prime}) \\
\end{align*}
よって，\mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] で考えると，p + p^{\prime} に一致しています．
暗号文同士の足し算の具体例
ここでは，第２回「Ring-LWE問題を使った準同型暗号の具体例」 での数値例を使います．
\begin{align*}
m & = 3, \ q = 65, \ n = 2, \ \zeta_3 = \frac{-1 + \sqrt{-3}}{2} \\
s & = \zeta_3 + 1, \ a = - 8 \zeta_3 - 19, \ e = - \zeta_3 + 1, \ b = - 21 \zeta_3 - 9 \\
p & = \zeta_3 + 1, \ v = \zeta_3 + 1, \ e_0 = \zeta_3 - 1, \ e_1 = - \zeta_3, \ c_0 = -6 \zeta_3 + 11, \ c_1 = - 21 \zeta_3 - 11 \\
p^{\prime} & = \zeta_3, \ v^{\prime} = \zeta_3, \ e_0^{\prime} = \zeta_3, \ e_1^{\prime} = 2, \ c_0^{\prime} = 15 \zeta_3 + 21, \ c_1^{\prime} = - 11 \zeta_3 + 12
\end{align*}
このとき，
\begin{align*}
[c_0 + c_0^{\prime}]_q & = [(-6 \zeta_3 + 11) + (15 \zeta_3 + 21)]_{65} = [9 \zeta_3 + 32]_{65} = 9 \zeta_3 + 32 \\
[c_1 + c_1^{\prime}]_q & = [(- 21 \zeta_3 - 11) + (- 11 \zeta_3 + 12)]_{65} = [- 32 \zeta_3 + 1]_{65} = - 32 \zeta_3 + 1
\end{align*}
ですから，d = (d_0, d_1) = (9 \zeta_3 + 32, - 32 \zeta_3 + 1) です．
これを秘密鍵 s = \zeta_3 + 1 を使って復号します．
\begin{align*}
[[d_0 - s d_1]_q]_2 & = [[(9 \zeta_3 + 32) - (\zeta_3 + 1)(- 32 \zeta_3 + 1)]_{65}]_2 \\
& = [[(9 \zeta_3 + 32) - (- 32 \zeta_3^2 - 31 \zeta_3 + 1)]_{65}]_2 \\
& = [[32 \zeta_3^2 + 40 \zeta_3 + 31]_{65}]_2 \\
& = [[32 (- \zeta_3 - 1) + 40 \zeta_3 + 31]_{65}]_2 \\
& = [[8 \zeta_3 - 1]_{65}]_2 \\
& = [8 \zeta_3 - 1]_2 \\
& = 1
\end{align*}
となります．ここで，平文は pt + pt^{\prime} = 11 + 10 = 01 \ \mathrm{in} \ \mathbb{B}^2 ですし，p = \zeta_3 + 1, p^{\prime} = \zeta_3 でしたから，[p + p^{\prime}]_2 = 1 となっていて，確かに足し算できていることがわかりました．
暗号文同士の掛け算
続いて掛け算です．足し算の場合を思い返すと，
\begin{align*}
c_0 - s c_1 & = (b - a s)v + 2(e_0 - s e_1) + (c_{0 q neg} - s c_{1 q neg}) + p \\
& = 2(e v + e_0 - s e_1) + (b_{qneg} v + c_{0 q neg} - s c_{1 q neg}) + p
\end{align*}
でしたから，(c_0 - s c_1) + (c_0^{\prime} - s c_1^{\prime}) を \mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] 内で考えることで，p + p^{\prime} を得るのでした．
掛け算もナイーブに考えると，(c_0 - s c_1) \cdot (c_0^{\prime} - s c_1^{\prime}) を \mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] 内で考えればいいことになります．やってみましょう．
以下では記号の煩雑さを避けるために，
\begin{align*}
E_{2 neg} & = e v + e_0 - s e_1 \\
Q_{q neg} & = b_{qneg} v + c_{0 q neg} - s c_{1 q neg} \\
E_{2 neg}^{\prime} &= e^{\prime} v^{\prime} + e_0^{\prime} - s e_1^{\prime} \\
Q_{q neg}^{\prime} & = b_{qneg}^{\prime} v^{\prime} + c_{0 q neg}^{\prime} - s c_{1 q neg}^{\prime} \\
\end{align*}
とします．各記号の意味は，足し算のときと同じです．
\begin{align*}
(c_0 - s c_1) \cdot (c_0^{\prime} - s c_1^{\prime})
& = \{ 2 E_{2 neg} + Q_{q neg} + p \} \cdot \{ 2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime} \} \\
& = 2 \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + p p^{\prime}
\end{align*}
こうなります．また，左辺は c_0 c_0^{\prime} - s(c_1 c_0^{\prime} + c_0 c_1^{\prime}) + s^2 c_1 c_1^{\prime} です．
c_0 - s c_1 の形を睨んで，d_0 = c_0 c_0^{\prime}, d_1 = c_1 c_0^{\prime} + c_0 c_1^{\prime}, d_2 = - c_1 c_1^{\prime} と置くと，
\begin{align*}
d_0 - s d_1 - s^2 d_2 = 2 \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + p p^{\prime}
\end{align*}
となります．つまり，d_0 - s d_1 - s^2 d_2 を \mathbb{Z}^{(q)}[\zeta_m], \mathbb{Z}^{(2)}[\zeta_m] 内で考えると，平文の積 p p^{\prime} が得られます．
これでめでたしめでたしと思いきや実は２つ問題があります．
１つ目は，d_0 - s d_1 - s^2 d_2 を計算する際に，- s^2 の値を知らないことです．サーバ内で s \cdot s を実行するわけにはいきませんので．すると，事前に - s^2 の値を持っておく（＝公開鍵に入れておく）必要があります．
２つ目は，(c_0, c_1) と (c_0^{\prime}, c_1^{\prime}) の暗号文を掛けると (d_0, d_1, d_2) と３成分になってしまうことです．つまり，これは繰り返すと成分数が増えることを意味しますし，成分数を見ることで，何回掛け算を行なったかまで推定できてしまいます．
＊まあ元々の原因は，１成分の平文に対して暗号文が２成分あることなのですが・・・
この問題を次節から解消していきます．
スイッチ鍵
まずは問題の１つ目．実はこれは簡単に解消することができます．- s^2 の暗号文を事前に公開鍵に組み込んでおけばいいからです．
そして，それは実際に計算する必要はなく（というより計算しないほうがいい），暗号文としては，
\begin{align*}
c_0 - s c_1 & = (b - a s)v + 2(e_0 - s e_1) + (c_{0 q neg} - s c_{1 q neg}) + p \\
& = 2(e v + e_0 - s e_1) + (b_{qneg} v + c_{0 q neg} - s c_{1 q neg}) + p
\end{align*}
さえ満たしてくれればいいので，B を \mathbb{Z}^{(q)}[\zeta_m] からランダムに選んで，ノイズ E を選択して，\mathbb{Z}^{(q)}[\zeta_m] 内で A = s B - s^2 + 2E を計算してから (A, B) を - s^2 を平文とみたときの暗号文として出力すればいいからです．
一見すると，ランダムに選んで大丈夫なのかと思うかもしれませんが，NP困難な問題を仮定すると，暗号文の分布とランダムな分布を識別することもNP困難，が知られているので問題ありません．
そして，(A, B) をswitch鍵と呼びます（が，名前はどうでもいいです）．
暗号文同士の掛け算の修正版
さて，問題の２つ目です．上記のスイッチ鍵のところで，A = s B - s^2 + 2E を計算しました．すると，- s^2 = A - s B - 2 E ですから，
\begin{align*}
d_0 - s d_1 - s^2 d_2 = 2 \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + p p^{\prime}
\end{align*}
を \mathbb{Z}^{(q)}[\zeta_m] 内で変形しようと思うと，
\begin{align*}
d_0 - s d_1 + (A - s B - 2 E) d_2 & = 2 \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + p p^{\prime} \\
(d_0 + A d_2) - s (d_1 + B d_2) & = 2 \{ E d_2 + (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + p p^{\prime} \\
\end{align*}
となります．d_0^{\prime} = d_0 + A d_2, d_1^{\prime} = d_1 + B d_2 と置くと，
\begin{align*}
d_0^{\prime} - s d_1^{\prime} & = 2 \{ E d_2 + (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + p p^{\prime} \\
\end{align*}
このようにまとめられます．これでうまくいくように見えますが，もう１つ問題があって，それは |E d_2| が O(|q|) であることです．ここで，「|E d_2| が O(|q|) である」とは，E d_2 の各係数について O(|q|) です．以下多項式について，O(|q|) である，と書いたら，多項式の長さではなく，各係数のことを指している，と認識してください．
思い返すと，d_2 = c_1 c_1^{\prime} で |c_1| と |c_1^{\prime}| は共に O(|q|) でしたから，|d_2| は O(|q|) です．O(|q|^2) ではないかと思うかもしれませんが，今は q で bit 長を制限している（モジュラスとはそういう意味らしい）ので，これ以上オーダーが増えることはありません．
また，E はノイズなので，O(\log |q|) です．よって，|E d_2| は O(|q|) です．
すると，復号が失敗する可能性があります．この辺は 第２回「Ring-LWE問題を使った準同型暗号」 を確認してください．
では，どうすればいいのか？
「今は q で bit 長を制限している」のなら「bit 長を増やせばいいじゃない」．
P = O(|q|) なる奇数 P を取ります．
先に - s^2 の暗号文（switch鍵）を取りましたが，ここでは - P s^2 の暗号文を取ります．つまり，B を \mathbb{Z}^{(Pq)}[\zeta_m] からランダムに選んで，ノイズ E を選択して，\mathbb{Z}^{(Pq)}[\zeta_m] 内で A = s B - P s^2 + 2E を計算してから (A, B) を - P s^2 を平文とみたときの暗号文として出力します．
つまり，
\begin{align*}
d_0 - s d_1 - s^2 d_2 = 2 \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + p p^{\prime}
\end{align*}
だったのですから，両辺に P を掛けることで，
\begin{align*}
P d_0 - s P d_1 - P s^2 d_2 & = 2 P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + P p p^{\prime} \\
P d_0 - s P d_1 + (A - s B + 2 E) d_2 & = 2 P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} + P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + P p p^{\prime} \\
(P d_0 + A d_2) - s (P d_1 + B d_2) & = 2 \{ E d_2 + P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} \} + P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + P p p^{\prime}
\end{align*}
となります．ですので，\mathbb{Z}^{(Pq)}[\zeta_m] 内で d_0^{\prime} = P d_0 + A d_2, d_1^{\prime} = P d_1 + B d_2 とします．
\begin{align*}
d_0^{\prime} - s d_1^{\prime} = 2 \{ E d_2 + P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} \} + P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + P p p^{\prime}
\end{align*}
です．さて，\mathbb{Z}^{(q)}[\zeta_m] 内で Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) = 0 でしたから，\mathbb{Z}^{(Pq)}[\zeta_m] 内で P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} = 0 です．
また，O(|E d_2|) = O(|q|) でしたが，今は \mathbb{Z}^{(Pq)}[\zeta_m] で考えている（というか，そう考えたかった）ので，この部分も無視できます．
後は，\mathbb{Z}^{(2)}[\zeta_m] で考えればいいので，まとめると
\begin{align*}
[[d_0^{\prime} - s d_1^{\prime}]_{Pq}]_2 = P p p^{\prime}
\end{align*}
です．しかし，このままでは得られる平文が P 倍されています．かと言って，\mathbb{Z}^{(P)}[\zeta_m] で d_0^{\prime} - s d_1^{\prime} = 0 とは限りません．
そこで，\delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(P)}[\zeta_m] かつ \delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(2)}[\zeta_m] かつ \delta_0 の各係数が [- P, P] なるものを取ります．
何をしているのかというと，d_0^{\prime} の代わりに d_0^{\prime} - \delta_0 を代入することで，d_0^{\prime} - \delta_0 = 0 \ \mathrm{in} \ \mathbb{Z}^{(Pq)}[\zeta_m] としたいのです．また，\delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(2)}[\zeta_m] ですから，[\delta_0]_2 = 0 です．
さらに，d_0^{\prime} = P d_0 + A d_2 の構成から d_0^{\prime} を P で割ったときに元に戻らないと困るので，\delta_0 の各係数を (- P, P] と制限しています．
定式化すると，\delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(P)}[\zeta_m], \delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(2)}[\zeta_m], \delta_0[i] \in (- P, P] です．ただし，\delta_0[i] は 0 \leq i \leq n - 1 で \delta_0 の X^i の係数を表しています．
同様に，\delta_1 \equiv d_1^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(P)}[\zeta_m], \delta_1 \equiv d_1^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(2)}[\zeta_m], \delta_1[i] \in (- P, P] とします．
このとき，両辺から \delta_0 と s \delta_1 を引きます．
\begin{align*}
(d_0^{\prime} - \delta_0) - s (d_1^{\prime} - \delta_1) = 2 \{ E d_2 - (\delta_0 - s \delta_1) + P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} \} + P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + P p p^{\prime}
\end{align*}
ここで，d_0^{\prime \prime} = d_0^{\prime} - \delta_0, d_1^{\prime \prime} = d_1^{\prime} - \delta_1 と置くことで，
\begin{align*}
d_0^{\prime \prime} - s d_1^{\prime \prime} = 2 \{ E d_2 - (\delta_0 - s \delta_1) + P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} \} + P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + P p p^{\prime}
\end{align*}
とでき，d_0^{\prime \prime}, d_1^{\prime \prime}, P \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \}, P p p^{\prime} = 0 \ \mathrm{in} \ \mathbb{Z}^{(P)}[\zeta_m]ですから，
\begin{align*}
2 \{ E d_2 - (\delta_0 - s \delta_1) + P \{ (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \} \} = 0 \ \mathrm{in} \ \mathbb{Z}^{(P)}[\zeta_m]
\end{align*}
です．つまり，両辺を P で割ることができます．
\begin{align*}
\displaystyle
\frac{d_0^{\prime \prime}}{P} - \frac{s d_1^{\prime \prime}}{P} = 2 \left \{ \frac{E d_2 - (\delta_0 - s \delta_1)}{P} + (E_{2 neg}(2 E_{2 neg}^{\prime} + Q_{q neg}^{\prime} + p^{\prime}) + E_{2 neg}^{\prime}(Q_{q neg} + p)) \right \} + \{ Q_{q neg}(Q_{q neg}^{\prime} + p^{\prime}) + Q_{q neg}^{\prime}(p) \} + p p^{\prime}
\end{align*}
このとき，\displaystyle O(|\frac{E d_2 - (\delta_0 - s \delta_1)}{P}|) \neq O(|q|) ですから，\mathbb{Z}^{(q)}[\zeta_m] で無視することができます．
以上より，\displaystyle (\frac{d_0^{\prime \prime}}{P}, \frac{s d_1^{\prime \prime}}{P}) が暗号文の積となっていて，確かに \displaystyle \left[ \left[\frac{d_0^{\prime \prime}}{P} - \frac{s d_1^{\prime \prime}}{P} \right]_q \right]_2 = p p^{\prime} となります．
暗号文同士の掛け算のアルゴリズム
今までやってきたことをアルゴリズムとしてまとめます:
\underline{\mathrm{Def(乗算アルゴリズム)}}
入力の暗号文 (c_0, c_1) と (c_0^{\prime}, c_1^{\prime}) に対して，それらの積 (d_0^{\prime \prime}, d_1^{\prime \prime}) を次のように計算する:
-
\mathbb{Z}^{(Pq)}[\zeta_m] からランダムに選び，また，ノイズ E を選択して，\mathbb{Z}^{(Pq)}[\zeta_m] 内で A = s B - s^2 + 2E を計算する．switch鍵 (A, B) を出力する．
-
\mathbb{Z}^{(q)}[\zeta_m] 内で d_0 = c_0 c_0^{\prime}, d_1 = c_1 c_0^{\prime} + c_0 c_1^{\prime}, d_2 = - c_1 c_1^{\prime} を計算して，(d_0, d_1, d_2) を出力する．
- switch鍵 (A, B) を使って，\mathbb{Z}^{(Pq)}[\zeta_m] 内で d_0^{\prime} = P d_0 + B d_2, d_1^{\prime} = P d_1 + A d_2 を計算して，(d_0^{\prime}, d_1^{\prime}) を出力する．
-
\delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(P)}[\zeta_m], \delta_0 \equiv d_0^{\prime} \ \mathrm{in} \ \mathbb{Z}^{(2)}[\zeta_m], \delta_0[i] \in (- P, P] とする．ただし，\delta_0[i] は 0 \leq i \leq n - 1 で \delta_0 の X^i の係数を表す．同様に \delta_1 を計算して，(\delta_0, \delta_1) を出力する．
-
\mathbb{Z}^{(q)}[\zeta_m] 内で \displaystyle d_0^{\prime \prime} = \frac{d_0^{\prime} - \delta_0}{P}, d_1^{\prime \prime} = \frac{d_1^{\prime} - \delta_1}{P} として，(d_0^{\prime \prime}, d_1^{\prime \prime}) を出力する．
このアルゴリズムの具体例もやろうと思ったのですが，論文内記載の例がめちゃめちゃ計算がえぐかったので，飛ばします・・・
アルゴリズムのまとめ
最後に KeyGen から始めて，提案方式のアルゴリズムを加算・乗算含めてまとめておきます．
KeyGen() \rightarrow (sk = s, pk = (a, b)):
正整数 m を取って，n = \phi(m) とする．また，正整数 q を取る．
次に，s \leftarrow \mathbb{Z}^{(2)}[\zeta_m], \ a \leftarrow \mathbb{Z}^{(q)}[\zeta_m] を取る．ただし，s の各係数は O(\log |q|) であり，a の各係数は O(|q|) とする．
また，正の実数 \sigma について，平均0・分散 \sigma の正規分布 N(0, \sigma^2) から実数を選び，四捨五入する操作を n 回繰り返す．1 \leq i \leq n 回目で得られる整数値を S_{i - 1} として，e = S_{n - 1} \zeta_m^{n - 1} + S_{n - 2} \zeta_m^{n - 2} + \cdots + S_1 \zeta_m + S_0 を構成する．ただし，S_i = O(\log |q|) とする．
上記を用いて，b = [a s + 2 e]_q \ \mathrm{in} \ \mathbb{Z}^{(q)}[\zeta_m] を計算する．
秘密鍵 sk を sk = s で，公開鍵 pk を pk = (a, b) で定める．
Encrypt(pk) \rightarrow (c = (c_0, c_1)):
n bit 長の平文 pt \in \mathbb{B}^n を取る．円分整数 p を p = pt[n - 1] \zeta_m^{n - 1} + \cdots + pt[1] \zeta_m + pt[0] で構成する．ただし，pt[i] で pt の i 番目の要素を表すものとする．
次に，v \leftarrow \mathbb{Z}^{(2)}[\zeta_m] を取る．ただし，v の各係数は O(\log |q|) である．
また，正の実数 \sigma について，平均0・分散 \sigma の正規分布 N(0, \sigma^2) から実数を選び，四捨五入する(\star)操作を n 回繰り返す．1 \leq i \leq n 回目で得られる整数値を S_{0, i - 1} として，e_0 = S_{0, n - 1} \zeta_m^{n - 1} + S_{0, n - 2} \zeta_m^{n - 2} + \cdots + S_{0, 1} \zeta_m + S_{0, 0} を構成する．(\star)を更に n 回繰り返して，1 \leq i \leq n 回目で得られる整数値を S_{1, i - 1} として，e_1 = S_{1, n - 1} \zeta_m^{n - 1} + S_{1, n - 2} \zeta_m^{n - 2} + \cdots + S_{1, 1} \zeta_m + S_{1, 0} とする．ただし，S_{0, i}, S_{1, i} = O(\log |q|) とする．
上記を用いて，c_0 = bv + 2 e_0 + p \ \mathrm{in} \ \mathbb{Z}^{(q)}[\zeta_m] と c_1 = a v + 2 e_1 \ \mathrm{in} \ \mathbb{Z}^{(q)}[\zeta_m] を計算する．
暗号文 c = (c_0, c_1) とする．
Decrypt(sk, c) \rightarrow pt
sk = s として，pt = c_0 - s c_1 \ \mathrm{in} \ \mathbb{Z}^{(q)}[\zeta_m] を計算したのちに，pt \ \mathrm{in} \ \mathbb{Z}^{(2)}[\zeta_m] を出力する．
加算アルゴリズム
公開鍵 pk を固定して，平文 p に対して，Encrypt(pk) を実行して得られる暗号文を c = (c_0, c_1) とする．同様に平文 p^{\prime} の暗号文を c^{\prime} = (c_0^{\prime}, c_1^{\prime}) とする．
このとき，d = (c_0 + c_0^{\prime}, c_1 + c_1^{\prime}) を復号すると，p + p^{\prime} に対応する．
乗算アルゴリズム
入力の暗号文 (c_0, c_1) と (c_0^{\prime}, c_1^{\prime}) に対して，それらの積 (d_0^{\prime \prime}, d_1^{\prime \prime}) を次のように計算する:
-
\mathbb{Z}^{(Pq)}[\zeta_m] からランダムに選び，また，ノイズ E を選択して，\mathbb{Z}^{(Pq)}[\zeta_m] 内で A = s B - s^2 + 2E を計算する．switch鍵 (A, B) を出力する．
-
\mathbb{Z}^{(q)}[\zeta_m] 内で d_0 = c_0 c_0^{\prime}, d_1 = c_1 c_0^{\prime} + c_0 c_1^{\prime}, d_2 = - c_1 c_1^{\prime} を計算して，(d_0, d_1, d_2) を出力する．
- switch鍵 (A, B) を使って，\mathbb{Z}^{(Pq)}[\zeta_m] 内で d_0^{\prime} = P d_0 + B d_2, d_1^{\prime} = P d_1 + A d_2 を計算して，(d_0^{\prime}, d_1^{\prime}) を出力する．
-
\displaystyle \delta_0 \equiv d_0^{\prime} \ \mathrm{mod} \ P, \delta_0 \equiv d_0^{\prime} \ \mathrm{mod} \ 2, \delta \in (- \frac{P}{2}, \frac{P}{2}] とする．同様に \delta_1 を計算して，(\delta_0, \delta_1) を出力する．
-
\mathbb{Z}^{(q)}[\zeta_m] 内で \displaystyle d_0^{\prime \prime} = \frac{d_0^{\prime} - \delta_0}{P}, d_1^{\prime \prime} = \frac{d_1^{\prime} - \delta_1}{P} として，(d_0^{\prime \prime}, d_1^{\prime \prime}) を出力する．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
今回でイデアル格子暗号入門の連載が終わったので，一旦秘密計算から離れて耐量子計算機暗号について色々やっていこうかなって思っています．
次回からは QR-UOV という方式について理解ログを書いていきます．
Discussion