勉強会の概要

資料: https://www.iisec.ac.jp/proc/vol0006/arita14.pdf
暗号の会社にいるので、格子暗号に関して、普段数学を触らないビジネスサイドの人間も理解できるように定性的理解と可視化を大切にしました
そのため数式の一般化は各自の努力にまかせて、円の3分整数(m=3)を用いて説明し概念を掴むことを目的とします
m=3を用いることで次元が2次元となり、実軸-虚軸の複素平面(2次元)にキレイにマッピングすることができます。m=3のとき(正確に言うとm=6も)のときにしか、次元を揃えたマッピングはできませんが、いったんこの特性を利用してマッピングします
今回は例題6の説明を担当します

これまでの流れ

例1
- 円分整数は格子を形成するよね (もっとも解像度が高いメモリと考えられ定規で言うとmmに相当)
- 円分整数の整数倍はイデアル格子を生成するよね (mmが10個でcmになるイメージ)
- この格子上の点は足し算と掛け算できるよね!
例4
- あるイデアル格子上の点に、円分整数$s_k$をかけると、他のイデアル格子上の点に移るけど、更にノイズを足すと、$s_k$を求めるのは、めっちゃ難しくなっちゃうよね。
- なんでかというとLWE問題になるから。これは耐量子性を持つよね
例5
- じゃーこのLWE問題の性質を使って暗号作っちゃおう！
- とりまー、鍵生成考えてみるかー
例6 (今日はココ)
- 鍵生成ができたから、この鍵を使って、平文を暗号化 / 復号化してみるぜ!

本日のゴール

イデアル格子における "4.円分整数を用いた準同型暗号の構成"において暗号化アルゴリズム, 復号アルゴリズムを理解する。具体的には以下のポイントを理解する。

データの暗号化は $c = (c_0, c_1)$と表さる
$c_0$は公開鍵の成分$b$をベースに平文$m$をノイズの中に埋め込む
$c_1$は公開鍵の成分$a$をベースに使う
復号化するとき、$c$, $s_k$を利用して、ノイズとメッセージだけを取り出し、$mod~2$を利用してノイズを削除する

最後に、例題6を手触り感をもって理解できればOK

0. 鍵生成 (前回の復習)

前回の資料を参考に鍵は作成済みとする。

秘密鍵

前回作成した秘密鍵を今回も利用しよう。$s_{k0}$, $s_{k1}$ は、0 or 1のどちらかである。2のあまりの世界とも考えられる。

s_k = s_{k0} + s_{k1}\zeta=1 + \zeta

公開鍵

前回作成した公開鍵を利用する。わかりやすさ重視で省略しているが、a, bは$mod~q$($q=65$)の世界、つまり65で割ったあまりの世界であることに注意する。

p_k = (a, b) = (a_0+a_1\zeta, as_k+2e)=(-19 - 8\zeta,-9 - 21\zeta)

$b$は$a$に秘密鍵を掛けて、イデアル格子上の別の点にワープさせて、そこからノイズ分ずらした形をしてることを思い出そう。

1. 暗号化アルゴリズム (m=3の円分整数のとき)

1.1. 平文の準備

上記で説明したように円の3分整数は$x_0 + x_1\zeta$と表せるが、$x_0$を1ビット目、$x_1$を2ビット目と考えると、どうやら円の3分整数は2ビットまでの表現力がありそうだ。

仮に平文を$m$とし、

1ビット目: $m_0$
2ビット目: $m_1$

とすると、平文は以下のように書ける

m = m_0 + m_1 \zeta

ここで具体的に $m_0=1$, $m_1=1$と11の平文を考えてみよう

m = 1 + \zeta

これで平文$m$が完成した。

1.2. 平文を暗号化しよう

ここからは、平文$m$を暗号化することを考えていこう。
暗号文を$c$とすると、公開鍵のときと同じように$c_0$と$c_1$の2成分で表すこととする。

c=(c_0, c_1)

ちなみに平文$m$は$c_0$の中に含まれている。$c_0$と$c_1$については以下で具体的に説明する。

1.2.1 小さい乱数vを生成

0か1しかでないサイコロをふって小さい乱数$v$を生成しよう。
$v$ももちろん円の3分整数 $x_0 + x_1\zeta$の形をしており、サイコロは2回ふって、例えば、$x_0=1$, $x_1=1$が出たとすると

v = 1 + \zeta

ちなみにこの$v$の役目は例え同じ平文と同じ公開鍵を使っても、同じ暗号文にならないようにするためである。もし同じであれば、平文と暗号文のルックアップテーブルを作られてしまうと、暗号文が解読されてしまう。

1.2.2 第1成分のc0を計算

c0用のノイズの生成

例5と同様にLWE問題になるよう、サイコロを振ってノイズを生成しよう。またこのサイコロは普通のサイコロではなく、平均0で標準偏差$\sigma$の正規分布$N(0, \sigma^2)$に従う確率分布をもつサイコロである。また出る目はいつでも整数になるようにしよう。

ノイズも円の3分整数 $x_0 + x_1\zeta$の形をしているのでサイコロを2回ふって$x_0=-1$, $x_1=1$が出たとすると

e_0 = -1 + \zeta \\

公開鍵の成分bを使ってc0の計算

次に公開鍵の成分$b$と$m$をノイズに紛れ込ませて$c_0$を生成する。第1成分 $c_0$は以下のように表現する。qはmやノイズと比較して十分に大きい数で $[~~~]_q$ は$q$で割ったあまりの世界$mod~q$をあらわしている。

c_0=[bv + 2e_0+m]_q

具体的な数値でc0を計算してみよう

\begin{align}
c_0&=(-9 - 21\zeta)(1 + \zeta) + 2(-1 + \zeta) + (1 + \zeta) \\
&=-9 - 9 \zeta - 21 \zeta  -21 {\zeta}^2 - 2 + 2 \zeta +1 + \zeta \\
&=-10 -27\zeta -21 (-1-\zeta) \\
&=11 - 6\zeta
\end{align}

今、$q=65$のため$mod~65$の世界でも同じ値になる。これで$c_0$が作成できた。

1.2.3 第2成分c1を計算

c1用のノイズの生成

先ほどと同様に、平均0で標準偏差$\sigma$の正規分布$N(0, \sigma^2)$に従う確率分布をもつサイコロを2回振って円の3分整数のノイズを生成しよう。仮に0と-1がでたとすると、以下のように書ける。

e_1 = -\zeta

公開鍵の成分aを使ってc1を生成

$c_1$は以下のように表現できる

c_1=[av + 2e_1]_q

c1を具体的な値で計算してみよう

\begin{align}
c_1&=(-19 - 8\zeta)(1 + \zeta)-2\zeta \\
&=-19 - 19\zeta - 8\zeta - 8{\zeta}^2 - 2\zeta \\
&=-19 - 29 \zeta - 8(-1-\zeta) \\
&=-11 - 21 \zeta
\end{align}

今、$q=65$のため$mod~65$の世界でも同じ値になる。これで$c_1$が作成できた。

1.2.4 暗号文の完成

これで暗号文が完成した

c=(c_0, c_1)=(11 - 6\zeta, -11 - 21 \zeta)

ここまでの秘密鍵, 公開鍵と暗号文の関係を図にすると

更に攻撃者の気分になると、公開情報から非公開情報を求める必要がある。公開情報の4つのベクトルをどういじっても、非公開情報は求められない(LWE問題)

公開情報: $a$, $b$, $c_0$, $c_1$
非公開情報: 平文+ノイズ

2. 復号アルゴリズム (m=3の円分整数)

2.1. 必要な情報の準備

復号化に関して、今、手元に秘密鍵と暗号文の2つの情報を用意しよう

秘密鍵(復号鍵): $s_k = 1 + \zeta$
暗号文: $c=(c_0, c_1)=(11 - 6\zeta, -11 - 21 \zeta)$

2.2. 暗号文を復号化しよう

計算の流れとしてはシンプルである。

STEP1: 秘密鍵を利用して$c_0-s_kc_1$ を計算
STEP2: 得られた結果に対し$mod~2$(2で割ったあまり)を計算しノイズが除去！！

ポイントは STEP2であり、これまでノイズは2倍してきたことを思い出そう。$mod~2$をとることでこのノイズは消えてしまうのである。Dragon bollの悟天の名ゼリフ「消えてなくなれ!!!!」である例えば ...

[2e]_2=0

2で割れるようにしているのでいつでもノイズは割り切れてゼロになる！すばらしー

実際の復号化の式は以下のように$mod~q$($q$で割ったあまりの世界)も入りこんでいるが、$q$は$m$やこれまで乗っけたノイズに比べて十分に大きいため、実際の計算上は無視できることを心の中にとどめておこう。

m=\left[\left[c_0-s_kc_1\right]_q\right]_2=\left[\left[STEP１の計算\right]_q\right]_2

2.2.1. STEP1:秘密鍵の利用

秘密鍵を使って平文とノイズだけにする(公開鍵, 秘密鍵の情報をキャンセル)

まずはSTEP1の$c_0-s_kc_1$から見ていこう

\begin{align}
c_0-s_kc_1&=bv+2e_0+m-s_k(av+2e_1) \\
&=(as_k+2e)v+2e_0+m-s_k(av+2e_1) \\
&=as_kv+2ev + 2e_0 + m - as_kv-2s_ke_1 \\
&=m + 2(ev+e_0-s_ke_1)
\end{align}

ここで得られた値は、$a$に関連する情報、イデアル格子の情報は無くなっており、平文とノイズのみになっていることに注目しよう！

実際に計算して平文とノイズのみにしてみよう

\begin{align}
c_0-s_kc_1 &= 11 - 6\zeta - (1 + \zeta)(-11 - 21 \zeta) \\
&=11 - 6\zeta + 11 + 21 \zeta + 11\zeta + 21{\zeta}^2 \\
&=22 + 26\zeta + 21(-1-\zeta) \\ 
&=22 + 26\zeta + 21(-1-\zeta) \\ 
&=1 + 5\zeta
\end{align}

ちなみに...

$m$は0か1, ノイズも$q$に比べて十分に小さいので$mod~q$をとってもいつでも同じ値が返ってくる。そのためこの工程は計算していない。

\left[m + 2(ev+e_0-s_ke_1)\right]_q = m + 2(ev+e_0-s_ke_1)

2.2.1. STEP2: mod2によるノイズの除去

次にSTEP2の$mod~2$を取ってやると

\left[m + 2(ev+e_0-s_ke_1)\right]_2 = m

すばらしーノイズが消えた！！

では実際計算してみよう。1を2で割ったあまりは1、また5を2で割ったあまりは1であることに注意しよう。

\left[m + 2(ev+e_0-s_ke_1)\right]_2 = \left[1 + 5\zeta \right]_2 = 1+\zeta

2.2.3. 平文と同じになっていることを確認してみよう

平文を思い出すと、$m=(m_0, m_1)=(1,1)$であり、$m$も円の3分整数の形をしているので、

m = m_0 + m_1 \zeta = 1+\zeta

ちゃんと、復号化された値が、平文と同じになっていることを確認できた。

考え方

Q&A

秘密鍵って何やってんの? なんでc0-sk*c1を実行するの？

$a$, $s_k$, $v$ などの情報を $c_0-s_kc_1$ を行うことでキャンセルできるから。秘密鍵$s_k$はこの役目を負う
- この時点でイデアル格子の世界$a$からは開放されていますー
- ノイズ$2ev$の中に$v$がありますが、これもノイズでありノイズ処理で消えます
$sk$と使って得られるものは平文+ノイズであり、ノイズの削除には$s_k$は寄与しません!

じゃー公開鍵って何やってんの？

俺々円分整数 $a$でイデアル格子作ってるよ!
- これに円分整数掛けてもイデアル格子上の点にワープするから、計算上都合が良いんだよ
$b$は平文を乗っけるためのベースだよ
- $a$を$s_k$を掛けてイデアル格子上のある点にワープさせて、そこにノイズを乗っけて、ちょいとずらしたよ。これでLWE問題だよ
- 平文はこのノイズの中に紛れさせるんだよ
- でもね、この$b$に直接平文を乗っけると、選択平文攻撃を受ける🦆(カモ)なんです。そう🦆です。そのため次で説明する$v$を使うんです

乱数vの必要性は？

今のところ、結論として$v$いらないんじゃねーになってます。
選択平文攻撃のために$v$を使っているという議論も勉強会ででたが、ノイズを乗っけている段階で、それは避けられている。ckksとか見ても$v$は使われておらず、オリジナルの文献が$v$を使っており、その名残では?という結論になった。

もう一度振り返る全体の流れ

暗号化プロセス

公開鍵を構成する俺々ベクトル$a$を選んでイデアル格子を作るよ
秘密鍵$s_k$に$a$をかけることにより、$a$が作る格子(イデアル格子)の何処かにワープするよ！
$a$とワープ先の情報$s_ka$があると連立方程式で$s_k$が求まっちゃう。これでは暗号には使えねーなー
そこで、ノイズを乗っけることで、連立方程式を解けなくしちゃうよ。人はこれをLWE問題と呼ぶよ!
このノイズを乗っけたベクトルを$b$としたよ
乱数$v$を作って、$b$をこの$v$で飛ばして、さらにノイズ乗っけて、その中に平文隠しちゃったよ。これが$c_0$だよ
秘密鍵$s_k$があれば復号化できるように$a$も同じく$v$で飛ばしておくよ。これも念の為ノイズ乗っけちゃうよ。これが$c_1$だよ
ここで注意する点が一つだけあるよ。ノイズは全部2倍してね！復号化プロセスでこれが重要になるんだよ！

復号化プロセス

秘密鍵$s_k$を使って$s_kc_1$を計算するよ
次に$c_0-s_kc_1$を計算するよ。何でかというと、これを計算することで、$a$, $s_k$, $v$の情報をキャンセルすることができるんです！残りはノイズ+平文の情報なんです
ノイズに紛れ込んでいる$v$は心配しないで。これもノイズの一部であり、次の工程で消せます
ノイズ+平文の情報から平文のみを取り出すよ。ノイズは全部2倍したことを思い出して！つまり2で割ってそのあまりをとると、ノイズが消えるよ！