（本記事は有田正剛『イデアル格子暗号入門』の内容を基に資料作成者ご本人の許可を得て作成しています。）
Ring-LWE問題の困難性をベースとした準同型暗号について解説します。
本記事の理解に必要な数学的概念の説明を行った後、Ring-LWE問題とその困難性について解説をします。その後、その困難性に強度の根拠を持つ準同型暗号の生成、暗号、復号化とその準同型性について簡単な説明を行います。
諸概念の導入
本題に入る前にいくつか必要な概念を定義しておきます。概念の定義の後に具体例をまとめて提示していますのでそちらも併せてご確認ください。
円分整数
\xi = \cos \left( \frac{2\pi}{m} \right) + i\sin \left( \frac{2\pi}{m} \right)
とすると、この複素数は $\xi ^m = 1$ を満たしています。
0以上m-1以下の整数の中でmと互いに素な整数の個数を$n = \phi(m)$とした時の
a_0 + a_1 \xi + \cdots + a_{n-1} \xi ^{n-1}\ \ \ (a_0, a_1 ,\dots, a_{n-1}\in \mathbb{Z})
の形の複素数を円の$m$分整数（円分整数）といいます。
（後に円の3分整数の例でも紹介していますが、$\xi ^n$が$\xi ^{n-1}$次以下の項の線形和によって表現されることから、$\xi ^n$以上の項は$\xi ^{n-1}$以下の項にまとめられます。なので円分整数の定義には$\xi^n$以上の項は存在していません。）
また円分整数$h$に対して絶対値$\left\lvert |h| \right\rvert $を
\sqrt{a_0 ^2 + a_1 ^2 + \cdots + a_{n-1} ^2}
と定義します。（一般に複素数の絶対値とは異なる値を取ります。）
イデアル
円分整数$g$の倍数全体の集合$I_g$を円分整数$g$が生成するイデアルといいます。すなわち
I_g = \{ a_0 g + a_1 \xi g + \dots + a_{n-1} \xi ^{n-1} g\ |\ a_0, a_1 ,\dots, a_{n-1}\in \mathbb{Z} \}
です。
記号の定義
最後にいくつか記号の定義を行います。
- $a\ \text{mod}\ n$：$a$を$n$で割った余り。余りは$0$から$n-1$の範囲に取る。$a$が円分係数の場合は$\xi$の各項の係数に関して余りをとる。
- $[a]_n$：$a$を$n$で割った余り。余りは$(-\frac{n}{2}, \frac{n}{2}]$の範囲に取る。$a$が円分係数の場合は$\xi$の各項の係数に関して余りをとる。
- $\mathbb{Z}_p = \{ 0, 1, \cdots , p-1 \}$
- $\mathbb{Z}^{(p)} = ( -\frac{p}{2}, \frac{p}{2}]\ \cap\ \mathbb{Z}$
- $\mathbb{Z}[\xi] = \{ a_0 + a_1 \xi + \cdots + a_{n-1} \xi ^{n-1}\ |\ a_0, a_1 ,\dots, a_{n-1}\in \mathbb{Z} \}$
- $\mathbb{Z_p} [\xi] = \{ a_0 + a_1 \xi + \cdots + a_{n-1} \xi ^{n-1}\ |\ a_0, a_1 ,\dots, a_{n-1}\in \mathbb{Z}_p \}$
- $\mathbb{Z} ^{(p)}[\xi] = \{ a_0 + a_1 \xi + \cdots + a_{n-1} \xi ^{n-1}\ |\ a_0, a_1 ,\dots, a_{n-1}\in \mathbb{Z} ^{(p)}\}$
具体例
$m=3$を選び、円の3分整数として$\xi = -\frac{1}{2} + \frac{\sqrt{3}}{2}i$を考えます。0以上2以下の整数で3と互いに素な整数は2つあるので$n= 2$となります。$\xi ^2 = -\xi -1$となるので$\xi ^2$以上の項は$\xi$以下の項にまとめられます。さらに円分整数$g, h$を$g = 3 + 4\xi, \ h = 5 + 12\xi$とします。この例を用いて先ほどまで紹介した各種の定義、計算について具体例を提示します。
\begin{align}
&
\begin{cases}
g + h = 8 + 16\xi\\
g \cdot h = 15 + 56\xi + 48\xi^2 = 15 + 56\xi + 48( -\xi -1) = -33 + 8\xi\\
||g|| = 5\\
||h|| = 13
\end{cases}
\\\\
&I_g = \{ a_0 g + a_1 \xi g \ |\ a_0, a_1 \in \mathbb{Z} \} \\
&\ \ \ \ = \{ a_0 (3+4\xi) + a_1 (-4-\xi) \ |\ a_0, a_1 \in \mathbb{Z} \} \\
&\ \ \ \ = \mathbb{Z} (3+4\xi) + \mathbb{Z}(-4-\xi)\\\\
&
\begin{cases}
8\ \text{mod}\ 5 = 3\\
[8]_5 = -2\\
12 + 8\xi -9\xi ^2\ \text{mod} \ 5 = 2 + 3\xi + \xi^2\\
[12 + 8\xi -9\xi ^2]_5 = 2 -2\xi + \xi^2\\
\end{cases}
\\\\
&
\begin{cases}
\mathbb{Z}_5 = \{ 0, 1, 2, 3,4 \}\\
\mathbb{Z}^{(5)} = \{ -2, -1, 0, 1, 2 \}
\end{cases}
\end{align}
剰余や剰余環について記号によって微妙な差がありますので注意しましょう。
これらの概念をふまえて、次はRing-LWE問題について解説します。
Ring-LWE問題
Ring-LWE(Ring-Learning with Errors)問題とは多項式$a(x),b(x)$が与えられて
b(x) = a(x)s(x) +e(x)
なる関係を持つ時、秘密の多項式$s(x)$を求める問題です。ノイズ項$e(x)\neq 0$が存在することにより$s(x)$を求めることが難しくなっています。
ここでは以下の様に値を設定し、Ring-LWE問題の設定および困難性を感じることにします。
\begin{align}
\begin{cases}
&m:m \in \mathbb{N}として適当に設定\\
&n:n = \phi (m)\\
&q:q \in \mathbb{N}として適当に設定\\
&s: s\in \mathbb{Z} ^{(2)}[\xi] となるように係数を一様ランダムにとりsを設定\\
&a:a\in \mathbb{Z} ^{(q)}[\xi]となるように係数を一様ランダムにとりaを設定\\
&\sigma: \sigma >0として適当に設定\\
&e:e \in \mathbb{Z}[\xi]となるように係数をN(0, \sigma^2)からサンプルし最も近い整数に丸めeを設定\\
&b:b = [as + e]_qとして設定
\end{cases}
\end{align}
繰り返しになりますが$a$$とb$を与えられたとき$s$を求める問題をRing-LWE問題といいます。次に具体例を紹介しますが、それをふまえてRing-LWE問題の困難性を感じてみることにします。
具体例
$\xi = -\frac{1}{2} + \frac{\sqrt{3}}{2}i$とする。
\begin{align}
\begin{cases}
&m=3\\
&n=2\\
&q=65\\
&s=1 + \xi\\
&a=-19-8\xi\\
&\sigma = 2\\
&e = 1 -\xi\\
&b= [as + e]_{q} = [(-19-8\xi)(1 + \xi) + 1 -\xi]_{65} = -10-20\xi
\end{cases}
\end{align}
各文字のイメージを解説します。$s$は各係数を$\{ 0, 1 \}$からランダムに選び、$q$を大きめにとることで$a$の係数は比較的幅広い範囲からランダムに取ることになります。また$\sigma$によって$e$の係数のおおよその範囲が決定されます。
実際に$(a, b)$が与えられたときに$(s,e)$を求めることに挑戦してみます。先ほどは秘密解の$s$を求める問題をRing-LWE問題としましたが、実際に$s$を求める際には同時に$e$も必然的に求めることになるのでここでは$(s,e)$を求めることにします。求めるべき$s, e$を$s = s_0 + s_1 \xi,\ e =e_0 + e_1 \xi$とします。解くべき問題は多少の計算を省略すると
-19s_0 + 8s_1 + e_0 \equiv -10\ (\text{mod}\ 65)\\
-8s_0 - 11s_1 + e_1 \equiv -20\ (\text{mod}\ 65)
と言い換えることができます。$e_0,e_1,s_0,s_1$の取りうる値が限られていることから全探索的に解を求めると、上で設定した$s,e$が適切であることがわかります。
Ring-LWE問題の困難性
ここで$m$を大きく設定することで$n$が大きい値を取ると、$e$の項の数が多くなります。それにより$e$全体として取りうる値のパターン数が$n$について指数的に増加します。（各係数がある程度の範囲の整数値からピックアップされ、それがn個あるとすると、全体の取りうる値のパターン数はその範囲の整数値の個数のn乗になります。）
さらに$\sigma$を小さく取りすぎた場合、$e$の設定の仕方を考えると、それは$e = 0$と判明してしまうことに相当するので簡単に$s$が求まってしまいます。一方で、$\sigma$を大きく取りすぎると、$e$の係数を選択する際に一様ランダムに選んでいることと同じになってしまいます。$b= [as + e]_{q}$により$a$と$b$はある程度関係づけられていましたが、$e$のランダム性（ノイズ）が高くなりすぎたあまり、$a$と$b$の統計的関係がほとんどなくなり、そもそも問題として解く意味のない物になってしまいます。（無限の時間があっても解くことができなくなります。）
後ほど説明しますが、準同型暗号の安全性のベースとして利用する場合にも、$\sigma$が大きすぎると復号化の際に不都合が生じるので、その点からも$\sigma$は適切に設定される必要があります。
解く意味のあるレベルで困難性を持たせるには$n$の値を十分に大きくしたうえで$\sigma$の値を適切に設定することが必要です。そのような$\sigma$は$q$に比べて十分小さい範囲にとれることが知られています。
Ring-LWE問題に基づいた準同型暗号
Ring-LWE問題に基づいた準同型暗号について鍵生成、暗号化、復号化アルゴリズムを説明した後、具体例を用いて準同型性の確認を行います。
鍵生成アルゴリズム
\begin{align}
\begin{cases}
&m:m \in \mathbb{N}として十分大きく設定\\
&n:n = \phi (m)\\
&q:q \in \mathbb{N}かつ奇数として設定\\
&s: s\in \mathbb{Z} ^{(2)}[\xi] となるように係数を一様ランダムにとりsを設定\\
&a:a\in \mathbb{Z} ^{(q)}[\xi]となるように係数を一様ランダムにとりaを設定\\
&\sigma: \sigma >0としてqに比べて十分小さく設定\\
&e:e \in \mathbb{Z}[\xi]となるように係数をN(0, \sigma^2)からサンプルし最も近い整数に丸めeを設定\\
&b:b = [as +2 e]_qとして設定
\end{cases}
\end{align}
（$b$の構成の仕方だけはRing-LWEの説明の時と微妙に異なっていることに注意してください。）
$(a,b)$は公開鍵pk、$s$を秘密鍵skとします。パラメータが適切に設定されていれば、Ring-LWE問題の困難性より、公開鍵が与えられても秘密鍵を求めることが難しいことが保証されることになります。
暗号化アルゴリズム
$n$bit文字列である平文$m = (m_0 , m_1 ,\dots ,m_{n-1})$を暗号化する。（$m_i \in \{ 0, 1 \}$）である。
\begin{align}
\begin{cases}
&m:m = m_0 + m_1 \xi + \cdots + m_{n-1} \xi^{n-1}と多項式に変換する\\
&v: v\in \mathbb{Z} ^{(2)}[\xi] となるように係数を一様ランダムにとりvを設定\\
&e_0:N(0, \sigma^2)に従うようにサンプル\\
&e_1:N(0, \sigma^2)に従うようにサンプル\\
&c_0:c_0 = [bv +2 e_0 + m]_qとして設定\\
&c_1:c_1 = [av +2 e_1]_qとして設定\\
\end{cases}
\end{align}
このように求めた$c_0, c_1$に対して$c = (c_0 , c_1)$を暗号文とする。
ここで$v$はRing-LWE問題の$s$に相当する役割を果たします。$c_0$においては$2 e_0 + m$が、$c_1$においては$2 e_1$がノイズ$e$の役割を果たします。Ring-LWE問題の困難性より$(c_0, b)$が与えられても$(v, 2e_0 + m)$を求めることができません。また$(c_1, a)$が与えられても$(v, 2e_1)$を求めることができないので平文mは秘密鍵なしには復元することができないことが保証されます。
復号化アルゴリズム
秘密鍵$s$を用いて暗号文$(c_0, c_1)$から平文mを復元します。以下のような解き方で復元することができます。
m =[[c_0 - sc_1]_q ]_2
その後$m$の各係数を連結することで平文mが得られます。この正当性を以下で示します。
\begin{align}
c_0 - sc_1 &\equiv bv + 2e_0 + m -s(av + 2e_1)\ (\because c_0, c_1の構成の仕方)\\
&\equiv (b-as)v + 2e_0 + m - 2se_1\\
&\equiv 2ev + 2e_0 + m - 2se_1(\because bの構成の仕方)\\
&\equiv 2(ev + e_0 - se_1)+m\ (\text{mod}\ q)
\end{align}
ここで$q$に比べて$e, v, e_0, s, e_1, m$の係数は小さいです。よってその和の$2(ev + e_0 - se_1)+m$の係数も$q$に比べて小さいので
[c_0 - sc_1]_q = 2(ev + e_0 - se_1)+m
が成立します。さらに
[[c_0 - sc_1]_q]_2 = m
が成り立つので平文mを復元することができています。
準同型性の確認
準同型暗号とは
Enc(x) \bigoplus Enc(y) =_d Enc(x + y)\\
Enc(x) \bigotimes Enc(y) =_d Enc(x × y)
を満たす暗号$Enc$のことをいいます。$Dec$が復号化を表すとすると,この暗号は
Dec(Enc(x) \bigoplus Enc(y)) = x + y\\
Dec(Enc(x) \bigotimes Enc(y)) = x × y
が成立します。このことは平文を暗号化したもの同士を演算にかけたものは、元の平文の二項演算に等しいことを表しています。
ここでは鍵生成、暗号化、復号化アルゴリズムを具体例を用いて確認するとともに、この準同型性を確認します。
鍵生成から復号化までのアルゴリズムの確認
円の3分整数の場合を考えます。$\xi = -\frac{1}{2} + \frac{\sqrt{3}}{2}i$とします。平文$m = 11 \rightarrow 1 +\xi$と平文$m^{\prime} = 01 \rightarrow \xi$を暗号化し計算することを考えます。
\begin{align}
\begin{cases}
&q=65\\
&s=1 + \xi\\
&a=-19-8\xi\\
&\sigma = 2\\
&e = 1 -\xi\\
&b= [as + 2e]_{q} = -9-21\xi
\end{cases}
\end{align}
とパラメータを設定（またはサンプル）しておきます。
次に$m$に関係するパラメータを設定（またはサンプル）したうえで暗号文$c$を計算します。
\begin{align}
\begin{cases}
&v=1 + \xi\\
&e_0 = -1 +\xi\\
&e_1 = -\xi\\
&c_0= [bv + 2e_0 + m]_{65} = 11-6\xi\\
&c_1= [av + 2e_1]_{65} = -11-21\xi
\end{cases}
\end{align}
これにより暗号文$c =(c_0 , c_1)$を得ました。
次に$m^{\prime}$に関係するパラメータを設定（またはサンプル）したうえで暗号文$c^{\prime}$を計算します。
\begin{align}
\begin{cases}
&v^{\prime}= \xi\\
&e_0^{\prime} = \xi\\
&e_1^{\prime} = 2\\
&c_0^{\prime}= [bv^{\prime} + 2e_0^{\prime} + m^{\prime}]_{65} = 21+15\xi\\
&c_1^{\prime}= [av^{\prime} + 2e_1^{\prime}]_{65} = 12-11\xi
\end{cases}
\end{align}
同様に暗号文$c^{\prime} =(c_0^{\prime} , c_1^{\prime})$を得ました。復号化についても
\begin{align}
&[[c_0 - sc_1]_{65} ]_2 = [1 +5\xi ]_2 = 1 + \xi \rightarrow 11 = m\\
&[[c_0^{\prime} - sc_1^{\prime}]_{65} ]_2 = [-2 +3\xi ]_2 = \xi \rightarrow 01 = m^{\prime}\\
\end{align}
の通りに行えることが確認できます。
和に関する準同型性の確認とその正当性
暗号文$C = (c_0 + c_0^{\prime} , c_1 + c_1^{\prime})$を復号化して$m + m^{\prime}$のケタごとの足し算の結果に一致することを確認します。
\begin{align}
&[[(c_0 + c_0^{\prime}) - s(c_1 + c_1^{\prime})]_{65} ]_2 = [[(32+9\xi -(1+\xi)(1-32\xi))]_{65} ]_2 = [-1+8\xi]_2 = 1 \rightarrow 01 = m + m^{\prime}
\end{align}
この計算で実際に平文の和が計算できることを説明します。（先ほどの復号化の際と同様の流れで説明できます。）
\begin{align}
(c_0 + c_0^{\prime}) - s(c_1 + c_1^{\prime}) &\equiv (bv + 2e_0 + m) + (bv^{\prime} + 2e_0^{\prime} + m^{\prime})- s(av + 2e_1) - s(av^{\prime} + 2e_1^{\prime}) \\
&\equiv (b-as)v + (b-as)v^{\prime} + 2(e_0 +e_0^{\prime} -se_1 -se_1^{\prime}) + m +m^{\prime}\\
&\equiv 2(e_0 +e_0^{\prime} -se_1 -se_1^{\prime}) + m +m^{\prime}\ (\text{mod}\ q)
\end{align}
$q$に比べて$s, e_0, e_0 ^{\prime},e_1, e_1 ^{\prime}$の係数は小さいので
[(c_0 + c_0^{\prime}) - s(c_1 + c_1^{\prime})]_q = 2(e_0 +e_0^{\prime} -se_1 -se_1^{\prime}) + m +m^{\prime}
が成立します。さらに
[[(c_0 + c_0^{\prime}) - s(c_1 + c_1^{\prime})]_q]_2 = m +m^{\prime}
が成り立つので上のようなプロセスで平文の和を計算できます。
積に関する準同型性の確認
暗号化した状態で積の計算を行う際は少々工夫を施します。
（なぜこのような工夫を行う必要があるかについてはここでは説明しませんが、参考資料を確認していただけると詳しく載っています。）
現在暗号文$c =(c_0 , c_1),c^{\prime} = (c_0^{\prime} ,c_1^{\prime})$を得ている状態であるとします。
流れとしては暗号文$c =(c_0 , c_1)$から暗号文$d^{\prime \prime} = (d_0 ^{\prime \prime}, d_1 ^{\prime \prime})$を生成し、$d^{\prime \prime}$を復号することで平文の積を得るという流れをとります。
まず$c, c^{\prime}$から$d_0, d_1, d_2$を計算します。
\begin{align}
\begin{cases}
&d_0 = [c_0 c_0^{\prime}]_q\\
&d_1 = [c_1 c_0^{\prime} + c_0 c_1^{\prime}]_q\\
&d_2 = [-c_1 c_1^{\prime}]_q
\end{cases}
\end{align}
次に$P, A, B$および$d_0 ^{\prime}, d_1 ^{\prime}$を設定、計算します。
\begin{align}
\begin{cases}
&P:qと同程度の大きさの奇数に設定\\
&A:\mathbb{Z}^{(Pq)}[\xi]からランダムに設定\\
&B:B = [As -Ps^2 +2e]_{Pq}\\
&d_0 ^{\prime} = [Pd_0 + Bd_2]_{Pq}\\
&d_1 ^{\prime} = [Pd_1 + Ad_2]_{Pq}
\end{cases}
\end{align}
その後$\delta _1 , \delta _2$および$d_0 ^{\prime \prime}, d_1 ^{\prime \prime}$を設定、計算します。
\begin{align}
\begin{cases}
&\delta _0:d_0 ^{\prime} \equiv \delta _0 \ (\text{mod}\ P)かつ偶数となるようになるべく小さく設定\\
&\delta _1:d_1 ^{\prime} \equiv \delta _1 \ (\text{mod}\ P)かつ偶数となるようになるべく小さく設定\\
&d_0 ^{\prime \prime} = \left[\frac{d_0^{\prime} - \delta _0}{P}\right]_{q}\\
&d_1 ^{\prime \prime} = \left[\frac{d_1^{\prime} - \delta _1}{P}\right]_{q}
\end{cases}
\end{align}
最後に以下のような復号化を行うことで平文の積を得られます。
\begin{align}
& m \cdot m^{\prime} =[[d_0 ^{\prime \prime} - sd_1 ^{\prime \prime}]_{q} ]_2
\end{align}
この計算で実際に平文の和が計算できることを説明します。その際復号化アルゴリズムの節でもみたように暗号文$(c_0, c_1)$が平文mを暗号化している時、ある小さな円分整数$e$が存在して
c_0 -s c_1 \equiv m + 2e \ (\text{mod}\ q)\ \cdots \ (1)
となることを用います。
\begin{align}
(d_0 ^{\prime} - \delta_0) - s(d_1 ^{\prime } -\delta _1) &\equiv (Pd_0 + Bd_2) -s(Pd_1 + Ad_2) - \delta_0 + s \delta_1 \ (\because d_0 ^{\prime}, d_1 ^{\prime}の定義)\\
&\equiv(Pd_0 - sPd_1 ) + (B-As)d_2 - \delta_0 + s \delta_1 \\
&\equiv (Pd_0 - sPd_1 ) + (-Ps^2 +2e)d_2 - \delta_0 + s \delta_1 \ (\because B の定義)\\
&\equiv P(d_0 - sd_1 -s^2 d_2 )+2ed_2 - \delta_0 + s \delta_1 \\
&\equiv P(c_0 c_0^{\prime} - s(c_1 c_0^{\prime} + c_0 c_1^{\prime}) +s^2c_1 c_1^{\prime} )+2ed_2 - \delta_0 + s \delta_1 \ (\because d_0, d_1 ,d_2 の定義)\\
&\equiv P(c_0 -sc_1)(c_0^{\prime} - sc_1 ^{\prime})+2ed_2 - \delta_0 + s \delta_1 \\
&\equiv P(m+2e )(m^{\prime}+ 2e^{\prime})+2ed_2 - \delta_0 + s \delta_1\ (\because (1)) \\
&\equiv P(m m^{\prime} +2e m^{\prime}+ 2e^{\prime} m + 4ee^{\prime})+2ed_2 - \delta_0 + s \delta_1 \ (\text{mod}\ Pq)
\end{align}
よって両辺を$P$で割ると
\begin{align}
\frac{d_0^{\prime} - \delta _0}{P } -s\frac{d_1^{\prime} - \delta _1}{P} &\equiv m m^{\prime} +2e m^{\prime}+ 2e^{\prime} m + 4ee^{\prime} +\frac{2ed_2 -\delta_0 +s \delta _1}{P}\ (\text{mod}\ q)
\end{align}
$q$に比べて$2e m^{\prime}+ 2e^{\prime} m + 4ee^{\prime} +\frac{2ed_2 -\delta_0 +s \delta _1}{P}$の係数は小さいので、
\left[\frac{d_0^{\prime} - \delta _0}{P } -s\frac{d_1^{\prime} - \delta _1}{P}\right]_q =m m^{\prime} +2e m^{\prime}+ 2e^{\prime} m + 4ee^{\prime} +\frac{2ed_2 -\delta_0 +s \delta _1}{P}
が成立します。よって$\delta _0 ,\delta_1$が偶数であることに注意すると
[d_0 ^{\prime \prime} - sd_1 ^{\prime \prime}]_{q} ]_2 = \left[\left[\left[\frac{d_0^{\prime} - \delta _0}{P}\right]_{q} - s\left[\frac{d_1^{\prime} - \delta _1}{P}\right]_{q}\right]_{q} \right]_2 = \left[ \left[\frac{d_0^{\prime} - \delta _0}{P } -s\frac{d_1^{\prime} - \delta _1}{P}\right]_q \right] _2 = m\cdot m^{\prime}
がいえます。
具体例を用いた積に関する準同型性の確認
先ほどまでの数値例に対して
\begin{align}
\begin{cases}
&d_0 = [(11-6\xi)(21+15\xi)]_{65} = -4- \xi\\
&d_1 = [(-11-21\xi)(21+15\xi)+(11-6\xi)(12-11\xi)]_{65} = 20- 30\xi\\
&d_2 = [-(-11-21\xi)(12-11\xi)]_{65} = -27- 28\xi
\end{cases}
\end{align}
のように$d_0 , d_1 , d_2$を計算します。次に
\begin{align}
\begin{cases}
&P=67\\
&A=2116 + 1119\xi\\
&B = [(2116 + 1119\xi)(1+\xi)-67\xi +2(1-\xi)]_{4355} = 999 + 2047\xi\\
&d_0 ^{\prime} = [67(-4- \xi)+ ( 999 + 2047\xi)( -27- 28\xi)]_{4355} = -410 + 138\xi\\
&d_1 ^{\prime} = [67(20- 30\xi)+ ( 2116 + 1119\xi)( -27- 28\xi)]_{4355} = 1670 + 831\xi\\
\end{cases}
\end{align}
のように$d_0 ^{\prime},d_1 ^{\prime}$を計算します。
\begin{align}
\begin{cases}
&\delta _0= -8 +4\xi\\
&\delta _1= 62 -40\xi\\
&d_0 ^{\prime \prime} = \left[\frac{(-410 + 138\xi) - (-8 +4\xi)}{67}\right]_{65} = -6 +2\xi\\
&d_1 ^{\prime \prime} = \left[\frac{(1670 + 831\xi) - ( 62 -40\xi)}{67}\right]_{65} = 24+13\xi
\end{cases}
\end{align}
最後に復号化を行い平文$m, m^{\prime}$のケタ同士の積に一致することを確認します。
\begin{align}
&[[d_0 ^{\prime \prime} - sd_1 ^{\prime \prime}]_{65} ]_2 = [[17-22\xi]_{65} ]_2 = [17-22\xi]_2 = 1 \rightarrow 01 = m \cdot m^{\prime}
\end{align}
終わりに
Ring-LWE問題の困難性に基づく準同型暗号の鍵生成から復号化までのアルゴリズムとその準同型性の成立の確認を行いました。
より詳しく以下の資料に記載がありますので適宜参照していただけますと幸いです。
参考
有田正剛『イデアル格子暗号入門』
（記事作成のご許可をいただいています。）