はじめに

この記事では量子公開鍵暗号方式の一つであるKKNY暗号の安全性証明を与える.
そもそもKKNY暗号とは何か?どういったアルゴリズムなのか?を知らない方はその１を参照してほしい.さらにこの記事は安全性証明の後半以降の部分であるから前半の部分が気になる場合はその2も参照して欲しい.
一応,証明で使う問題を再現しておこう

グラフ自己同型問題(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}$かの判定.

GAPからFPSPへの帰着

証明の残りの部分である.まずはこの問題を定式化しよう.

定理

$k$を任意の多項式とする.無視できない確率でk-FPSPを解く多項式時間量子アルゴリズムが存在すると仮定する.この時無限に多くの$n$についてその長さの入力に対してGAPを圧倒的確率でしかも最悪多項式時間内に解くような量子アルゴリズムが存在する.

なぜこれがGAPからFPSPへの帰着なのか疑問に思うかも?
対偶をとって考えよう.GAPを解く手段が,ごくわずかな確率,もしくは膨大な時間を要するものしかないとする.この時,無視できない確率でk-FPSPを解く多項式時間量子アルゴリズムは存在しない.

定理の証明の準備

唯一グラフ自己同型問題(u-GAP)

入力:無向グラフ$G=(V,E)$
ここで入力に対して次のような制限を加える.$G$は唯一つの非自明な自己同型写像を持つか,あるいは持たない.この時,前者の場合の$G$を正インスタンスと呼び,後者の場合の$G$を負インスタンスと呼ぶ.

出力:$G$が正インスタンスか負インスタンスかの判定

唯一反転グラフ自己同型問題(u-ff-GAP)

入力:無向グラフ$G=(V,E)$
ここで入力に対して次のような制限を加える.$|V|=n$とおき,$G$は$\pi \in \mathcal{K}_n$の中に非自明な自己同型写像を持つか,あるいはそもそも非自明な自己同型写像を持たない.この時,前者の場合の$G$を正インスタンスと呼び,後者の場合の$G$を負インスタンスと呼ぶ.

出力:$G$が正インスタンスか負インスタンスかの判定

補題1

u-ff-GAPとGAPはチューリング等価である.

証明はグラフ理論による.ここでは省略する.この補題により,u-ff-GAPからFPSPへの帰着を示せば安全性証明が終わる.
そのために新しいアルゴリズムを2つ用意する.

補題2

u-ff-GAPの入力をインスタンスと呼ぶ事にする.今,インスタンス$G$が与えられたとして以下が成立する.

1.$G$が正インスタンスのときは$\rho_{\pi}^+$を,負インスタンスのときは$\displaystyle{\iota = \frac{1}{n!} \sum_{\sigma \in S_n} | \sigma \rangle \langle \sigma | }$を生成する多項式時間量子アルゴリズム(正剰余類サンプリングアルゴリズム)が存在する.

2.$G$が正インスタンスのときは$\rho_{\pi}^-$を,負インスタンスのときは$\iota$を生成する多項式時間量子アルゴリズム(負剰余類サンプリングアルゴリズム)が存在する.

補題2の証明

u-ff-GAPのインスタンス$G$が与えられているとする.最初に正剰余類サンプリングアルゴリズムを実際に構築する.とはいえやる事はたったの2手順だけである

1.量子状態$\displaystyle{\frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n}| \sigma \rangle | \sigma (G) \rangle}$を実装する.

2.第二レジスタの内容を破棄する.

$| \sigma (G) \rangle$を表現するにはそもそもコンピュータ上でグラフを表現する必要がある.しかしその方法を議論するのは本題からかけ離れすぎているためここでは割愛する.ちなみに$\sigma (G)$とは,Gの各頂点の番号を$\sigma$で置換したものである.

こんなんで本当に上手くいくだろうか?場合分けして考えよう.
まず$G$が正インスタンスの場合,$\sigma (G) = \sigma \pi (G)$であるから与えられた量子状態は

\frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n}| \sigma \rangle | \sigma (G) \rangle = \frac{1}{\sqrt{2n!}} \sum_{\sigma \in S_n}(| \sigma \rangle  + | \sigma \pi \rangle 
 ) |\sigma (G) \rangle

ここで第二レジスタを破棄するとその密度状態$\chi$は

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

つぎに$G$が負インスタンスの場合だが,自己同型写像が無いので,第一レジスタの状態は最初の量子状態以外の表現はない.よって第二レジスタを破棄すれば密度状態$\chi$が$\iota$に一致する.

続いて負剰余類サンプリングアルゴリズムを考えよう.正剰余類の場合とあまり変わらない.
まず量子状態$\displaystyle{\frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n}| \sigma \rangle | \sigma (G) \rangle}$を実装する.
ここで第一レジスタに格納されている各置換の符号を計算し(これは多項式時間で出来る事が知られている),置換が奇置換である時は位相を反転させる.これにより量子状態は$\displaystyle{\frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n} (-1)^{\textrm{sgn}(\sigma)} | \sigma \rangle | \sigma (G) \rangle}$へと変化する.
第二レジスタを破棄し,第一レジスタの密度状態を$\chi$とおく.ここで$\pi$は奇置換なので$\sigma$と$\sigma \pi$のそれぞれの符号は異なる.あとは正剰余類の場合と同様に計算すれば,$G$が正インスタンスならば$\chi = \rho_{\pi}^-$であり,負インスタンスならば$\chi = \iota$を得る.

定理の証明

二つの多項式$k,p$と多項式時間量子アルゴリズム$\mathcal{A}$が存在して,無視できない確率でk-FPSPを解く,すなわち無限に多くの$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)}

が成立すると仮定する.そのような$n$をひとつ固定して考える.u-ff-GAPの入力のインスタンス$G$が与えられた時,次のようなアルゴリズム$\mathcal{B}$を実行する.

アルゴリズムB

(S1)正剰余類サンプリングアルゴリズムによる出力$\chi^+$と負剰余類サンプリングアルゴリズムによる出力$\chi^-$を用いて以下の２つの系列を用意する.

S^+ = (\chi^{+ \otimes k} , \cdots , \chi^{+ \otimes k}), \hspace{30pt} S^- = (\chi^{- \otimes k} , \cdots , \chi^{- \otimes k})

ただし,それぞれの長さは$8p^2(n)n$とする(例えば$S^+$なら$\chi^{+ \otimes k}$が$8p^2(n)n$個並んでいる).

(S2)$S^+$と$S^-$の各構成要素を入力として$\mathcal{A}$を合計$8p^2(n)n$回独立に実行する.この時出力系列を$R^+$と$R^-$とおく,当然次が成立する.

R^+ = (\mathcal{A} (\chi^{+ \otimes k}) , \cdots , \mathcal{A} (\chi^{+ \otimes k})), \hspace{15pt} R^- = (\mathcal{A} (\chi^{- \otimes k}) , \cdots , \mathcal{A} (\chi^{- \otimes k}))

(S3) $R^+$における$1$の個数と$R^-$における$1$の個数の合計の差が$4p(n)n$以上であるとき「正」を出力,そうでなければ「負」を出力する.

分析

もし$G$が正インスタンスならば

S^+ = (\rho_{\pi}^{+ \otimes k} , \cdots , \rho_{\pi}^{+ \otimes k}) かつ S^- = (\rho_{\pi}^{- \otimes k} , \cdots , \rho_{\pi}^{- \otimes k})

である.$G$が負インスタンスならば

S^+ = S^- = (\iota^{\otimes k} , \cdots , \iota^{\otimes k})

である.$G$が正インスタンスであるとき,$R^+$における$1$の個数と$R^-$における$1$の個数は,仮定よりその差が$\frac{1}{p(n)}$より真に大きいのだから,少なくとも異なるはずである.この差を評価するためにHoeffding上界を用いるが,このために2つの確率変数$X^+$と$X^-$を導入する.それぞれ$R^+$における$1$の個数と$R^-$における$1$の個数を表すものとする.

$X_1 , \cdots X_r$を独立なベルヌーイ試行とし,$\textrm{Pr}(X_i) = p$とする.$X = \sum_{i=1}^{r} X_i$および$\mu = E[X] = rp$とおく,このとき,$0 < \epsilon < 1$に対して,$\textrm{Pr}[|X- \mu| \geq \epsilon r] \leq 2 e^{-2 \epsilon^2 r}$が成立する.これをHoeffding上界(あるいは加法形式のChenoff上界)という.

$p^+ = \textrm{Pr}[\mathcal{A} (\rho_{\pi}^{+ \otimes k})], \hspace{10pt} p^- = \textrm{Pr}[\mathcal{A} (\rho_{\pi}^{- \otimes k})],$および$p^0 = \textrm{Pr}[\mathcal{A} (\iota^{\otimes k})]$とする.

今,$G$を正インスタンスであるとしよう.Hoeffding上界より任意の$\epsilon > 0$で

\textrm{Pr}[|X^+ - p^+ r(n)| \geq \epsilon r(n)] < 2 e^{-2 \epsilon^2 r(n)}

\textrm{Pr}[|X^- - p^- r(n)| \geq \epsilon r(n)] < 2 e^{-2 \epsilon^2 r(n)}

が成立する.これらの不等式より

\textrm{Pr}[|(X^+ - X^-)- (p^+ - p^-) r(n)| < 2 \epsilon r(n)] \geq 1- 4 e^{-2 \epsilon^2 r(n)}

であり,仮定より$|p^+ - p^-| > \frac{1}{p(n)}$だから

\textrm{Pr}\left[ |X^+ - X^- | \geq \left( \frac{1}{p(n)} - 2 \epsilon \right) r(n)\right] \geq 1- 4 e^{-2 \epsilon^2 r(n)}

である.

次に,もし$G$が負インスタンスならばHoeffding上界を用いて,任意の$\epsilon > 0$で

\textrm{Pr}[|X^+ - p^0 r(n)| \geq \epsilon r(n)] < 2 e^{-2 \epsilon^2 r(n)}

\textrm{Pr}[|X^- - p^0 r(n)| \geq \epsilon r(n)] < 2 e^{-2 \epsilon^2 r(n)}

これらの不等式より

\textrm{Pr}[|X^+ - X^- | \geq 2 \epsilon r(n)] \leq 4 e^{-2 \epsilon^2 r(n)}

である.

ここで$\epsilon = \frac{1}{4p(n)}, \hspace{10pt} r(n) = 8p^2(n)n$とおくと,$G$が正インスタンスの場合,

\textrm{Pr}[|X^+ - X^- | \geq 4p(n)n] \leq 1 - 4 e^{-n}

が成立し,$G$が負インスタンスの場合,

\textrm{Pr}[|X^+ - X^- | < 4p(n)n] \leq 1 - 4 e^{-n}

が成立する.よってアルゴリズム$\mathcal{B}$はu-ff-GAPを圧倒的確率で効率的に解く量子アルゴリズムである.

まとめ

KKNY暗号は,GAPの最悪時困難性が保障される限り安全であることが証明された.