完全準同型暗号入門

はじめに

この資料では， イデアル格子暗号入門 で紹介されている完全準同型暗号について説明する．完全準同型暗号とは，２つの暗号文に対する足し算と掛け算ができる暗号方式である．

（ イデアル格子暗号入門 と同時に読むと良い思います。）

完全準同型暗号

完全準同型暗号とは，２つの暗号文に対する足し算と掛け算ができる暗号方式である．

数学的準備

本資料を読むにおいて，必要最低限の円分整数の知識について,以下に述べる．
本資料では，円分整数ついて詳しくは説明しない．

本資料を読む分には,円分整数とは 円分整数の性質 で説明する性質を持った，不思議な多項式みたいなものと思ってもらえれば構わない．

円分整数

$\zeta = e ^ {\frac{2 \pi i}{m}}$としたとき，以下のような虚数 $g$ を，円分整数または円の $m$ 分整数と呼ぶ．（$\phi(\cdot)$はオイラーの$\phi$関数）

$g = a_0 + a_1 \zeta + a_2 \zeta ^ 2 + \dots + a_{n - 1}\zeta^{n-1} （n = \phi(m), \forall a_0,\dots , a_{n-1} \in \mathbb{Z}）$

円分整数全体

円分整数全体の集合を $\mathbb{Z}[\zeta]$と表記する．

$\mathbb{Z}[\zeta] = \{a_0 + a_1 \zeta + a_2 \zeta ^ 2 + \dots + a_{n - 1}\zeta^{n-1} | n = \phi(m), \forall a_0,\dots , a_{n-1} \in \mathbb{Z}\}$

円分整数の性質

円分整数同士の演算では以下の性質が成り立つ.
（円分整数は可換環である.）

円分整数の性質1. 演算可能

円分整数同士は加法,減法,乗法ができる.

加法

円分整数同士は足し算ができ,その和は各係数を足した円分整数になる.

• $a + b = a_0 + b_0 + (a_1 + b_1)\zeta + \dots + (a_{n-1} + b_{n-1})\zeta^{n-1} (\forall a, b \in \mathbb{Z}[\zeta],\forall i, j, a_i, b_j \in \mathbb{Z})$

減法

円分整数同士は引き算ができ,その差は各係数を引いた円分整数になる.

• $a - b = a_0 - b_0 + (a_1 - b_1)\zeta + \dots + (a_{n-1} - b_{n-1})\zeta^{n-1}(\forall a, b \in \mathbb{Z}[\zeta],\forall i, j, a_i, b_j \in \mathbb{Z})$

乗法

円分整数同士は掛け算ができる．

• 多項式の掛け算と同じように計算できる．
• 具体的な乗法の方法について,本資料では紹介しない.

円分整数の性質2. 演算の閉性

円分整数は加法,減法,乗法について閉じる

加法の閉性

円の $m$ 分整数同士は足し算ができ，結果は必ず円の$m$ 分整数になる．

• $a + b \in \mathbb{Z}[\zeta] (\forall a, b \in \mathbb{Z}[\zeta])$

減法の閉性

円の $m$ 分整数同士は引き算ができ，差は必ず円の$m$ 分整数になる．

• $a - b \in \mathbb{Z}[\zeta] (\forall a, b \in \mathbb{Z}[\zeta])$

乗法の閉性

円の $m$ 分整数同士は掛け算ができ，積は必ず円の $m$ 分整数になる．

• $a b \in \mathbb{Z}[\zeta](\forall a, b \in \mathbb{Z}[\zeta])$

円分整数の性質3. 演算の可換性

円分整数の加法と乗法は可換である.

加法の可換性

円分整数同士の加法は可換である.

• $a + b = b + a (\forall a, b \in \mathbb{Z}[\zeta])$

乗法の可換性

円分整数同士の乗法は可換である.

• $a b = b a (\forall a, b \in \mathbb{Z}[\zeta])$

円分整数の性質4. 整数との演算

スカラー倍

整数と円分整数はかけることができ,その積は円分整数の各項が整数倍されたものになる.なおこの演算は可換である.

• $a b = b a = a_0 b + a_1 b\zeta+ a_2 b \zeta ^ 2 \dots + a_{n-1} b \zeta^{n-1} (\forall a \in \mathbb{Z}[\zeta], \forall b \in \mathbb{Z})$

整数との剰余

円分整数を整数で割ってあまりをとることができる.その剰余は円分整数の各項を整数でわってあまりを,各項の係数とした円分整数とする.

• $a \bmod n = (a_0 \bmod n) + (a_1 \bmod n) \zeta + \dots + (a_{n - 1} \bmod n )\zeta^{n-1}$
• $[a]_n = [a_0]_n + [a_1]_n \zeta + \dots + [a_{n - 1}]_n \zeta^{n-1}$

整数との除算

円分整数を整数$n$（$a \bmod n = 0, n \in \mathbb{Z}$）で割ることができる.その商は円分整数の各項を整数でわったものを,各項の係数とした円分整数とする.$a \bmod n \neq 0$のとき，$a /n $は円分整数に閉じない．

• $a / n = (a_0 / n) + (a_1 / n) \zeta + \dots + (a_{n - 1} / n )\zeta^{n-1}$

その他表記

$\mathbb{Z}_q = \{0, 1, \cdots , q - 1\}$

$0$ 〜 $q-1$ までの整数の集合

$\mathbb{Z}^{(q)} = \{-q/2 + 1, \dots , 0, \cdots , q/2\} = (-q/2, q/2] \cap \mathbb{Z}$

$-q/2+1 〜 q/2$までの整数の集合（実数がでた場合は,0に近づけて切り捨てる）

※ 一般的な表記と異なる.

$\mathbb{Z}_q[\zeta]$

$\mathbb{Z}_q$の要素を各係数にもつ円分整数全体.

$\mathbb{Z}^{(q)}[\zeta]$

$\mathbb{Z}^{(q)}$の要素を各係数にもつ円分整数全体.

$a \bmod n$

$a$を$n$で割ったあまりを表す.あまりは$\{0 , 1, \dots, n - 1\}$にとる.$a$が円分整数の場合,$a$の各係数を$n$で割った係数を持つ円分整数を表す.

$[a]_n$

$a$を$n$で割ったあまりを表す.あまりは$- n/2$より大きく$n/2$以下にとる.円分整数の場合,$a$の各係数を$n$で割った係数を持つ円分整数を表す.

$a \equiv b \pmod n$

$a$を$b$を$n$で割ったあまりが等しい（合同）

$a \leftarrow \mathbb{Z}_q[\zeta]$

$\mathbb{Z}_q[\zeta]$からランダム（※一様乱数的）に要素を取り出して$a$とする.

$a \leftarrow \mathbb{Z}^{(q)}[\zeta]$

$\mathbb{Z}^{(q)}[\zeta]$からランダム（※一様乱数的）に要素を取り出して$a$とする.

$a \leftarrow \chi(0,\sigma^2)$

各係数に平均が$0$かつ分布が$\sigma^2$のガウス乱数を持つ,円分整数を取り出して$a$とする.

• $a = Round(N(0, \sigma^2)) + Round(N(0, \sigma^2)) \zeta + \dots + Round(N(0, \sigma^2))\zeta^{n-1} \leftarrow \chi(0,\sigma^2)$
• $N(0, \sigma ^ 2)$は$0$かつ分布が$\sigma^2$のガウス乱数

※ 一般的な表記と異なる.

暗号化と復号

本節では，方式の暗号化/復号の仕組みについて述べる．

具体的に，本節は公開鍵の暗号の設計に必要な暗号学的仮定について説明した後，暗号化と復号の手順についてそれぞれ説明する．

RLWE 問題

RLWE(Ring Learning With Errors)問題とは，以下のような次元の大きい$a, b, e, s$が存在する時，$a, b$から$e, s$を求めるのが難しいという問題である．$q$は大きな自然数，$n$は円分整数の次元である．

秘密鍵

$s = s_0 + s_1 \zeta + \dots + s_{n-1} \zeta ^ {n-1} \leftarrow \mathbb{Z}^{(2)}[\zeta]$

$\mathbb{Z}^{(2)}$の一様乱数から選んだ$n$個の係数$s_0, \dots, s_{n-1}$を持つ円分整数.

ノイズ

$e = Round(N(0, \sigma^2)) + \dots + Round(N(0, \sigma^2))\zeta^{n-1} \leftarrow \chi(0,\sigma^2)$

平均が$0$かつ分布が$\sigma^2$のガウス乱数から選んだ，$n$個の要素$e_0, \dots, e_{n-1}$を持つ円分整数. $\sigma$の大きさは大きすぎても，小さすぎてもいけない．

公開鍵1

$a = a_0 + a_1 \zeta + \dots + a_{n-1} \zeta ^ {n-1} \leftarrow \mathbb{Z}^{(q)}[\zeta]$
$\mathbb{Z}^{(q)}$の一様乱数から選んだ$n$個の係数$a_0, \dots, a_{n-1}$を持つ円分整数.

公開鍵2 $b = [as + e]_q \in \mathbb{Z}^{(q)}[\zeta]$

$a$と$s$の積に，$e$を足して，$q$のあまりをとった円分整数.

$\sigma$が大きすぎると復号できなくなり，小さすぎると安全でなくなるため，丁度良いサイズが求められている．
一般に$\sigma$は$q$にくらべて，かなり小さくとれることが知られている．

手順

以下の鍵生成，暗号化，復号の手順にそれぞれ示す．

鍵生成

以下の手順で公開鍵$pk$，秘密鍵$sk$を生成する．以下の$q$は大きな自然数，$n$円分整数の次元である．

1. 以下を生成する．
   • ノイズ $e \leftarrow \chi(0,\sigma^2)$
   • 秘密鍵 $s \leftarrow \mathbb{Z}^{(2)}[\zeta]$
   • 公開鍵 $a \leftarrow \mathbb{Z}^{(q)}[\zeta]$
2. 公開鍵 $b = [a s + 2 e ]_{q} \in \mathbb{Z}^{(q)}[\zeta]$ を計算する．
   - $e$ではなく，$2e$ を足していることに注意
3. 公開鍵を$pk = (a, b)$，秘密鍵$sk = s$とする．

暗号化

以下の手順で，平文$m \in \mathbb{Z}^{(2)}[\zeta]$を$pk = (a, b)$で暗号化した，暗号文$c$を計算する．

1. 小さな一様乱数を集めた整数 $v \leftarrow \mathbb{Z}^{(2)}[\zeta]$ を生成する．
2. ノイズ $e_1, e_2 \leftarrow \chi(0,\sigma^2)$ を生成する．
3. $c_0 = [bv + 2e_0 + m]_q$ を計算する．
4. $c_1 = [av + 2e_1]_q$ を計算する．
5. 暗号文を$c = (c_0, c_1)$ とする．

復号

暗号文$c = (c_0, c_1)$と秘密鍵$sk = s$用いて，平文$m$を以下のように求める．

$m = [[c_0 - s c_1 ]_q]_2$

健全性の証明

この節では暗号文が正しく復号されることを説明する．
（$m = [[c_0 - s c_1 ]_q]_2$が成り立つことを，以下の1.と2.で証明する．）

大まかには，1.で$c_0 - s c_1 = m + 2(ev + e_0 - se_1)$であることを証明した後，2.で $m = [[m + 2(ev + e_0 - se_1)]_q]_2$であることを証明する．

1. 平文とノイズの和であることの証明

まず以下の通り, $c_0 - s c_1 = m + 2(ev + e_0 - se_1)$であることがわかる.

\begin{align} c_0 - s c_1 &\equiv bv + 2e_0 + m - s(av + 2 e_1) \\ &\equiv bv + 2e_0 + m - s a v - 2 s e_1 \\ &\equiv m + (b-as)v + 2{e_0} - 2 se_1 \\ &\equiv m + 2ev + 2 e_0 - 2 se_1 \\ &\equiv m + 2(ev + e_0 - se_1) \pmod q \end{align}

※実際には等式はなりたたず,$q$を法として合同である

$e_{t} = ev + e_0 - se_1$とおくと，これは平文$m$とノイズ$2e_{t} = 2(ev + e_0 - se_1)$の和になっている.

（まとめると，$c_0 - s c_1 = m + 2(ev + e_0 - se_1) = m + 2 e_t$となる）

2. ノイズの消去

以下の理由で，$m = [[m + 2e_{t}]_q]_2$が成り立つ．

1. $2e_{t}$の各係数が$q$より小さい場合， $[[2e_{t}]_q]_2 = [2e_{t}]_2$となる．

   • $e_{t}$ を構成する$e$，$e_0$,$e_1$, $v$，$s$どれをとっても，$q$にくらべてかなり小さい為，$e_{t}$は$q$より小さくなる．

2. $2e_{t}$の各係数は，必ず偶数である．$[2e_{t}]_2$の各係数は$0$になる．

3. $m$の各係数には，$0$か$1$が入っていた為，2のあまりをとっても値が変わらない．

足し算と掛け算

この暗号方式は，暗号化した円分整数同士の，足し算と掛け算ができる．

足し算

平文$m, m'$，秘密鍵$s$による平分の暗号文$c_0', c_1'$と復号処理$decrypt$がある時，以下を満たすような足し算$sum$を考える．

$m + m' = decrypt(sum(c_0', c_1'),s)$

以下に足し算の手順と健全性の証明を以下に述べる．

手順

同じ秘密鍵でそれぞれ暗号化された，$m$の暗号文$c = (c_0, c_1)$, $m'$の暗号文$c' = (c_0', c_1')$があるとする．

$m + m'$を暗号化した暗号文$c''= (c_0'', c_1'')$は，次のように計算できる．

\begin{align} c_0'' &= [c_0 + c_0']_q \\ c_1'' &= [c_1 + c_1']_q \\\\ c'' &= (c_0'', c_1'') \\ &= ([c_0 + c_0']_q, [c_1 + c_1']_q) \end{align}

健全性の証明

暗号文が正しく復号されることを以下に証明する．
基本的な流れは， 通常の暗号化に対する健全性の証明 と同じである．

1. 平文とノイズの和であることの証明

$c_0' - s c_1' = m' + 2e_{t}'$と置く．

$m + m'$を暗号化した暗号文$c''= (c_0'', c_1'')$を復号したものは，以下の通り，平文$m + m'$とノイズ$2(e_{t} + e_{t}')$ の和になっていることがわかる．

\begin{align} c_0& + c_0' - s (c_1 + c_1') \\ &\equiv c_0 - s c_1 + c_0' - s c_1' \\ &\equiv m + 2e_{t} + m' + 2e'_{t} \\ &\equiv m + m' + 2(e_t + e'_{t}) \pmod q \end{align}

2. ノイズの消去

以下の理由で，$m + m' = [[m + m' + 2(e_{t} + e_{t}')]_q]_2$が成り立つ．

1. $2(e_{t} + e_{t}')$が$q$より小さい場合， $[[2(e_{t} + e_{t}')]_q]_2 = [2(e_{t} + e_{t}')]_2$となる．

   • $2(e_{t} + e_{t}')$の各係数は以下の理由で$q$より小さい
     • $e_{t}$ を構成する$e$，$e_0$,$e_1$, $v$，$s$どれをとっても，$q$にくらべてかなり小さい
     • $e_{t}$と同じ理由で$e_{t}'$は$q$よりかなり小さい．

2. $2(e_{t} + e_{t}')$の各係数は，必ず偶数である．$[2(e_{t} + e_{t}')]_2$の各係数は$0$になる．

3. $m+m'$の各係数は$\mathbb{Z}^{(2)}$なので，2で割ったあまりをとることで，正しい計算結果を得ることができる．

掛け算

平文$m, m'$，秘密鍵$s$による平分の暗号文$c, c'$と復号処理$decrypt$がある時，以下を満たすような掛け算$mul$を考える．

$mm' = decrypt(mul(c, c'),s)$

まず簡単な掛け算の方法について述べる．その掛け算の方法では,積の暗号文がもつ成文の数が増えてしまう問題がある.

最後に成文の数が増えない掛け算の方法について述べる.

シンプルな方法

以下にシンプルな方式の手順，健全性，この方式の問題点についてそれぞれ述べる．

手順

以下にシンプルな方式の掛け算の手順について述べる．

この方式では,復号の仕方が通常の復号と変わるため，
その手順についても述べる．

掛け算

同じ秘密鍵でそれぞれ暗号化された，$m$の暗号文$c = (c_0, c_1)$, $m'$の暗号文$c' = (c_0', c_1')$があるとする．

$m m'$を暗号化した暗号文$c''= (c_0'', c_1'', c_2'')$は，次のように計算できる．

\begin{align} c_0'' &\equiv [c_0 c_0']_q \\ c_1'' &\equiv [c_0 c_1' + c_0' c_1]_q \\ c_2'' &\equiv [- c_1 c_1']_q \\\\ c'' &\equiv (c_0'', c_1'', c_2'') \\ &\equiv ([c_0 c_0']_q , [c_0 c_1' + c_0' c_1]_q, [- c_1 c_1']_q ) \pmod q \end{align}

復号

暗号文$c'' = (c_0'', c_1'', c_2'')$と秘密鍵$sk = s$用いて，平文$m$を以下のように求める．

$mm' = [[c_0'' - s c_1'' - s^2 c_2'']_q]_2$

健全性の証明

暗号文が正しく復号されることを以下に証明する．
基本的な流れは， 通常の暗号化に対する健全性の証明 と同じである．

1. 平文とノイズの和であることの証明

$c_0' - s c_1' = m + e_{t}'$と置く．

$m + m'$を暗号化した暗号文$c''= (c_0'', c_1'', c_2'')$を復号したものは，以下の通り，平文$m m'$とノイズ$2e_{t} e_{t}'$ の和になっていることがわかる．

\begin{align} c_0'' &- s c_1'' - s^2 c_2'' \\ &\equiv c_0 c_0' - s(c_0c_1' + c_0'c_1) - s^2(- c_1 c_1') \\ &\equiv c_0 c_0' - s c_0c_1' - s c_0'c_1 + s^2 c_1 c_1' \\ &\equiv c_0(c_0' - sc_1') - s c_1(c_0' - s c_1') \\ &\equiv c_0 (m' + 2e_t')' - s c_1 (m' + 2e_t')' \\ &\equiv (c_0 - s c_1) (m' + 2e_t')' \\ &\equiv (m + 2e_t) (m' + 2e_t')' \\ &\equiv m m' + 2e_t m' + 2e_t' m + 2e_te_t' \\ &\equiv m m' + 2(e_t m' + e_t' m + e_te_t') \pmod q \end{align}

$e_{t}'' = e_t m' + e_t' m + e_te_t'$とおくと，これは平文$mm'$とノイズ$2e_{t}'' = 2(e_t m' + e_t' m + e_te_t')$の和になっている.

（まとめると，$c_0'' - s c_1'' - s^2 c_2'' = m m' + 2(e_t m' + e_t' m + e_te_t') = mm' + 2e_{t}''$となる）

2. ノイズの消去

以下の理由で，$mm' = [[m m' + 2(e_t m' + e_t' m + e_te_t')]_q]_2$が成り立つ．

1. $2e_{t}''$が$q$より小さい場合， $[[2e_{t}'']_q]_2 = [2e_{t}'']_2$となる．

   • $2e_{t}''$は以下の理由で$q$より小さい
     • $m$と$m'$は，$q$にくらべてかなり小さい
     • $e_{t}$ を構成する$e$，$e_0$,$e_1$,$v$，$s$どれをとっても，$q$にくらべてかなり小さい
     • $e_{t}$と同じ理由で$e_{t}'$は$q$よりかなり小さい．

2. $2e_{t}''$の各係数は，必ず偶数である．$[2e_{t}'']_2$の各係数は$0$になる．

3. $mm'$の各係数は$\mathbb{Z}^{(2)}$なので，2で割ったあまりをとることで，正しい計算結果を得ることができる．

問題点

この方式には,入力に対して出力の成分の数が大きくなるという問題がある.

例えば，以下のように2成分同士の掛け算では,３成分になる.

• 2成分の掛け算(i.e. $(c_0, c_1)$と$(c_0',c_1')$の掛け算)をすると,積が3成分(i.e. $(c_0'', c_1'', c_2'')$)になる.

このように,掛け算を繰り返せば繰り返すほど,出力する成分の数が大きくなることが知られている.

成文の数が増えない掛け算の方法

以下に出力が必ず2成分になる掛け算の手順，健全性についてそれぞれ述べる．

手順

以下に出力が必ず2成分になる掛け算の手順について述べる．

大まかに以下の流れで説明する.

1. 掛け算に使う値の生成
2. 掛け算の仕方
   • シンプルな掛け算
   • 成分を2成文にする
     • モジュラスが変わる.
   • ノイズを消しながら,モジュラスを$q$に戻す

1. 掛け算に使う値の生成

1. $q$の同程度の大きさを持つ奇数 $P$を選ぶ.
2. $s^2P$の暗号文$(A, B)$を生成する.
   • $A \leftarrow \mathbb{Z}^{(qP)}$
   • $B = [A s - s^2 P + 2e]_{qP}$

2. シンプルな掛け算

同じ秘密鍵でそれぞれ暗号化された，$m$の暗号文$c = (c_0, c_1)$, $m'$の暗号文$c' = (c_0', c_1')$があるとする．

シンプルな掛け算 に沿って,$m m'$を暗号化した暗号文$c'' = (c_0'', c_1'', c_2'')$　を計算する.

3. 成分を2成文にする処理

$c_0''', c_1'''$を次のように計算する.

\begin{align} c_0''' &= [P c_0'' + Bc_2'']_{qP} \\ c_1''' &= [P c_1'' + Ac_2'']_{qP} \\ \end{align}

4. ノイズを消しながら,モジュラスを$q$に戻す

$m m'$を暗号化した暗号文$c^{(4)}= (c_0^{(4)}, c_1^{(4)})$を次のように計算する.ただし$\delta_{0}, \delta_{1}$は以下に沿ってなるべく小さく選ぶ.

\begin{align} \exists \delta_i \in \mathbb{Z}^{(p)},& [\delta_i]_P = [c_i''']_P , [\delta_i]_2 = 0\\ \\ c_0^{(4)} &= [(c_0''' - \delta_0)/P]_q \\ c_1^{(4)} &= [(c_1''' - \delta_1)/P]_q \\ \\ c^{(4)} &= (c_0^{(4)}, c_1^{(4)}) \\ &= ([(c_0''' - \delta_0)/P]_q, [(c_1''' - \delta_1)/P]_q) \end{align}

$c_0'''$, $c_1'''$がそれぞれ$P$で割り切れるとは限らない．
そこで$c_0'''$, $c_1'''$を$\delta_{0}, \delta_{1}$でそれぞれ引くことで，必ず$P$で割り切れるようにしている．

健全性の証明

暗号文が正しく復号されることを以下に証明する．

1. 掛け算に使う値の生成

暗号文$c''' = (c_0''', c_1''')$に対する復号を考えてみる.

\begin{align} c_0''' &- s c_1''' \\ & \equiv c_0''P + Bc_2'' - s (P c_1'' + Ac_2'') \\ & \equiv c_0''P + (As - s^2 P + 2e)c_2'' - s (P c_1'' + Ac_2'') \\ & \equiv c_0''P + (Asc_2'' - s^2 c_2''P + 2ec_2'') - (s c_1''P + Asc_2'' ) \\ & \equiv c_0''P + (Asc_2'' - s^2 c_2''P + 2ec_2'') - (s c_1''P + Asc_2'' ) \\ & \equiv c_0''P - sc_1''P + (Asc_2'' - Asc_2'' + s^s c_2'' P + 2ec_2'')\\ & \equiv c_0''P - sc_1''P + s^2 c_2'' P + 2ec_2'' \\ & \equiv P(c_0'' - sc_1'' + s^2 c_2'') + 2ec_2'' \\ & \equiv P m m ' + 2Pe_t'' + 2ec_2'' \pmod q \end{align}

これは,暗号文に $P$をかけたものになっている.

2. ノイズを消しながら,モジュラスを$q$に戻す

$c_0'''/P$, $c_1'''/P$に対する復号を考えてみる.

\begin{align} c_0'''/P - s c_1/P''' & \equiv \frac{c_0''' - s c_1'''}{P} \\ & \equiv \frac{P m m ' + 2Pe_t'' + 2ec_2}{P} \\ & \equiv mm' + 2 e_t '' + 2ec_2''/P \pmod q \end{align}

しかし，$2ec_2''/P$の各係数は整数にならないため，$c_0'''/P$, $c_1'''/P$の各係数も整数にならない．

3. 分数が出ないように調整

$c_0 / P , c_1 / P$ で分数がでないようにするため.
各項を $\delta_0, \delta_1$をつかって以下のように調整する．

\begin{align} c_0''' - \delta_0 \equiv c_0''' - \delta_0 \equiv c_0''' - c_0''' \equiv 0 \pmod P \\ c_1''' - \delta_1 \equiv c_1''' - \delta_1 \equiv c_1''' - c_0''' \equiv 0 \pmod P \end{align}

それらを$P$で割ると， 以下のようになる．

\begin{align} c_0^{(4)} &= (c_0''' - \delta_0) / P \bmod q \\ c_1^{(4)} &= (c_1''' - \delta_1) / P \bmod q \end{align}

4. 復号

$\delta_0 = 2 \delta_0', \delta_1 = 2 \delta_1'$とおく.
（$\delta_0, \delta_1$ の各係数は偶数なので,このような置き方をしても構わない）

暗号文$c^{(4)} = (c_0^{(4)} c_1^{(4)})$ を復号したものは,

\begin{align} c_0^{(4)} - s c_1^{(4)} &\equiv (c_0''' - \delta_0)/P - s(c_1''' - \delta_1)/P \\ &\equiv (c_0''' - sc_1''') / P + (s\delta_1 - \delta_0) / P \\ &\equiv mm' + 2 e_t '' + 2ec_2''/P + (2s\delta_1' - 2\delta_0') / P \\ &\equiv mm' + 2 e_t '' + 2( ec_2'' + s\delta_1 '- \delta_0') / P \pmod q \end{align}

5. ノイズの消去

以下の理由で，$m m' = [[mm' + 2 e_t '' + 2( ec_2'' + s\delta_1 - \delta_0) / P]_q]_2$が成り立つ．

1. $2 e_t '' + 2( ec_2'' + s\delta_1 - \delta_0) / P$が$q$より小さい場合， $[[2 e_t '' + 2( ec_2'' + s\delta_1 - \delta_0) / P]_2$となる．

   • $2 e_t '' + 2( ec_2'' + s\delta_1 - \delta_0) / P$の各係数は以下の理由で$q$より小さい
     • $e_{t}''$は$q$にくらべてかなり小さい
     • $2( ec_2'' + s\delta_1 - \delta_0) / P$は大きな奇数$P$で割っているので$q$に比べてかなり小さい．

2. $2 e_t '' + 2( ec_2 ''+ s\delta_1 - \delta_0) / P$の各係数は，必ず偶数である．$[2 e_t '' + 2( ec_2'' + s\delta_1 - \delta_0) / P]_2$の各係数は$0$になる．

3. $mm'$の各係数は$\mathbb{Z}^{(2)}$なので，2で割ったあまりをとることで，正しい計算結果を得ることができる．

まとめ

完全準同型暗号についてまとめた．
完全準同型暗号はRLWE仮定に基づいており,
暗号文同士の足し算と引き算ができた．