#はじめに
この記事では量子公開鍵暗号方式の一つであるKKNY暗号の安全性証明を与える.
そもそもKKNY暗号とは何か?どういったアルゴリズムなのか?を知らない方はその１を参照してほしい.一応,証明で使う問題を再現しておこう

###グラフ自己同型問題(GAP)
入力:無向グラフ$G=(V,E)$

出力:$A_G$をグラフ$G$の隣接行列として,$A_G = P^{-1} A_G P$を満たす置換行列$P \neq I$が存在するときはその$P$を出力し,存在しない場合は$\perp$を出力.

###反転置換符号問題の準備
$S_n$を$n$次の対称群とし,$\sigma$を$S_n$の元とする.
ただし$n$は自然数$n'$を用いて$2(2n' + 1)$の形で表される数とする.

$\mathcal{K}_n$は$S_n$の部分集合であり,次で定義する.

\mathcal{K}_n = \{ \pi \in S_n | \pi^2 = \textrm{id} \hspace{5pt}かつ\hspace{5pt} \forall i \in \{ 1, \dots , n \}[\pi (i) \neq i] \}

以下,$\pi$を$\mathcal{K}_n$の元とする(円周率は登場しない).

さらに混合状態$\rho_{\pi}^+ (n)$と$\rho_{\pi}^- (n)$を次で定義する.

\rho_{\pi}^+ (n) = \frac{1}{2n!} \sum_{\sigma \in S_n} (| \sigma \rangle + |\sigma \pi \rangle)(\langle \sigma | + \langle \sigma \pi |)

\rho_{\pi}^- (n) = \frac{1}{2n!} \sum_{\sigma \in S_n} (| \sigma \rangle -|\sigma \pi \rangle)(\langle \sigma | - \langle \sigma \pi |)

ただし$\pi$は$\mathcal{K}_n$の元.

###反転置換符号問題(FPSP)
$S_n$を$n$次の対称群とし,$\sigma$を$S_n$の元とする.
ただし$n$は自然数$n'$を用いて$2(2n' + 1)$の形で表される数とする.

入力:$\rho_{\pi}^+(n)$または$\rho_{\pi}^-(n)$.

出力:入力が$\rho_{\pi}^+(n)$か$\rho_{\pi}^-(n)$であるかの判定.

さらにFPSPを一般化した問題を導入する.

一般化反転置換符号問題(k-FPSP)
入力:$\rho_{\pi}^+(n)^{\otimes k}$または$\rho_{\pi}^-(n)^{\otimes k}$.

出力:入力が$\rho_{\pi}^+(n)^{\otimes k}$か$\rho_{\pi}^-(n)^{\otimes k}$かの判定.

###安全性証明の方針
KKNY暗号の安全性は,グラフ自己同型問題(GAP)の「最悪時困難性」に基づいている.しかしFPSPの「平均的困難性」と「最悪時困難性」が等価であることを示し,次にGAPからFPSPへの帰着を示すという手順で安全性証明を行う.

#FPSPの平均的困難性と最悪時困難性の等価性の証明
平均的困難性と最悪時困難性の等価性を定式化しよう

###定理
$k$を任意の多項式とする.$\pi$を$\mathcal{K}_n$から一様に選んだ時,無視できない確率でk-FPSPを多項式時間量子アルゴリズム$\mathcal{A}$が存在すると仮定する.すなわち,ある多項式$p$が存在して,無限に多くの自然数$n$において

\left| \Pr_{\pi , \mathcal{A}} [\mathcal{A} (\rho_{\pi}^{+}(n)^{\otimes k(n)}) = 1] - \Pr_{\pi , \mathcal{A}} [\mathcal{A} (\rho_{\pi}^-(n)^{\otimes k(n)}) = 1] \right| > \frac{1}{p(n)}

が成立すると仮定する.
このとき多項式時間量子アルゴリズム$\mathcal{B}$が存在して,任意の$\pi \in \mathcal{K}_n$に対して,無視できない確率でk-FPSPを解く.

なぜこれが平均的困難性と最悪時困難性の等価性なのかと疑問に思うかも?
対偶をとって考えよう.すなわちある$\pi$ではk-FPSPを解く多項式時間量子アルゴリズムが存在しない(これが最悪時困難性).この時無視できない量の$\pi \in \mathcal{K}_n$に対してk-FPSPを解く多項式時間量子アルゴリズムが存在しない(これが平均的困難性)からである.
平均的困難ならば最悪時困難はごく簡単,すなわち平均時の困難な入力を一つ固定し最悪であると主張せよ.

###証明
定理の仮定を満足するような自然数$n$を一つ取り固定して考える.$i = 1,2, \cdots , k(n)$に対して$\chi_i$を与えられた$k(n)$個の量子状態のうち$i$番目の状態とする.ただし$\chi_i$は$\rho_{\pi}^+$または$\rho_{\pi}^-$のどちらかである.
次にに平均時間アルゴリズム$\mathcal{A}$を用いて最悪時間アルゴリズム$\mathcal{B}$を具体的に構成しよう

1 $S_n$から一様ランダムに$\tau$を選択する.
2 $i=1,2, \cdots ,k(n)$について,$\chi_i$に右側から$\tau$を適用し,得られる状態を$\chi'_{i}$とする.このとき

\chi'_i = \frac{1}{2n!} \sum_{\sigma \in S_n} (| \sigma \tau \rangle \pm | \sigma \tau \tau^{-1} \pi \tau \rangle ) (\langle \sigma \tau | \pm \langle \sigma \tau \tau^{-1} \pi \tau |)

= \frac{1}{2n!} \sum_{\sigma \in S_n} (| \sigma'\rangle \pm | \sigma' \tau^{-1} \pi \tau \rangle ) (\langle \sigma' | \pm \langle \sigma' \tau^{-1} \pi \tau |)

3 平均時間量子アルゴリズム$\mathcal{A}$に入力$\otimes_{i=1}^{k} \chi'_i$を与える.
4 $\mathcal{A}$からの出力をそのまま$\mathcal{B}$の出力とする.

こんなんで本当にうまくいくだろうか?$\tau^{-1} \pi \tau$について考察する.
任意の$\tau$おいて$(\tau^{-1} \pi \tau)^2$を計算すると恒等置換であることから$\tau^{-1} \pi \tau$は$\mathcal{K}_n$の元である.さらに,任意の$\pi' \in \mathcal{K}_n$に対して,$\tau^{-1} \pi \tau = \pi'$を満たす$\tau \in S_n$が存在するので$\mathcal{K}_N$は$\pi$の共役類である.加えて,$\tau^{-1} \pi \tau = \pi'$を満たす$\tau$の数は$\pi'$によらず一定である.よって$\tau$を一様ランダムに選択すると,$\tau^{-1} \pi \tau$は$\mathcal{K}_n$内の一様分布となる.

以上から,$\mathcal{A}$への入力$\otimes_{i=1}^{k} \chi'_i$は$\mathcal{A}$が平均的にうまく動作するという仮定のもと,任意の条件で$\mathcal{A}$と$\mathcal{B}$でうまく動作する確率は同じである.

#まとめ
ここではKKNY暗号の安全性証明の第一段階を行った.平均的アルゴリズムの存在を仮定すればそれを少しいじるだけで最悪時アルゴリズムが構成出来た.その3では安全性証明の第二段階を与える(予定).