IND安全性からOW安全性を導出する

これは最近書いた論文の自分用のメモです．備忘録として置いておきます．論文用のメモだからと言って，正しさの保証は無いです．
ついでにWORDIAN Advent Calendar 2020の18日目の記事でもあります．
昨日の記事は，hid_alma1026さんのGPDWINMAX購入と環境整備です．
$
\newcommand{\secp}{\lambda}
\newcommand{\secparam}{1^{\secp}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\sk}{\mathsf{sk}}
\newcommand{\pk}{\mathsf{pk}}
\newcommand{\Enc}{\mathsf{Enc}}
\newcommand{\Dec}{\mathsf{Dec}}
\newcommand{\PKE}{\mathsf{PKE}}
\newcommand{\msgspace}{\mathcal{M}}
\newcommand{\sample}{\xleftarrow{\mathrm{R}}}
\newcommand{\uniform}{\xleftarrow{\mathrm{U}}}
\newcommand{\Exp}{\mathsf{Exp}}
\newcommand{\OW}{\mathrm{OW}}
\newcommand{\IND}{\mathrm{IND}}
\newcommand{\Adv}{\mathcal{A}}
\newcommand{\oracle}{\mathcal{O}}
\newcommand{\advan}{\mathsf{Adv}}
\newcommand{\negl}{\mathop{\mathrm{negl}}}
\newcommand{\Reduc}{\mathcal{B}}
$

諸定義

記法など

有限集合$S$から何らかの方法で要素$s$を取り出すこと(サンプリング)を$s \sample S$と書く．
特に，一様分布に従ってランダムにサンプルする場合は$s \uniform S$と書く．
ある$x$の非負値関数$f(x)$が$x$について無視可能であるとは，任意の非負値多項式関数$g(x)$について，ある正整数$N$が存在し，任意の$n > N$なる$n$について，$f(n) < 1 / g(n)$となることを指す．($\forall g$, $\exists N$ s.t. $\forall n > N$, $f(n) < 1 / g(n)$.)
ある$x$の関数$f$が無視可能とは，直観的には，$f$は，任意の多項式関数$g$の逆数$1/g$に対して，十分に大きい$x$を選べば，$f$は$1/g$よりも速く減衰するということ．具体例は指数関数の逆数，$2^{-x}$など．（関数値の逆数と言った方がよいかもしれない．）

シンタックス/モデル

公開鍵暗号方式$\PKE$とは，次の3つの(効率的な)アルゴリズム$\Gen$, $\Enc$, $\Dec$の組みである:

• $\Gen$: セキュリティパラメータ$\secparam$ (長さ$\secp$のunary string)を入力に取り，暗号化鍵と復号鍵の鍵ペア$(\sk, \pk)$を出力する確率的アルゴリズム．
• $\Enc$: 暗号化鍵$\pk$と平文$m$を入力に取り，暗号文$c$を出力する確率的アルゴリズム．
• $\Dec$: 復号鍵$\sk$ (と暗号化鍵$\pk$)と暗号文$c$を入力に取り，平文$m$を出力するアルゴリズム．

鍵ペア$(\sk, \pk)$の空間，平文空間$\msgspace$，暗号文空間は，$\PKE$を1つ決める時に同時に決めるものとする．

定義は自由なので，定義方法は様々なものがある．他の例としては，公開パラメータの存在を明示したもの．
上記の定義は明示していない．この時，公開パラメータに相当するものは，実装にハードコードされていると見なす．

正当性

方式$\PKE = (\Gen, \Enc, \Dec)$が公開鍵暗号方式の正当性を満たす，または公開鍵暗号方式として正当であるとは，任意のセキュリティパラメータ$\secparam$，任意の暗号化鍵と復号鍵の鍵ペア，任意の平文について，平文を暗号化鍵で暗号化した結果を，復号鍵で復号すると，元の平文に等しい時とする．

または，次の式に示すように，生成された暗号化鍵と復号鍵の鍵ペアについて，任意の方法でサンプルされた平文を暗号化鍵で暗号化した時，その暗号文を復号鍵で復号した結果が元の平文に等しくなる確率が1ならば，正当性を満たすとする:

\forall \secp,
\forall \text{$\msgspace$のサンプリング},
\Pr\left[
\begin{matrix}
(\sk, \pk) \gets \Gen(\secparam); \\
m \sample \msgspace; \\
c \gets \Enc(\pk, m)
\end{matrix}
: m = \Dec(\sk, \pk, c) \right] = 1.

確率を知りたいイベントはコロンの右側に書いている．
コロンの左側は，右側のイベントのランダムネスを明示しており，他の記法としては，これを$\Pr$記号の下に書くこともある．
長くなるので，コロンの左側に書いていると言った方が正確かもしれない．

これ以降，$\PKE$は正当なもののみを考える．

安全性

OW

公開鍵暗号方式$\PKE$が一方向(one-way, OW)であるとは，直観的には，暗号文からその平文の情報を得られないという理論的な安全性を持っていること．
但し，平文の部分情報が漏えいしないことを捉えた安全性ではない．

OW試行

セキュリティパラメータ$\secparam$と攻撃者$\Adv$について，次のようにOW試行$\Exp_{\OW}(\secparam, \Adv)$を定義する:

1. $(\sk, \pk) \gets \Gen(\secparam)$.
2. $s \gets \Adv^{\oracle_1}(\pk)$.
3. $m^* \uniform \msgspace$.
4. $c^* \gets \Enc(\pk, m^*)$.
5. $m' \gets \Adv^{\oracle_2}(s, \pk, c^*)$.
6. Output 1 if $m^* = m'$, 0 otherwise.

ここで，$\oracle_1$と$\oracle_2$はそれぞれ復号オラクルである．

復号オラクルとは，$\oracle_1$と$\oracle_2$はそれぞれ暗号文$c$を入力に取り，その暗号文の復号結果$\Dec(\sk, c)$を出力する存在であり，この時に使用される鍵ペアは，試行の1行目で$\Gen$が出力した鍵ペアである．
上記の試行では，$\Adv$が出力を行う際に，これらオラクルに(複数回)問い合わせを行い，攻撃に有利な情報を得た上で計算を行い，出力を行うことを示している．
復号オラクルの理論的な役割は，攻撃者の能力を決めることである．詳細は後述する．

OW優位性

$\Exp_{\OW}(\secparam, \Adv)$の攻撃者$\Adv$の優位性$\advan_{\OW}(\secparam, \Adv)$を次のように定義する:

\advan_{\OW}(\secparam, \Adv) := \left| \Pr\left[ \Exp_{\OW}(\secparam, \Adv) = 1 \right] - \frac{1}{\# \msgspace} \right|.

One-Wayness

$\PKE = (\Gen, \Enc, \Dec)$が一方向(one-way)である，またはOW-CPA/CCA1/CCA2安全であるとは，任意の確率的多項式時間攻撃者$\Adv$について，OW優位性$\advan_{\OW}(\secparam, \Adv)$が$\secp$について無視可能な時とする．

IND

公開鍵暗号方式$\PKE$が識別不可能(indistingushable, IND)であるとは，直観的には，暗号文からその平文に関する情報が1ビットも得られないという理論的な安全性を持っていること．

IND試行

セキュリティパラメータ$\secparam$と攻撃者$\Adv$について，次のようにIND試行$\Exp_{\IND}(\secparam, \Adv)$を定義する:

1. $(\sk, \pk) \gets \Gen(\secparam)$.
2. $(s, m_0, m_1) \gets \Adv^{\oracle_1}(\pk)$, where $m_0, m_1 \in \msgspace$.
3. $b \uniform \{ 0, 1 \}$.
4. $c^* \gets \Enc(\pk, m_b)$.
5. $b' \gets \Adv^{\oracle_2}(s, \pk, c^*)$.
6. Output 1 if $b = b'$, 0 otherwise.

ここで，$\oracle_1$と$\oracle_2$はそれぞれOW試行の復号オラクルと同じ機能を持つ復号オラクルである．

IND優位性

$\Exp_{\IND}(\secparam, \Adv)$の攻撃者$\Adv$の優位性$\advan_{\IND}(\secparam, \Adv)$を次のように定義する:

\begin{align}
\advan_{\IND}(\secparam, \Adv) &:= \left| \Pr\left[ \Exp_{\IND}(\secparam, \Adv) = 1 \right] - \frac{1}{2} \right| \\
& = \frac{1}{2} \left| \Pr\left[ b' = 0 \mid b = 0 \right] - \Pr\left[ b' = 0 \mid b = 1 \right] \right|.
\end{align}

Indistinguishability

$\PKE = (\Gen, \Enc, \Dec)$が識別不可能，またはIND-CPA/CCA1/CCA2安全であるとは，任意の確率的多項式時間攻撃者$\Adv$について，IND優位性$\advan_{\IND}(\secparam, \Adv)$が$\secp$について無視可能な時とする．

攻撃者の能力

CPA

選択平文攻撃(chosen-plaintext attack, CPA)とは，鍵ペア$(\sk, \pk)$が決定した後，攻撃者は任意の平文$m$を暗号化オラクルに問い合わせることができ，このオラクルが$\Enc(\pk, m)$を実行した結果を得られることを意味する．

公開鍵暗号方式は，暗号化鍵が公開されるため誰でも正しく$\Enc$を実行できる．よって，公開鍵暗号方式においては暗号化オラクルに問い合わせずとも，誰でも任意の平文を暗号化可能である．
つまり，CPAは公開鍵暗号方式において最低限想定される攻撃となる．
また，CPA安全性が標準的な仮定の上で証明されていない方式は，安全な公開鍵暗号方式として認められることは難しいだろう．

これまでに述べてきた定義においては，$\oracle_1 := \bot$, $\oracle_2 := \bot$の場合に対応する．
ここで$\bot$は意味の無い動作や，意味の無い情報，何も存在しないことなどを表す．

CCA1

選択暗号文攻撃(chosen-ciphertext attack, CCA1)とは，鍵ペア$(\sk, \pk)$が決定した後，攻撃者は任意の暗号文$c$を復号オラクル$\oracle_1$に問い合わせることができ，このオラクルが$\Dec(\sk, \pk, c)$を実行した結果を得られることを意味する．
但し，各試行において$c^*$を得た後は問い合わせできない．
つまり，これまでに述べてきた定義においては，$\oracle_1 := x \mapsto \Dec(\sk, \pk, x)$, $\oracle_2 := \bot$の場合に対応する．

CCA2

適応的選択暗号文攻撃(adaptive chosen-ciphertext attack, CCA2)とは，鍵ペア$(\sk, \pk)$が決定した後，攻撃者は任意の暗号文$c$を復号オラクル$\oracle_1$と$\oracle_2$に問い合わせることができ，このオラクルが$\Dec(\sk, \pk, c)$を実行した結果を得られることを意味する．
但し，各試行において $c^{*}$ を得た後， $\oracle_2$ に $c^{*}$ を問い合わせてはならない．
これまでに述べてきた定義においては，$\oracle_1 := x \mapsto \Dec(\sk, \pk, x)$, $\oracle_2 := x \mapsto \Dec(\sk, \pk, x)$ if $x \neq c^{*}$, $\bot$ otherwiseの場合に対応する．

諸定義はここまで．

INDとOWの関係

直観的には，ある方式がIND安全なら，それはOW安全でもあるはず．
それなら，きちんと理論的に証明できるはずである．

定理: IND安全→OW安全

公開鍵暗号方式PKEがIND-CPA (resp. CCA1, CCA2)安全ならば，PKEはOW-CPA (resp. CCA1, CCA2)安全である．

IND安全→OW安全の証明

対偶を証明する．
任意の確率的多項式時間攻撃者$\Adv$について，$\advan_{\OW}(\secparam, \Adv)$が$\secp$について無視可能ではないとする．
つまり，優位性が無視可能でないOW-CPA/CCA1/CCA2攻撃者$\Adv$が存在すると仮定する．
この時，$\Adv$を利用することで，優位性が無視可能でない効率的なIND-CPA (resp. CCA1, CCA2)攻撃者$\Reduc$が構成できる(存在する)ことを示す．

まず始めに，$\Reduc$の動作を定義する．

$\Reduc^{\oracle_1}(\pk)$:

1. $t \gets \Adv^{\oracle_1}(\pk)$.
2. $m_0, m_1 \uniform \msgspace$.
3. Output $((t, m_0), m_0, m_1)$.

$\Reduc^{\oracle_2}(s, \pk, c^*)$:

1. Parse $s = (t, m_0)$.
2. $m' \gets \Adv^{\oracle_2}(t, \pk, c^*)$.
3. Output 0 if $m' = m_0$, 1 otherwise.

上記$\Reduc$を使用して，試行$\Exp_{\IND}(\secparam, \Reduc)$を構成し，$\advan_{\IND}(\secparam, \Reduc)$を求める:

• $b = 0$の時: $\Reduc$と$\Adv$の対話は$\Exp_{\OW}(\secparam, \Adv)$を完全に模倣する．ゆえに$\Pr\left[ b' = 0 \mid b = 0 \right] = \Pr[\Exp_{\OW}(\secparam, \Adv) = 1]$.
• $b = 1$の時: $\Adv$は$m_0$に関する情報を一切得ることができない．また，$m_0$は$\msgspace$上一様分布に従う．ゆえに$\Adv$がどのように動作および出力をしても$\Pr\left[ b' = 0 \mid b = 1 \right] = \frac{1}{\# \msgspace}$.

従って:

\begin{align}
\advan_{\IND}(\secparam, \Reduc)
&= \frac{1}{2} \left| \Pr\left[ b' = 0 \mid b = 0 \right] - \Pr\left[ b' = 0 \mid b = 1 \right] \right| \\
&= \frac{1}{2} \left| \Pr[\Exp_{\OW}(\secparam, \Adv) = 1] - \frac{1}{\# \msgspace} \right| \\
&= \advan_{\OW}(\secparam, \Adv) / 2.
\end{align}

仮定より$\advan_{\OW}(\secparam, \Adv)$は無視可能ではないので，$\advan_{\IND}(\secparam, \Reduc)$も無視可能ではない．
よって，$\PKE$がOW-CPA (resp. CCA1, CCA2)安全でないならば，それはIND-CPA (resp. CCA1, CCA2)安全でない．
ゆえに，$\PKE$がIND-CPA (resp. CCA1, CCA2)安全ならば，それはOW-CPA (resp. CCA1, CCA2)安全である．□

あとがき

構成の話はしていません．公開鍵暗号方式のシンタックスと正当性といった仕様を与え，それら抽象的な概念の上のみで議論しています．

上に書いているように，安全でない，さらに正当でもない公開鍵暗号方式は存在します．方式のインターフェースに合致してしまえば十分だからです．しかし，一般的には正当かつ安全な方式を指して「公開鍵暗号方式」と呼ぶことが多いでしょう．

定理は証明が不要ではないかと思うぐらい，直観的に明らかな性質です．しかし，formalに書くのは大変，という一例かなと思います．
ある程度，formalに書いたつもりですが，細かい所でinformalな所が残っています．
全部formalに書くのはきついですね．

それと，LaTeX記法の挙動がアレだったので，あとでPDFにしてどこか別の所に置くかもしれない．

余談

CCA1とCCA2で出てくるオラクルについての私見

※若干，ポエムが入っているので，ここは読まなくても良いです．

CCA1とCCA2は，例えば，攻撃者が解読しようとする暗号文$c^*$以外の暗号文について，復号が可能な状況であることを暗に示している．
これはつまり，攻撃者が「本来なら知り得ない情報を利用している」ことを意味する．
少し詳細に書くと，「攻撃者は，復号鍵（秘密）や解読対象そのものの答えを直接知ることはないが，その情報に関連した計算を行う機能にアクセスできると，攻撃者は何ができるのか」という状況を考えようとしている．
これは一見すると超越的な状況を捉えようとしているように見える．

しかし，方式の構成が持つ性質，実装の使い方や運用などから，現実にはある程度の情報の漏えいが想定されるべきだろう．これが原因となり復号オラクルなど，様々なオラクルが実際に構成可能となる場合がある．そのため，このようなオラクルの利用を許すことは必ずしも非現実的とは言えない．

例として，トラステッドコンピューティングにおけるRoot-of-Trustの実装では，秘密情報を耐タンパデバイスに内包する場合がある．外部からはこの情報を観測困難としているが，外部からの問い合わせに応じてその秘密情報に依存した回答をこのデバイスが行うので，これは秘密の情報に関連した計算結果を外に出していると言える．よって，RoTは復号オラクルと言える存在かもしれない．
そのため，RoTなど，秘密の情報を内包する耐タンパデバイスは，正常動作の範疇で外に出力する情報から秘密の情報が暴かれないよう，注意深く設計する必要があるだろう．

オラクルで捉えようしているのは，このような運用上の注意を「個別ではなく一般的」に捉えようとしているものと考えられる．
少し飛躍するが，つまり，CCA1とCCA2のような概念を考えるモチベーションの一つは，「どのように利用されても安全な（公開鍵）暗号」の理論的存在の証明，あるいはその表示を目指していると思われる．

なお，CCA2については，Bleichenbacherの攻撃の発見およびその対抗手段となることが認識された後は，現実に意味のある安全性概念をもたらす攻撃者の定義として広く受け入れられており，CCA2における攻撃者に対して安全であることは，汎用的な公開鍵暗号方式が満たすべき安全性であると考えられている．

こういった概念が突然登場するのは，典型的な躓きポイントだと思う．そのため，私見を書いてみたが，本稿の目的はこれを深く考えることではなく，またやはりあくまで私見なので，この話題はここまでとする．