【イデアル格子勉強会 #3】準同型暗号の鍵生成アルゴリズムをシンプルな条件で理解しよう

勉強会の概要

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

これまでの流れ

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

本日のゴール

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

• 秘密鍵の作り方
• 公開鍵の作り方とノイズの概念
• 秘密鍵が分かったらLWE問題を構成するノイズを計算できる(なぜ秘密鍵で複合化できるかの頭出しになっている)

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

資料の説明

まずは円の3分整数の復習

円の3当分($m=3$) するとき $\theta = \frac{2 \pi}{m} = \frac{2 \pi}{3} (= 120^{\circ})$ となる。オイラーの公式で得られる値を$\zeta$とすると以下のようにかける

\begin{eqnarray*}
\zeta = e^{i\theta} &=& \cos \theta + i\sin \theta \\
&=& \cos \left(\frac{2\pi}{3}\right) + i\sin \left(\frac{2\pi}{3}\right) \\
&=& -\frac{1}{2} + i\frac{\sqrt 3}{2}
\end{eqnarray*}

$\zeta$ の(一般次数) 多項式 $f(\zeta)$ は、$\zeta^2 = −ζ − 1$ であることを利用すれば、必ず $\zeta$ の一次式 $x_0 + x_1\zeta$ に変形することができる。

$x_1$, $x_2$ を整数とすると円の3分整数は以下のように定義できる。

x_0 + x_1\zeta

あとイデアル格子の意味ももう一度思い出そう！

鍵生成アルゴリズム (m=3の円分整数)

秘密鍵の作成

秘密鍵$s_k$とし、$x_0$と$x_1$に$0$もしくは$1$の乱数を入れて作成する

• $x_0 \implies 0 ~~ or ~~ 1$
• $x_1 \implies 0 ~~ or ~~ 1$

例えば、0か1しかでないサイコロを降って$x_0=1$と$x_1=1$になったとすると秘密鍵$s_k$は

s_k = 1 + \zeta

公開鍵の作成

公開鍵を$p_k$とすると秘密鍵と異なる点は、以下で説明する$a$と$b$の2つが必要になる点だ。これが公開鍵となる。よって

p_k = (a,b)

aは俺々のジャイアン円分整数

$s_k$のときと比較て十分に大きい円分整数$a$をつくる。これを俺々ジャイアン円分整数と呼ぼう！つまり$x_0$と$x_1$に大きめの乱数をいれて俺々のジャイアン$a$を作る。

仮に今サイコロを降って、$x_0=-19$と$x_1=-8$とすると俺々の$a$は

a = -19 - 8\zeta

いったんここまでを図示してみよう。aがイデアル格子を形成していることが分かる.

bを作るにはノイズが必要(なぜならLWE問題にするため)

bを作るにはノイズが必要なので、ここでノイズを作ってしまおう。

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

以下は標準偏差を1, 2, 3ときの正規分布をそれぞれ図示した。例えば$\sigma=2$のときはオレンジの線になる。

このオレンジの正規分布のサイコロを降って、出た目が$x_0=1$と$x_1=-1$とすると、ノイズ$e$は以下のように書ける

e = 1 - \zeta

bを実際に計算してみる

では、公開鍵を作るために必要な２つ目の要素である$b$を計算してみる。結論から言うと以下のように計算する。ノイズが2倍になっていることがポイントだが、これは例6をやるとありがたみが分かるのでここでは説明はスキップしよう。ちなみに$q$はmodである。

b = [as_k + 2e]_q

ここで具体的な値を入れて計算してみよう

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

公開鍵pkが求まった

p_k = (a, b) =(-19 - 8\zeta,-9 - 21\zeta)

ここまでを図示してみよう。

• $a$がイデアル格子を作る
• $as_k$はいぜんとしてイデアル格子上の点である
• 紫はノイズのためのサイコロをふったときの確率分布を示しており、今回サイコロを振った結果、紫の点が選択された
• この点はイデアル格子から外れた円分整数(m=3)上の点である
• これは例4で示したLWE問題になっている

skが分かると加えたノイズが求まる

例題6以降で詳細が分かるが、ここで言いたいことは、「$s_k$がわかれば復号化できるよ」の頭出しになっている。いったんその性質を見てみよう。

\begin{align}
b − as_k &= (−9 − 21\zeta) − (−19 − 8\zeta)(1 + \zeta) \\
        &= (−9 − 21\zeta) − (-19 -19\zeta − 8\zeta − 8{\zeta}^2) \\
        &= (−9 − 21\zeta) − (-19 -27\zeta − 8(-1-\zeta)) \\
        &= −9 − 21\zeta + 11 + 19\zeta \\
        &= 2 − 2ζ \\
        &= 2e
\end{align}

図からも明確であろう。$b − as_k$をすると、すぐにノイズが求まってしまう。

手を動かして例題を解いて見よう！

ちなみに、ここまで説明してきた具体例で使った数値は、以下の例題と同じです〜!