この記事はある程度の数学(大学1年生レベル)と量子アルゴリズムの知識を前提とします.最低でも「ブラケット記法」「アダマール行列」「レジスタ」「コントロールビット」などを知っている必要があります.
はじめに
ここでは量子公開鍵暗号のひとつであるKKYN暗号について紹介する.
量子公開鍵暗号は特に敵対者が量子計算機を用いて攻撃する場合にその攻撃に耐えられるよう,こちらも量子計算機を積極的に利用するものである.
現在,もっとも一般的に使われているRSA公開鍵暗号は量子計算機によって多項式時間$O(n^3)$で解読されてしまう($n$は素因数分解すべき整数のケタ数).
KKYN暗号とは2005年に,河内,小柴,西村,山上によって考案された量子公開鍵暗号である.これがどのように動作するかを見る.
なお,本記事の内容はSpringer社による「Journal CRYPTOLOGY」という数学誌のVolume25のNumber3(2012年7月)にて528~555ページに掲載されたものと同一の内容である.
基本となる問題
グラフ自己同型問題
入力:無向グラフ$G=(V,E)$
出力:$A_G$をグラフ$G$の隣接行列として,$A_G = P^{-1} A_G P$を満たす置換行列$P \neq I$が存在するときはその$P$を出力し,存在しない場合は$\perp$を出力.
グラフ自己同型問題は今のところ量子計算機でも効率よく解く方法が発見されていない.この事実が,KKYNの安全たるゆえんである.
反転置換符号問題の準備
このアルゴリズムで直接使うのはこの問題である.
$S_n$を$n$次の対称群とし,$\sigma$を$S_n$の元とする.
ただし$n$は自然数$n'$を用いて$2(2n' + 1)$の形で表される数とする.
さて,ここで$\sigma$をどのようにコンピューター上で表現するかは別種の問題である.ここではひとつ愚直な例を与えるが,例えば膨大な量子ビットが必要である点や連結の区切りの位置をあらかじめ決めておかなければいけない点など問題点はいくつかある.しかしこの記事でそれを議論するのは本題から離れすぎてしまうため割愛する.当然,$| \sigma \rangle$の定義が必ずしも次のものである必要はない.
$| \sigma \rangle$を次で定義しよう.
| \sigma \rangle = | \sigma(0) \sigma (1) \cdots \sigma(n) \rangle
ただし$\sigma(i)$はビット列で$\sigma(i) \sigma(j)$はそれらの連結である.
また$\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] \}
ただし$\textrm{id}$は恒等置換である.以下,$\pi$を$\mathcal{K}_n$の元とする.
定義が多少複雑なので理解するために次の問題を解いてみてもいいかも?いま$n$は定義から偶数である事が保障されているがもし$n$が奇数だった場合,$\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$の元.
いわゆる密度表現である.レジスタの状態としては$\frac{1}{\sqrt{2}}(| \sigma \rangle + |\sigma \pi \rangle)$などと表現する方が適切だが,安全性証明のためこの様に表現する.
このとき,反転置換符号問題を次で与える.
反転置換符号問題(FPSP)
入力:$\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}$かの判定.
以上で準備は終わりである.ここからは鍵生成アルゴリズム,暗号化アルゴリズム,復号アルゴリズムの順に紹介する.
鍵生成アルゴリズム
アルゴリズム
- $\pi \in \mathcal{K}_n$をランダムに選択する.この$\pi$が秘密鍵である.
- 第一レジスタを$|0\rangle$とし,$S_n$の元$\sigma$を一様ランダムに選び第二レジスタに格納する.
- 第一レジスタにアダマール変換を適用する.
- 第一レジスタの唯一の量子ビットをコントロールビットとし,第二レジスタにコントロール$\pi$を適用する.
- 第一レジスタにアダマール変換を適用する.
- 第一レジスタを計算基底で測定する.もし$0$が観測されたなら第二レジスタの状態は$\rho_{\pi}^+$であり,もし$1$が観測されたなら第二レジスタの状態は$\rho_{\pi}^-$である(証明は後でする).
- もし,手順6の観測で$1$が測定された場合,次に示す反転アルゴリズムを適用する.
| \sigma \rangle \pm | \sigma \pi \rangle \mapsto (-1)^{\textrm{sgn}(\sigma)}| \sigma \rangle \pm (-1)^{\textrm{sgn}(\sigma \pi)}| \sigma \pi \rangle
ただし$\sigma$が偶置換なら$\textrm{sgn}(\sigma)=0$であり,$\sigma$が奇置換なら$\textrm{sgn}(\sigma)=1$である.$\pi$は奇置換だからこの反転アルゴリズムの適用により,$\rho_{\pi}^+$は$\rho_{\pi}^-$へ,$\rho_{\pi}^-$は$\rho_{\pi}^+$へと変化する.($-1$倍は無視)
反転アルゴリズムが行われるのは第二レジスタが$\rho_{\pi}^-$の時だけだから必ず$\rho_{\pi}^+$が得られるのである.この$\rho_{\pi}^+$が公開鍵である.ちなみに置換の偶奇性の判定は多項式時間で出来る.
また,手順4も補足しておこう.コントロール$\pi$と表現した変換$C_{\pi}$は次のようになる
C_{\pi} | 0 \rangle | \sigma \rangle = | 0 \rangle | \sigma \rangle , \hspace{20pt} C_{\pi} | 1 \rangle | \sigma \rangle = | 1 \rangle | \sigma
\pi \rangle
分析
では数式を用いてアルゴリズムの手順を最初から追っていこう.初期の状態は$|0 \rangle | \sigma \rangle$である.手順3より
|0 \rangle | \sigma \rangle \mapsto (H \otimes I)|0 \rangle | \sigma \rangle = \frac{1}{\sqrt{2}}(| 0 \rangle + | 1 \rangle)| \sigma \rangle
手順4により
\mapsto \frac{1}{\sqrt{2}}(|0 \rangle | \sigma \rangle +|1 \rangle | \sigma \pi \rangle )
手順5により
\mapsto \frac{1}{2}(|0 \rangle (| \sigma \rangle + | \sigma \pi \rangle) + |1 \rangle (| \sigma \rangle - |\sigma \pi \rangle))
よってもし$0$が観測されたなら第二レジスタの状態は$\rho_{\pi}^+$であり,もし$1$が観測されたなら第二レジスタの状態は$\rho_{\pi}^-$である.
最後に反転アルゴリズムにより$\rho_{\pi}^+$を得て,これを公開鍵とする.
暗号化アルゴリズム
- 公開鍵$\rho_{\pi}^+$を入手する
- 平文$b \in \{ 0,1 \}$に対して,$b=0$のとき$\chi = \rho_{\pi}^+$とする.$b = 1$のとき,反転アルゴリズムを利用して,$\rho_{\pi}^+$から$\rho_{\pi}^-$を生成し,この状態を$\chi$とする.
- $\chi$を暗号文として出力する.
もちろん平文の入力が2通りだけならば一瞬で解読されてしまう.なぜならその2通りの平文を公開鍵を使って暗号化してみてその結果と比較すれば良いからである.しかし,この暗号には複数ビットへの一般化が存在する.それは安全性証明の後で紹介する.
復号アルゴリズム
アルゴリズム
- $\chi$を受け取り,入力とする.
- 第一レジスタを$|0 \rangle$とし,第二レジスタを$| \chi \rangle$とする.
- 第一レジスタにアダマール変換を適用する.
- 第一レジスタの唯一の量子ビットをコントロールビットとし,第二レジスタにコントロール$\pi$を適用する.
- 第一レジスタにアダマール変換を適用する.
- 第一レジスタを計算基底で測定する.観測結果が平文である.
分析
初期状態から手順3まで
|0 \rangle | \chi \rangle \mapsto \frac{1}{\sqrt{2}}(|0 \rangle + |1 \rangle)| \chi \rangle = \frac{1}{\sqrt{2}}(|0 \rangle + |1 \rangle)| \rho_{\pi}^{\pm} \rangle
= \frac{1}{\sqrt{2}}(|0 \rangle + |1 \rangle) \otimes \frac{1}{\sqrt{2}} (| \sigma \rangle \pm | \sigma \pi \rangle)
= \frac{1}{2}(|0 \rangle (| \sigma \rangle \pm | \sigma \pi \rangle) + |1 \rangle (| \sigma \rangle \pm | \sigma \pi \rangle))
このように$\chi$は$\rho_{\pi}^{+}$と$\rho_{\pi}^-$のどちらかであるから$\rho_{\pi}^{\pm}$と略記しよう.ほかにも$\pm$の略記は積極的に使うが,いずれも復号同順である.
手順4により$C_{\pi}$を適用して$\pi^2 = \textrm{id}$を使えば
\mapsto \frac{1}{2}(|0 \rangle (| \sigma \rangle \pm | \sigma \pi \rangle) + |1 \rangle (| \sigma \pi \rangle \pm | \sigma \pi \pi \rangle))
= \frac{1}{2}(|0 \rangle (| \sigma \rangle \pm | \sigma \pi \rangle) + |1 \rangle (| \sigma \pi \rangle \pm | \sigma \rangle))
手順5によりもう一度アダマール変換して
\mapsto \frac{1}{2} (\frac{1}{\sqrt{2}}(|0 \rangle + |1 \rangle)(| \sigma \rangle \pm | \sigma \pi \rangle) + \frac{1}{\sqrt{2}}(|0 \rangle - |1 \rangle)(| \sigma \pi \rangle \pm | \sigma \rangle))
= \frac{1}{2 \sqrt{2}} |0 \rangle (| \sigma \rangle \pm | \sigma \rangle + | \sigma \pi \rangle \pm | \sigma \pi \rangle) + \frac{1}{2 \sqrt{2}} |1 \rangle (| \sigma \rangle \mp | \sigma \rangle - | \sigma \pi \rangle \pm | \sigma \pi \rangle)
手順6の証明は$\chi$が$\rho_{\pi}^{+}$ならば測定直前の状態は復号同順の上側を計算して
\frac{1}{2 \sqrt{2}} |0 \rangle (| \sigma \rangle + | \sigma \rangle + | \sigma \pi \rangle + | \sigma \pi \rangle) + \frac{1}{2 \sqrt{2}} |1 \rangle (| \sigma \rangle - | \sigma \rangle - | \sigma \pi \rangle + | \sigma \pi \rangle)
= \frac{1}{\sqrt{2}}|0 \rangle (| \sigma \rangle + | \sigma \pi \rangle)
よって測定により確率$1$で平文$0$を得る.$\chi$が$\rho_{\pi}^{-}$の時は復号同順の下側を計算して欲しい.正しく復号される事がわかる.
まとめ
ここでは量子公開鍵暗号方式の１つであるKKNY暗号について紹介した.その1はここまでである.その2以降では安全性証明を与える.