今回は番外編です．前回のSVP を元にして，衝突困難関数を構成します．
全３回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 1の3乗根
- 3分整数
- p分整数
- m分整数
- イデアル
- 衝突困難関数とSVP
第1.5回
- 記号の整理
- 衝突困難関数の構成
- 衝突困難関数の計算例
- 構成の証明の方針
- 構成の正当性の証明
第２回
第３回
今回は第1.5回です．番外編です．
前回放棄した，SVPを使った衝突困難関数の構成を行います．
具体的な内容としては，次のようになります:
- 記号の整理
- 衝突困難関数の構成
- 衝突困難関数の計算例
- 構成の証明の方針
- 構成の正当性の証明
記号の整理
初めに記号の整理をします．
論文とは違うものもあるしれませんが，数学的に一般的だと思われる方を採用しています．
以下では，正整数 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
となります．
衝突困難関数の構成
早速構成してみましょう．
自然数 m をとって，n = \phi(m) とします．B = (\mathbb{Z} / 2 \mathbb{Z})[\zeta_m] とします．つまり，B に含まれる円分整数は，係数が 0 or 1 です．
また，k を自然数，p を素数として，k 個の円分整数 a_1, \cdots, a_k を (\mathbb{Z} / p \mathbb{Z})[\zeta_m] から取ります．
このとき，H : B^k \rightarrow (\mathbb{Z} / p \mathbb{Z})[\zeta_m] を H(z_1, \cdots, z_k) = a_1 z_1 + a_2 z_2 + \cdots + a_k z_k とします．
＊論文だと，H の定義でわざわざ mod p と書いていますが，右辺は (\mathbb{Z} / p \mathbb{Z})[\zeta_m] 内で計算することは定義より明らかなので，今回は省略しています．
といっても，少し経つと忘れてしまうので，今後はどこの環での演算かは毎回明示するようにします．今回なら「a_1 z_1 + a_2 z_2 + \cdots + a_k z_k \ \textrm{in} \ (\mathbb{Z} / p \mathbb{Z})[\zeta_m]」みたいな感じで．
そして，次の定理が成り立ちます．この定理を証明することが，今回の記事の目標です．
＊関数が衝突困難であることの定義は，第１回「衝突困難関数とSVP」 を見てください
\underline{\mathrm{Thm}}
上記で構成された関数 H は，SVPがNP困難であるという仮定のもとで衝突困難関数である．
衝突困難関数の計算例
m = 3 の場合で考えます．このとき，n = \phi(m) = 2, \ \zeta_3 = \frac{-1 + \sqrt{-3}}{2} です．また，k = 6, p = 5 とします．
まず，6個の \mathbb{Z} / 5 \mathbb{Z} 係数のランダムな円分整数として，
\begin{align*}
a_1 = 2 + 3 \zeta_3, \ a_2 = 4 + \zeta_3, \ a_3 = 1 + 3 \zeta_3, \ a_4 = 1, \ a_5 = 3 + 2 \zeta_3, a_6 = 2 + 2 \zeta_3
\end{align*}
を選びます．
また，6個の \mathbb{B} 係数の入力を
\begin{align*}
z_1 = \zeta_3, \ z_2 = 1, \ z_3 = 0, \ z_4 = 1 + \zeta_3, \ a_5 = \zeta_3, a_6 = 1 + \zeta_3
\end{align*}
とします．
このとき，(\mathbb{Z} / 5 \mathbb{Z})[\zeta_3] 内での計算として，
\begin{align*}
H(z_1, \cdots, z_6) & = a_1 z_1 + a_2 z_2 + \cdots + a_6 z_6 \\
& = (2 + 3 \zeta_3) \cdot \zeta_3 + (4 + \zeta_3) \cdot 1 + (1 + 3 \zeta_3) \cdot 0 + 1 \cdot (1 + \zeta_3) + (3 + 2 \zeta_3) \cdot \zeta_3 + (2 + 2 \zeta_3)(1 + \zeta_3) \\
& = (2 \zeta_3 + 3 \zeta_3^2) + (4 + \zeta_3) + 0 + (1 + \zeta_3) + (3 \zeta_3 + 2 \zeta_3^2) + (2 + 4 \zeta_3 + 2 \zeta_3^2) \\
& = 7 \zeta_3^2 + 11 \zeta_3 + 7 \\
& = 7 (- \zeta_3 - 1) + 11 \zeta_3 + 7 \\
& = 4 \zeta_3
\end{align*}
を得られます．
構成の証明の方針
暗号方式が安全であることの証明ですが，基本的に対偶を示すことになります（何かのNP困難性に基づいて，その方式が安全であることを示すため）．
今回だと，「SVPがNP困難 \Rightarrow H は衝突困難」ですから，「H は衝突困難でない \Rightarrow SVPがNP困難でない（多項式時間で解ける）」ことを示します．
SVPが多項式時間で解ける，は一見すると何をすればいいか分からないかもしれませんが，衝突困難ではない（と仮定している）H を使って，実際にSVPを解くアルゴリズムを構成すればいいのです．
一旦，SVPの定義を振り返ってみましょう．
参照：第１回「衝突困難関数とSVP」
\underline{\mathrm{Def(最短円分整数問題)}}
自然数 m を取って，n = \phi(m) とする．f_0, \cdots, f_{n - 1} \in \mathbb{Z} として f = f_0 + f_1 \zeta_m + \cdots + f_{n - 1} \zeta_m^{n - 1} と置く．イデアル I_f と 0ではない円分整数 g = a_0 f + a_1 \zeta_m f + \cdots + a_{n - 1} \zeta_m^{n - 1} f \in I_f \ (a_0, \cdots, a_{n - 1} \in \mathbb{Z}) が与えられているとする．
このとき，c_0, \cdots, c_{n - 1} \in \mathbb{Z} で g = c_0 + c_1 \zeta_m + \cdots + c_{n - 1} \zeta_m^{n - 1} であって，g の大きさ ||g|| = \sqrt{c_0^2 + c_1^2 + \cdots + c_{n - 1}^2} が最小な (c_0, \cdots, c_{n - 1}) を求めよ．
g = c_0 + c_1 \zeta_m + \cdots + c_{n - 1} \zeta_m^{n - 1} なる (c_0, \cdots, c_{n - 1}) は，一般には複数あります．ですが，
a. 上記の (c_0, \cdots, c_{n - 1}) を1つ見つける（存在性を示す）
b. その (c_0, \cdots, c_{n - 1}) から長さが短い (c_0^{\prime}, \cdots, c_{n - 1}^{\prime}) を構成する
c. 2のループは (c_0, \cdots, c_{n - 1}) の長さが有限だから，有限回で止まる
d. 最終的な出力値が求める答え
ということをイメージできれば，bのイテレーションの操作で，H を使って，(c_0^{\prime}, \cdots, c_{n - 1}^{\prime}) を見つける多項式時間アルゴリズムを考えればOKなわけです．
では，実際にどうアルゴリズムを構成するかですが，まず，分かりやすい部分から考えましょう．
衝突困難でないと仮定すると，H(x_1, \cdots, x_k) = H(y_1, \cdots, y_k) なる (x_1, \cdots, x_k), (y_1, \cdots, y_k) \in B^k を取れます．
つまり，a_1 x_1 + \cdots + a_k x_k = a_1 y_1 + \cdots + a_k y_k \ \textrm{in} \ (\mathbb{Z} / p \mathbb{Z})[\zeta_n] であるので，a_1 (x_1 - y_1) + \cdots + a_k (x_k - y_k) = 0 \ \textrm{in} \ (\mathbb{Z} / p \mathbb{Z})[\zeta_n] になりますから，(x_1 - y_1, \cdots, x_k - y_k) \in B^k として H(x_1 - y_1, \cdots, x_k - y_k) = 0 となります．
これは何をいっているのかというと，衝突困難でないと仮定すると，そこから H(x) = 0 \ \textrm{in} \ (\mathbb{Z} / p \mathbb{Z})[\zeta_n] なる x \in B^k が取れる，ということです．
↑の話は初めの方針a-dいずれにも直接は役立たなさそうです．
結論から書くと，以下のようにして，1と2のループ中の操作を実現できます
１：領域 U(g, g \zeta_m, \cdots, g \zeta_m^{n - 1}) からランダムに元を取る
２：１の元を丸めこんで円分実数に整形する
３：２までの操作で得られる円分実数をm個取る
４：３でのm個の円分実数を引数にして，衝突困難関数を作用させると0に移るベクトルを取る
５：４までの結果を使って，gより短い円分整数を取れる
１
まずは領域 U(g, g \zeta_m, \cdots, g \zeta_m^{n - 1}) の内部および周（論文でいう基本領域）を考えます．それは，
\begin{align*}
u_0 g + u_1 g \zeta + \cdots + u_{n - 1} g \zeta_m^{n - 1} \ (0 \leq u_i \leq 1)
\end{align*}
と表すことができます．ここで，u_i の範囲を考えてみると，一見すると実数で良さそうなのですが，実数だと計算機上でシミュレートすることができません．
よって，パラメタ \sigma を取って，N(0, \sigma) に従う正規分布からランダムに実数（実際には有理数）を取ります．もちろん，Nは「離散」な正規分布です．
この試行をn回繰り返して線型結合の形にすることで，U(g, g \zeta_m, \cdots, g \zeta_m^{n - 1}) から適当に元を1つ取ることができます．
この元を（記号 u_i の乱用ですが） y_i = u_0 g + u_1 g \zeta + \cdots + u_{n - 1} g \zeta_m^{n - 1} とします．
２
y_i はまだ円分整数ではありません．u_i が有理数だからです．
ここで，w_i = p y_i / g とします．このことから、
\begin{align*}
w_i & = p(u_0 g + u_1 g \zeta + \cdots + u_{n - 1} g \zeta_m^{n - 1}) / g \\
& = p(u_0 + u_1 \zeta + \cdots + u_{n - 1} \zeta_m^{n - 1}) \\
& = u_0^{\prime} + u_1^{\prime} \zeta_m + \cdots + u_{n - 1}^{\prime} \zeta_m^{n - 1}
\end{align*}
を得られます．
このとき，u_i^{\prime} を四捨五入した整数値を a_{i, 0} とすると，
\begin{align*}
a_{i, 0} + a_{i, 1} \zeta_m + \cdots + a_{i, n - 1} \zeta_m^{n - 1}
\end{align*}
となります．これをa_i と置きます．
３
２で得られた a_i を i 回目の操作とみなして，a_0 から a_{k - 1} まで取ります．
４
ここでやっと衝突困難関数の話が出てきます．3での a_0 から a_{n - 1} に対して，z = (z_1, \cdots, z_k) \in \mathbb{Z}^{2}[\zeta_m] であって H(z_1, \cdots, z_k) = a_1 z_1 + \cdots + a_k z_k \ \mathrm{in} \ \mathbb{Z}^{(p)}[\zeta_m] なるような z を取ります．
５
最後に
\begin{align*}
\displaystyle
h = \left( \frac{g(w_1 - a_1)}{p} - y_1 \right) z_1 + \cdots + \left( \frac{g(w_k - a_k)}{p} - y_k \right) z_k
\end{align*}
とします．この h こそが，bのイテレーションで求めたかったものになります．
構成の正当性の証明
円分整数 g \in I_f を固定する．
0 \leq i \leq n - 1 とする．
i 回目の操作
実数 \sigma をパラメタとする，離散正規分布 N(0, \sigma^2) から，0以上1以下の n 個の有理数 u_{i, 0}, \cdots, u_{i, n - 1} を選び，y_i = u_{i, 0} g + u_{i, 1} g \zeta_m + \cdots + u_{i, n - 1} g \zeta_m^{n - 1} とする．
w_i = p y_i / g として，各係数を四捨五入することで得られる円分整数 a_i を取る．
以上の操作で得られる円分整数 a_0, \cdots, a_{n - 1} を考える．
この a_0, \cdots, a_{n - 1} に対して，z = (z_1, \cdots, z_k) \in \mathbb{Z}^{2}[\zeta_m] であって H(z_1, \cdots, z_k) = a_1 z_1 + \cdots + a_k z_k \ \mathrm{in} \ \mathbb{Z}^{(p)}[\zeta_m] なるような z を取る．
ここで，
\begin{align*}
\displaystyle
h = \left( \frac{g(w_1 - a_1)}{p} - y_1 \right) z_1 + \cdots + \left( \frac{g(w_k - a_k)}{p} - y_k \right) z_k
\end{align*}
とする．後は，
\bullet h \in I_f
\bullet h の長さが g よりも短い
以上の２つを示せばよい．ここでは前者のみ示す（後者は準備が大変なので・・・）．
\begin{align*}
\displaystyle
h & = \sum_{i = 1}^n \left( \frac{g(w_i - a_i)}{p} - y_i \right) z_i \\
& = \sum_{i = 1}^n \left( \frac{g(p y_i / g - a_i)}{p} - y_i \right) z_i \\
& = \sum_{i = 1}^n \left( y_i - \frac{g}{p} a_i - y_i \right) z_i \\
& = \sum_{i = 1}^n - \frac{g}{p} a_i z_i \\
\end{align*}
であり，\displaystyle \sum_{i = 1}^n a_i z_i = a_1 z_1 + \cdots + a_k z_k = H(z_1, \cdots, z_k) \ \mathrm{in} \ \mathbb{Z}^{(p)}[\zeta_m] であったから，このことより h \in I_f が示される．
よって，与えられた g \in I_f より短い h \in I_f を構成でき，この操作を十分回数繰り返す（g の長さは有限なので有限会の操作で止まる）ことで，I_f に属する最小の長さの円分整数を構成できる．
以上より示された．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion