証明可能安全性と帰着

現代暗号の安全性を「絶対」ではなく相対評価する枠組み。『耐量子計算機暗号』『Foundation of Cryptography』で扱われる。「この問題が困難ならばこの暗号を破るのも困難」という形で、計算量的困難性へ帰着して証明する。

計算量的安全性の基礎

• 攻撃を多項式時間で実行できないことを目指す(BPP、確率的チューリングマシン)。
• Negligible Function、PPT(多項式時間)アルゴリズム、一方向関数・トラップドア一方向関数。
• onetime pad は Perfect Secure を達成するが鍵長=平文長で非現実的。

安全性定義

• 公開鍵暗号 $\Pi =(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ の正当性 ${\mathrm{Dec}}_{sk}({\mathrm{Enc}}_{pk}(m))=m$。
• Semantic Secure は扱いにくいので同値な IND-CCA で定式化。攻撃者と挑戦者のゲームで証明する。
• 統計距離 $\Delta (X,Y)$ で確率分布の近似を評価(計算機の乱数で連続分布を近似する基盤)。

帰着のテクニック

• 攻撃アルゴリズム ${\mathcal{A}}^{\mathrm{Elg}}$ を内部で実行する形で仮定の問題(例 DDH)を解くアルゴリズムを構成し、advantage の不等式 $\mathrm{Adv}({\mathcal{A}}^{\mathrm{Elg}})\le P(\kappa )\cdot \mathrm{Adv}({\mathcal{A}}^{\mathrm{DDH}})+ϵ$ を示す。
• game-hopping: ゲームに IND な変更を繰り返し、自明に困難なゲームへ到達させて元の困難性を示す。
• 帰着の向きに注意(問題の帰着と困難性の帰着は逆)。ElGamal の IND-CPA は DDH 仮定、ひいては離散対数問題の困難性に基づく。
• タイトな帰着ほど良く、128ビット安全性が標準基準。標準仮定(素因数分解・離散対数)への帰着が望ましい。

格子暗号(LWE) / isogeny-based-cryptography / cryptographic-security-models と接続。関連: _moc-book-notes