【イデアル格子勉強会 #5】準同型暗号の暗号文どうしの加算を理解しよう

勉強会の概要

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

これまでの流れ

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

本日のゴール

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

• 暗号文どうしを足し算して復号化した結果は、平文のどうしの足し算に等しい！
• 暗号同士の加算は暗号文の成分1どうし、成分2どうしを単純に足せばOK

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

0. 鍵生成と2つの暗号文の生成 (前回の復習)

鍵の生成

• 秘密鍵: $s_k = s_{k0} + s_{k1}\zeta=1 + \zeta$
• 公開鍵: $p_k = (a, b) = (a_0+a_1\zeta,~as_k+2e)=(-19 - 8\zeta,-9 - 21\zeta)$

暗号文1

• 平文: $m = 1 + \zeta$
• 小さな乱数: $v = 1 + \zeta$
• ノイズ1: $e_0 = -1 + \zeta$
• ノイズ2: $e_1 = -\zeta$
• 暗号文: $c=(c_0, c_1)=(bv + 2e_0+m,~av + 2e_1)=(11 - 6\zeta, -11 - 21 \zeta)$

暗号文2

• 平文: $m = \zeta$
• 小さな乱数: $v^{\prime} = \zeta$
• ノイズ1: $e_0 = \zeta$
• ノイズ2: $e_1 = 2$
• 暗号文: $c^{\prime}=(c_0^{\prime}, c_1^{\prime})=(bv^{\prime} + 2e_0^{\prime}+m^{\prime},~av^{\prime} + 2e_1^{\prime})=(21 + 15\zeta, 12 - 11 \zeta)$

1. 暗号の足し算

いったん復習として例6の復号化プロセスを思い出してみよう(復習)

\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) \\
&=m + 2e_{all}
\end{align}

上記は暗号文$c_0$についての復号化だが、暗号文$c_1$の復号化も同時に考えると以下のように示せる。

\begin{aligned}
c_0 - sc_1 &\equiv m + 2e_{all} \pmod{q} \\
c'_0 - sc'_1 &\equiv m' + 2e_{all}^{\prime} \pmod{q}
\end{aligned}

この両辺を足して、それぞれの項をまとめてやると

(c_0 + c'_0) - s(c_1 + c'_1) \equiv (m + m') + 2(e_{all} + e_{all}^{\prime}) \pmod{q}

つまり以下のように表せるので・・・

d = \left(c_0+c_0^{\prime}~,~c_1+c_1^{\prime}\right) =  \left(d_0, d_1\right)~~~~\pmod q

$d$は$m+m'$の暗号文と考えることができる。

1.1 暗号文における足し算

1.1.1 2つの暗号文を用意する

\begin{align}
c&=(c_0, c_1)=(11 - 6\zeta, -11 - 21 \zeta) \\
c^{\prime}&=(c_0^{\prime}, c_1^{\prime})=(21 + 15\zeta, 12 - 11 \zeta)
\end{align}

1.1.2 暗号文の第1成分どうし, 第2成分どうしを足す

足し算したあとの暗号文を$d$とすると

\begin{align}
d &= \left(d_0, d_1\right)=\left(c_0+c_0^{\prime}~,~c_1+c_1^{\prime}\right) \\
  &=(11 - 6\zeta + 21 + 15\zeta, -11 - 21 \zeta + 12 - 11 \zeta) \\
  &=(32+9\zeta, 1-32\zeta) ~\pmod q
\end{align}

1.2 足し算した暗号文の復号化

1.2.1 秘密鍵を使って、メッセージとノイズだけにする

\begin{align}
d_0-s_kd_1 &= 32+9\zeta - (1 + \zeta)(1-32\zeta) \\
&=32+9\zeta - (1-32\zeta + \zeta-32\zeta^2)\\
&=31+40\zeta +32(-1-\zeta)\\
&=-1+8\zeta \pmod{65}
\end{align}

1.2.2 mod2をとってノイズを除去

$-1$を$2$で割ったあまり$x$は

x=-1-int(-1/2)\times 2 = -1-(-1\times2)=1

$8$を$2$で割ったあまり$x$は$0$により

m+m^{\prime} = \left[-1+8\zeta\right]_2 = 1

1.3 平文の足し算と比較

• $m = 1 + \zeta$
• $m^{\prime} = \zeta$

[m+m^{\prime}]_2 = [1 + 2\zeta]_2 = 1

確かにこれは、$d$を復号化した値と等しい