今回からいよいよ本題って感じです．Ring-LWE問題を紹介し，それに基づく準同型暗号を解説します．
全３回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 1の3乗根
- 3分整数
- p分整数
- m分整数
- イデアル
- 衝突困難関数とSVP
第1.5回
- 記号の整理
- 衝突困難関数の構成
- 衝突困難関数の簡単な例
- 構成の証明の方針
- 構成の正当性の証明
第２回
- 記号の整理
- 準同型暗号とは
- Ring-LWE問題
- Ring-LWE問題の具体例
- Ring-LWE問題を使った準同型暗号
- Ring-LWE問題を使った準同型暗号の具体例
第３回
今回は第２回です．いよいよ準同型暗号の話に入っていきます．
具体的な内容としては，次のようになります:
- 記号の整理
- 準同型暗号とは
- Ring-LWE問題
- Ring-LWE問題の具体例
- Ring-LWE問題を使った準同型暗号
- Ring-LWE問題を使った準同型暗号の具体例
記号の整理
＊この内容は第1.5回と同じです
論文とは違うものもあるしれませんが，数学的に一般的だと思われる方を採用しています．
以下では，正整数 m に対して，n = \phi(m) としています．
\bullet [a, b] : a 以上 b 以下の実数からなる区間（a 以上 b 以下の実数全体）
\bullet (a, b] : a より大きく b 以下の実数からなる区間（a より大きく b 以下の実数全体）
\bullet a \equiv b \ (\mathrm{mod} \ n) : a を n で割った余りが b
\bullet a \ \mathrm{mod} \ n : a を n で割った余りで0以上 n - 1 以下の値で取る，a が円分整数の場合は，各係数に対して \mathrm{mod} を取る
\bullet [a]_n : a を n で割った余りで - \frac{n}{2} より大きく \frac{n}{2} 以下の値で取る，a が円分整数の場合は，各係数に対して []_n を取る
\bullet \mathbb{Z} : 整数全体の集合（有理整数環）
\bullet \mathbb{Z} / p \mathbb{Z} = \{0, 1, \cdots, p - 1 \}
\bullet \displaystyle \mathbb{Z}^{(p)} = \left( - \frac{p}{2}, \frac{p}{2} \right] \bigcap \mathbb{Z}
\bullet \mathbb{Z}[\zeta_m] = \mathbb{Z} + \mathbb{Z} \zeta_m + \cdots + \mathbb{Z} \zeta_m^{n - 1} = \{ a_0 + a_1 \zeta_m + \cdots + a_{n - 1} \zeta_m^{n - 1} \ | \ a_0, a_1, \cdots, a_{n - 1} \in \mathbb{Z} \}
\bullet (\mathbb{Z} / p \mathbb{Z})[\zeta_m] = (\mathbb{Z} / p \mathbb{Z}) + (\mathbb{Z} / p \mathbb{Z}) \zeta_m + \cdots + (\mathbb{Z} / p \mathbb{Z}) \zeta_m^{n - 1} = \{ a_0 + a_1 \zeta_m + \cdots + a_{n - 1} \zeta_m^{n - 1} \ | \ a_0, a_1, \cdots, a_{n - 1} \in \mathbb{Z} / p \mathbb{Z} \}
\bullet \mathbb{Z}^{(p)}[\zeta_m] = \mathbb{Z}^{(p)} + \mathbb{Z}^{(p)} \zeta_m + \cdots + \mathbb{Z}^{(p)} \zeta_m^{n - 1} = \{ a_0 + a_1 \zeta_m + \cdots + a_{n - 1} \zeta_m^{n - 1} \ | \ a_0, a_1, \cdots, a_{n - 1} \in \mathbb{Z}^{(p)} \}
\bullet I_g = \mathbb{Z} g + \mathbb{Z} g \zeta_m + \cdots + \mathbb{Z} g \zeta_m^{n - 1} = \{ a_0 g + a_1 g \zeta_m + \cdots + a_{n - 1} g \zeta_m^{n - 1} \ | \ a_0, a_1, \cdots, a_{n - 1} \in \mathbb{Z}^{(p)} \}
具体例を解説します．
まず，[a, b], \ (a, b] は共に集合です．5 \in [3, 5], \ 5 \in (3, 5] や 3 \in [3, 5] は成り立ちますが，3 \notin (3, 5] です．
次に 7 \equiv 3 \equiv -1 \ (\mathrm{mod} \ 4) などが成り立ちます．余りは負の数にも定義されることに注意してください．
ただし，7 \ \mathrm{mod} \ 4 と書いたら，この値は 3 と一意に定まります．これは，7を4で割った余りのなかで，0以上3以下のものは3しかないからです．また，円分整数 -6 + 5 \zeta_3 \ \mathrm{mod} \ 4 = 2 + \zeta_3 については，各係数について \mathrm{mod} を取っています（そして，あまりの範囲も制限している）．
同様に，[7]_4 と書いたら，この値は -1 と一意に定まります．これは，7を4で割った余りの中で，-1以上2以下のものは-1しかないからです．また，円分整数 [-6 + 5 \zeta_3]_4 = 2 + \zeta_3 については，各係数について []_4 を取っています（そして，あまりの範囲も制限している）．
p としては，素数を想定することが多いのですが，例えば，p = 11 なら，\mathbb{Z} / 11 \mathbb{Z} = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} ですし，\mathbb{Z}^{(11)} = \{ -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 \} となります．
また，例えば m = 3 なら n = \phi(m) = 2 なので，
-2 + 3 \zeta_3 \in \mathbb{Z}[\zeta_3], 9 + 3 \zeta_3 \in (\mathbb{Z} / 11 \mathbb{Z})[\zeta_3], -2 + 3 \zeta_3 \in \mathbb{Z}^{(11)}[\zeta_3], -2 g + 3 g \zeta_3 \in I_g
となります．
準同型暗号とは
平たくには，準同型暗号とは，「暗号文同士の足し算（掛け算）を復号すると，対応する平文同士の足し算（掛け算）になっている」ような公開鍵暗号方式のことです．
ここでは，まず公開鍵暗号方式の定義から振り返ってみます．定義だけ見ると難しく感じるかもしれませんが，RSA暗号とかElgamal暗号などを知っている方なら，具体例を想像しながら確認すると言わんとすることが分かると思います．
\underline{\mathrm{Def(公開鍵暗号方式)}}
公開鍵暗号方式とは，次の3つ組のアルゴリズム(KeyGen, Encrypt, Decrypt)のこと:
\bullet 鍵生成アルゴリズム KeyGen(1^n)
セキュリティパラメタ 1^n を入力として受け取り，公開鍵 pk と，それに対応する秘密鍵 sk のペア (pk, sk) を出力するアルゴリズム
\bullet 暗号化アルゴリズム Encrypt(pk, \mu)
公開鍵 pk と平文 \mu を入力として受け取り，暗号文 c を出力するアルゴリズム
\bullet 復号アルゴリズム Decrypt(sk, c)
秘密鍵 sk と暗号文 c を入力として受け取り，平文 \mu か，\perp（失敗） を出力するアルゴリズム
ここで，セキュリティパラメタ n は，鍵の長さに関する値で，任意の n について，KeyGen によって出力される任意の (pk, sk) について，メッセージが平文空間から入力されているなら，Decrypt(sk, Encyrpt(pk, \mu)) = \mu が常に成り立つ．
準同型暗号は，上記の公開鍵暗号方式の具体例と見ることができます．「準同型」の由来はおそらく，環準同型でしょう．
環準同型
\underline{\mathrm{Def(環準同型)}}
R, R^{\prime} を環とする．f : R \rightarrow R^{\prime} が次の条件を満たすとき，f を環準同型であるという．
(i) f(1) = 1
(ii) f(x + y) = f(x) + f(y)
(iii) f(x \cdot y) = f(x) \cdot f(y)
Ring-LWE問題
初めに定義を示します．
\underline{\mathrm{Def(Ring-LWE問題)}}
正整数 m を取って，n = \phi(m) とする．また，正整数 q を取る．
次に，s \leftarrow \mathbb{Z}^{(2)}[\zeta_m], \ a \leftarrow \mathbb{Z}^{(q)}[\zeta_m] を取る．
また，正の実数 \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 を構成する．
上記を用いて，b = [a s + e]_q \ \mathrm{in} \ \mathbb{Z}^{(q)}[\zeta_m] を計算する．
このとき，(a, b) が与えられたときに，s を求めよ．
Ring-LWE問題は，LWE問題の多項式版と見なせます．LWE問題の解説となぜLWE問題が難しいのかの直感的な説明は プログラマブルブートストラップの原著論文を理解する回 2/4「TLWEとTRLWE」 に書いています．
Ring-LWE問題の具体例
m = 3, q = 65 の場合で考えます．このとき，n = \phi(m) = 2, \ \zeta_3 = \frac{-1 + \sqrt{-3}}{2} です（何回も出てきているな・・・）．
まず，s, a をそれぞれランダムに \mathbb{Z}^{(2)}[\zeta_3], \ \mathbb{Z}^{(65)}[\zeta_3] から選びます．この結果を s = \zeta_3 + 1, \ a = - 8 \zeta_3 - 19 とします．
次に \sigma = 4 としたとき，S_0 = 1, \ S_1 = - 1 だったとします．つまり，e = - \zeta_3 + 1 です．
このとき，b = [as + e]_q = [(- 8 \zeta_3 - 19)(\zeta_3 + 1) + (- \zeta_3 + 1)]_{65} = [- 27 \zeta_3 - 19 - 8 (- \zeta_3 - 1) + (- \zeta_3 + 1)]_{65} = [-20 \zeta_3 - 10]_{65} = - 20 \zeta_3 - 10 です．
Ring-LWE問題を使った準同型暗号
早速定義から入りましょう．
\underline{\mathrm{Def(Ring-LWE問題を使った準同型暗号)}}
次の3つのアルゴリズムの組からなる公開鍵暗号方式を考える:
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] を出力する．
初めに正整数のパラメタ m を選択しているのに，その後に平文の文字列と円分整数でも m を使用するのはちょっとキツイなと・・・．
\bullet 復号がきちんとできているか（correctness）
\bullet KeyGenとEncryptでの O(\log |q|) の意味
の２つについて解説します．
\underline{\mathrm{correctness}}
以下では，\mathbb{Z}^{(q)}[\zeta_m] での議論としても良いのですが，今回（と次回）はきちんと議論します．
まず，KeyGen で b を求める部分ですが，b = [a s + 2 e]_q \ \mathrm{in} \ \mathbb{Z}^{(q)}[\zeta_m] と合同式を用いた構成になっているので，ある b_0, b_1, \cdots, b_{n - 1} \in \mathbb{Z}^{(q)} を使って，
\begin{align*}
b = a s + 2 e + (q b_{n - 1} \zeta_m^{n - 1} + \cdots + q b_1 \zeta_m + q b_0)
\end{align*}
と表すことができます．なんですが，一々こう書くのは面倒なので，b_{q neg} = q b_{n - 1} \zeta_m^{n - 1} + \cdots + q b_1 \zeta_m + q b_0 と表すことにします．b_{q neg} の意味は，\mathbb{Z}^{(q)}[\zeta_m] で無視できる（negligible）だと思ってください．
同様に，Encrypt で c_0, c_1 を求める部分ですが，こちらもある c_{0, 0}, c_{0, 1}, \cdots, c_{0, n - 1}, c_{1, 0}, c_{1, 1}, \cdots, c_{1, n - 1} \in \mathbb{Z}^{(q)} を使って，
\begin{align*}
c_0 & = b v + 2 e_0 + p + (q c_{0, n - 1} \zeta_m^{n - 1} + \cdots + q c_{0, 1} \zeta_m + q c_{0, 0}) \\
c_1 & = a v + 2 e_1 + (q c_{1, n - 1} \zeta_m^{n - 1} + \cdots + q c_{1, 1} \zeta_m + q c_{1, 0})
\end{align*}
とします．ここでも 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} の記号を使うことにします．
まとめると，b = a s + 2 e + b_{q neg} ですし，c_0 = b v + 2 e_0 + p + c_{0 q neg} や c_1 = a v + 2 e_1 + c_{1 q neg} が（通常の多項式の意味で）成り立っていることになります．
では，ここで Decrypt を見てみると，
\begin{align*}
pt
& = c_0 - s c_1 \\
& = (b v + 2 e_0 + p + c_{0 q neg}) - s (a v + 2 e_1 + c_{1 q neg}) \\
& = (b - s a) v + 2 (e_0 - s e_1) + (c_{0 q neg} - s c_{1 q neg}) + p
\end{align*}
となります．ここで，b = a s + 2 e + b_{q neg} でしたので，b - s a = 2 e + b_{q neg} ですから，
\begin{align*}
pt
& = (b - s a) v + 2 (e_0 - s e_1) + (c_{0 q neg} - s c_{1 q neg}) + p \\
& = (2 e + b_{q neg}) 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) + (c_{0 q neg} - s c_{1 q neg} + b_{q neg} v) + p
\end{align*}
となります．ここで，2 (e v + e_0 - s e_1) は \mathbb{Z}^{(2)}[\zeta_m] で無視できますし，(c_{0 q neg} - s c_{1 q neg} + b_{q neg} v) は \mathbb{Z}^{(q)}[\zeta_m] で無視できる部分ですので，ここから，pt = p を得ることができます．
＊厳密には論理の飛躍があるので，それは次の \underline{\log |q| について} を確認してください
なお，上の議論から分かることですが，\mathbb{Z}^{(q)}[\zeta_m] で考えてから \mathbb{Z}^{(2)}[\zeta_m] で考えるのと，その逆ででも，今回は同じ結果が得られます．
\underline{\log |q| について}
論文でいう「小さい」に相当する部分です．これは，|q| が \log |q| よりも「小さい」という意味です．
なぜこの条件を課す必要があったのかというと，復号の部分で，
\begin{align*}
pt = 2 (e v + e_0 - s e_1) + (c_{0 q neg} - s c_{1 q neg} + b_{q neg} v) + p
\end{align*}
という式が少し厄介だからです．もちろん，ここから
\begin{align*}
pt \equiv 2 (e v + e_0 - s e_1) + p \ \mathrm{mod} \ q
\end{align*}
が成り立ちます（各係数に対して，\mathrm{mod} \ q です）．しかし，この式は，pt と 2 (e v + e_0 - s e_1) + p の各係数を q で割った余りが等しい，ということしか主張していません．
[[2 (e v + e_0 - s e_1) + p]_q]_2 = pt まで言うには，2 (e v + e_0 - s e_1) + p （の各係数）が \mathrm{mod} \ q ではなく厳密に \displaystyle \left[ - \frac{q}{2}, \frac{q}{2} \right] の範囲に収まっている必要があります．
なぜなら，その範囲に収まっていないとすると，pt の値が一意には定まらないからです．
簡単のために例えば，8 \equiv 68 + 6 \ \mathrm{mod} \ 64 ですが，今は 68, 6 共に未知なので，一意には求められないわけです．
＊じゃあ 2 (e v + e_0 - s e_1) の部分を \displaystyle \left[ - \frac{q}{2}, \frac{q}{2} \right] に制限してから計算すればいいじゃん，と思うかもしれません．そうすると，確かに[2 (e v + e_0 - s e_1)]_q （の各係数）は \displaystyle \left[ - \frac{q}{2}, \frac{q}{2} \right] に収まりますが， [2 (e v + e_0 - s e_1)]_q （の各係数）が偶数になるかどうかまでは保障されません．特に q が奇数の場合はめんどくさいと思います．
逆に，2 (e v + e_0 - s e_1) + p （の各係数）が \displaystyle \left[ - \frac{q}{2}, \frac{q}{2} \right] の範囲に収まっているなら，上の例だと，8 \equiv 2 + 6 \ \mathrm{mod} \ 64 となるので，後は，\mathrm{mod} \ 2 で 2 の部分を消せばいいことになります．
そして，2 (e v + e_0 - s e_1) + p が小さい，というのは 2 (e v + e_0 - s e_1) + p の長さが \log |q| 程度であればいいわけです．
よって，e, v, e_0, s, e_1 （の各係数）は \log |q| 程度で，これを「小さい」と表記しています．
なお，補足ですが，a の長さが |q| なのは，b の長さを |q| にするためです．a, b は公開鍵なので，そこそこの鍵長である必要があります．そこで b = [as + 2e]_q で求めるのでしたから，a の長さが |q| という条件があれば，この求め方から b の長さも |q| と分かります．
Ring-LWE問題を使った準同型暗号の具体例
今回の「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
\end{align*}
とします．
KeyGen
\begin{align*}
b & = [as + 2e]_{q} \\
& = [(-8 \zeta_3 - 19)(\zeta_3 + 1) + 2(- \zeta_3 + 1)]_{65} \\
& = [- 27 \zeta_3 - 19 - 8 (- \zeta_3 - 1) + (- 2 \zeta_3 + 1)]_{65} \\
& = [-21 \zeta_3 - 9]_{65} \\
& = - 21 \zeta_3 - 9
\end{align*}
です．
よって，秘密鍵 sk は sk = s = \zeta_3 + 1 であり，公開鍵 pk は pk = (a, b) = (-19 - 8 \zeta_3, - 21 \zeta_3 - 9) です．
秘密鍵を使って，復元できるかを確認してみます．
\begin{align*}
b - as & = (- 21 \zeta_3 - 9) - (-19 - 8 \zeta_3) (1 + \zeta_3) \\
& = (- 21 \zeta_3 - 9) - (-19 - 27 \zeta_3 - 8 \zeta_3^2) \\
& = (- 21 \zeta_3 - 9) - (-19 - 27 \zeta_3 - 8 (- \zeta_3 - 1)) \\
& = (- 21 \zeta_3 - 9) - (- 19 \zeta_3 - 11) \\
& = - 2 \zeta_3 + 2
\end{align*}
ですから，[b - a s]_{q} = [- 2 \zeta_3 + 2]_{65} = - 2 \zeta_3 + 2 ゆえ，確かに 2e = - 2 \zeta_3 + 2 と一致しています．
Encrypt・Decrypt
n = 2 ですから，平文として，pt = 11 を \mathbb{B}^2 から取ります．よって，p = 1 + \zeta_3 です．
このとき，v = \zeta_3 + 1, e_0 = \zeta_3 - 1, e_1 = - \zeta_3 とします．
すると，
\begin{align*}
c_0 & = [b v + 2 e_0 + p]_q \\
& = [(- 21 \zeta_3 - 9)(\zeta_3 + 1) + 2(\zeta_3 - 1) + (\zeta_3 + 1)]_{65} \\
& = [(- 21 \zeta_3^2 - 30 \zeta_3 - 9) + (2 \zeta_3 - 2) + (\zeta_3 + 1)]_{65} \\
& = [- 21 \zeta_3^2 - 27 \zeta_3 - 10]_{65} \\
& = [- 21 (- \zeta_3 - 1) - 27 \zeta_3 - 10]_{65} \\
& = [-6 \zeta_3 + 11]_{65} \\
& = -6 \zeta_3 + 11 \\
c_1 & = [a v + 2 e_1]_{q} \\
& = [(- 8 \zeta_3 - 19)(\zeta_3 + 1) + 2 (- \zeta_3)]_{65} \\
& = [(- 8 \zeta_3^2 - 27 \zeta_3 - 19) - 2 \zeta_3]_{65} \\
& = [- 8 (- \zeta_3 - 1) - 27 \zeta_3 - 19 - 2 \zeta_3]_{65} \\
& = [- 21 \zeta_3 - 11]_{65} \\
& = - 21 \zeta_3 - 11
\end{align*}
です．よって暗号文 c = (c_0, c_1) は c = (-6 \zeta_3 + 11, - 21 \zeta_3 - 11) です．
ここから，秘密鍵 s = \zeta_3 + 1 を使って，c から p を復号してみます．
\begin{align*}
[[c_0 - s c_1]_q]_2 & = [[(-6 \zeta_3 + 11) - (\zeta_3 + 1)(- 21 \zeta_3 - 11)]_{65}]_2 \\
& = [[(-6 \zeta_3 + 11) - (- 21 \zeta_3^2 - 32 \zeta_3 - 11)]_{65}]_2 \\
& = [[21 \zeta_3^2 + 26 \zeta + 22]_{65}]_2 \\
& = [[21 (- \zeta_3 - 1) + 26 \zeta + 22]_{65}]_2 \\
& = [[5 \zeta_3 + 1]_{65}]_2 \\
& = [5 \zeta_3 + 1]_2 \\
& = \zeta_3 + 1
\end{align*}
となり，p = \zeta_3 + 1 でしたから，無事に復号できました．
以下では，もう１つの例として，鍵は固定（pk, sk は固定）して，別の平文で具体例を見てみます．
平文として，{pt}^{\prime} = 01 を \mathbb{B}^2 から取ります．よって，p^{\prime} = \zeta_3 です．
このとき，v^{\prime} = \zeta_3, e_0^{\prime} = \zeta_3, e_1^{\prime} = 2 とします．
すると，
\begin{align*}
c_0^{\prime} & = [b v^{\prime} + 2 e_0^{\prime} + p^{\prime}]_q \\
& = [(- 21 \zeta_3 - 9)(\zeta_3) + 2(\zeta_3) + (\zeta_3)]_{65} \\
& = [(- 21 \zeta_3^2 - 9 \zeta_3) + 2 \zeta_3 + \zeta_3]_{65} \\
& = [- 21 \zeta_3^2 - 6 \zeta_3]_{65} \\
& = [- 21 (- \zeta_3 - 1) - 6 \zeta_3]_{65} \\
& = [15 \zeta_3 + 21]_{65} \\
& = 15 \zeta_3 + 21 \\
c_1^{\prime} & = [a v^{\prime} + 2 e_1^{\prime}]_{q} \\
& = [(- 8 \zeta_3 - 19)(\zeta_3) + 2 (2)]_{65} \\
& = [(- 8 \zeta_3^2 - 19 \zeta_3) + 4]_{65} \\
& = [- 8 (- \zeta_3 - 1) - 19 \zeta_3 + 4]_{65} \\
& = [- 11 \zeta_3 + 12]_{65} \\
& = - 11 \zeta_3 + 12
\end{align*}
です．よって暗号文 c^{\prime} = (c_0^{\prime}, c_1^{\prime}) は c^{\prime} = (15 \zeta_3 + 21, - 11 \zeta_3 + 12) です．
ここから，秘密鍵 s = \zeta_3 + 1 を使って，c^{\prime} から p^{\prime} を復号してみます．
\begin{align*}
[[c_0^{\prime} - s c_1^{\prime}]_q]_2 & = [[(15 \zeta_3 + 21) - (\zeta_3 + 1)(- 11 \zeta_3 + 12)]_{65}]_2 \\
& = [[(15 \zeta_3 + 21) - (- 11 \zeta_3^2 + \zeta_3 + 12)]_{65}]_2 \\
& = [[11 \zeta_3^2 + 14 \zeta + 9]_{65}]_2 \\
& = [[11 (- \zeta_3 - 1) + 14 \zeta + 9]_{65}]_2 \\
& = [[3 \zeta_3 - 2]_{65}]_2 \\
& = [3 \zeta_3 - 2]_2 \\
& = \zeta_3
\end{align*}
となり，p^{\prime} = \zeta_3 でしたから，こちらも無事に復号できました．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion