論文紹介 M. Abadi and P.Rogaway: Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption) J. Cryptology (2002) 15: 103-127

概要:（暗号）メッセージの 形式的表現を計算論的に正当化 形式的（Formal） メッセージは形式的・代数的“表現” プロトコルの形式的解析に有用 具体的実現とギャップがある 計算論的（Computational） メッセージはビット列 厳密かつエレガント 確率と計算量理論が必要

Formal View

形式的表現（メッセージ） 形式的表現の集合Exp: 構文的同一性を“=”で表す Symmetric

次のような等価性を定義したい 復号できない部分 (ランダムな文字列に見える) 等価性：「復号できる部分が等しい」 様相論理の意味を与えるのに便利： 「ある参加者からは同じに見える」

Entailment M ` N ： MからNが得られる

Entailmentの定義

パターン パターンの集合Pat: 復号できない部分をで表す

表現からパターンへの変換 p(M, T)：鍵の集合Tを知っているとして、 表現Mの復号できない部分をに書き換える

パターンへの変換の定義

表現のパターン 表現だけを見て、復号できない部分をに 次のように定義

等価性 等価性の定義（「見え方が同じ」） 鍵の名前変え の下での等価性 例

例（１） 　 　 　　

例（２） but

例（３）

例（４） 平文の長さはわからない 繰り返しはわからない 同じ鍵で暗号化したかどうかわからない 同じ鍵 違う鍵

Computational View

準備 (乱数) (セキュリティ・パラメータ)

暗号スキーム 計算結果が 確率的に決まる 暗号スキーム =(K, E, D) 復号によって戻る、戻せないとき0

暗号文の長さ 暗号文の長さ|Ek(x)|は、 平文の長さ|x| セキュリティ・パラメータ のみに依存 （ただし k2K()）

無視できる（negligible） 関数  : N! R が無視できる： 任意の c>0 に対し Nc が存在し、 ¸ Nc なら 「どんな 1/(多項式) よりも速く減少」 例： 無視できる 無視できない

確率 Ensemble：（文字列集合上の）確率変数の列 サンプリング サンプルxに関する事象Eが起こる確率

Ensembleの識別不能性 x D x D’ A() A() 0 or 1 識別不能 ⇔ 出力が1である確率の 差が無視できる 確率的多項式時間 チューリング機械 (攻撃者) A() 0 or 1 識別不能 ⇔ 出力が1である確率の 差が無視できる D’ x A() 0 or 1

Ensembleの識別不能性 ２つのensemble が識別不能である とは、任意の確率的多項式時間攻撃者Aに対し次の関数が無視できることをいう

暗号スキームのセキュリティ 繰り返しを隠す(repetition-conceiling)：２つの暗号文c, c’の平文が同じであるか判定できない どの鍵を使用したかを隠す(which-key conceiling)：２つの暗号文c, c’の鍵が同じであるか判定できない メッセージの長さを隠す(length-conceiling)：暗号文から平文の長さがわからない

Repetition conceiling 暗号スキームのセキュリティ型 Repetition conceiling Which-key conceiling Length conceiling Type-0 OK Type-1 ? Type-2 Type-3 Type-4 …

アドバンテージ f A … g A … 0 or 1 Adv＝ 出力が１である確率の差 0 or 1 正しく暗号化 するオラクル 何らかの結果を返す オラクル g A … 0 or 1

Type-0 A A 0 or 1 平文の長さを 区別できるなら Advを大きくできる 0 or 1 この繰り返し 正しく暗号化 異なる鍵 ゴミを暗号化 平文の長さを 区別できるなら Advを大きくできる A 同じ鍵 0 or 1

Type-0 セキュリティ Type-0: (repetition, which-key, length) 任意の確率的多項式時間の攻撃者Aに対し次が無視できる 入力を暗号化するオラクル 入力を無視して0を暗号化するオラクル

Type-1 A 0 or 1 入力と同じ長さの ゴミを暗号化 使用した鍵を 区別できるなら Advを大きくできる A 0 or 1

Type-1 セキュリティ Type-1: (repetition, which-key, length) 入力と同じ長さの0の列を暗号化するオラクル

Type-3 A A 0 or 1 同じ平文かどうか 区別できるなら Advを大きくできる 0 or 1 正しく暗号化 入力と同じ長さの ゴミを暗号化 同じ平文かどうか 区別できるなら Advを大きくできる A 0 or 1

Type-3セキュリティ Type-3: (repetition, which-key, length) 暗号化オラクルを１つしか使えない （別の鍵で暗号化された暗号文を入手できない）

Type-0の実現 ブロック暗号(DES, AESなど)：固定長の入力 CBCモード：任意長の入力（⇒Type-1） 暗号化 乱数 暗号化 暗号化 暗号化

健全性：等価性⇒識別不能性 主定理（健全性）：暗号の循環が無いとき ならば Mを（Type-0の暗号スキームにより） 実際に暗号化して作ったビット列 （の確率変数（からなるensemble））

形式的表現をensembleに対応 形式的表現Mをビット列に変換 «M¬[]からensemble «M¬={«M¬[]}が決まる CONVERT ランダムに(Ki)2K() を選んでおく ) t(K6)

健全性：等価性⇒識別不能性 主定理（健全性）：Type-0暗号スキームを仮定、暗号の循環が無いとき 例 循環

(“hybrid technique”の利用) 定理の証明 (“hybrid technique”の利用)

準備：鍵の名前換え M, N （MN）の鍵をある条件（次のスライド）を満たすように名前変えして M’, N’とする 名前変えによってensembleは変わらない したがって、次を示せばよい

名前換えの条件 復号可能な鍵を左から順にJi、それ以外をKi {… Ki …}Kj, {… {…}Ki …}Kjの出現では i<j M, N (MN) の例：

ハイブリッド・パターン M0=pattern(M’)=pattern(N’)=N0から開始して、{…}Kiに相当するを順に元の暗号文に戻す

ハイブリッド・パターンの定義 特に、M’  N’より Mの鍵がJ1, J2,…; K1, K2, …, Kmのとき、

以降のあらすじ(hybrid tech.) «M’¬と«N’¬が識別不能でない （識別可能）と仮定する（背理法） 途中の«Mi¬, «Mi+1¬の組 （または«Ni¬, «Ni+1¬の組） いずれかが識別可能になる «Mi¬, «Mi+1¬を識別する攻撃者からType-0暗号を 破る攻撃者を構成できる⇒Type-0に矛盾

準備：パターンをensembleに対応 パターンからビット列への変換 この変換からensembleが決まる CONVERT’ （«Mi¬ ，«Nj¬などと書く） CONVERT’ (K0)は専用の鍵

大きいギャップの探索 定理がなりたたないと仮定（背理法）すると、 «M’¬と«N’¬は識別不能でない（識別可能）、 つまり、ある攻撃者Aに対し次が無視できない 以下、このAを固定

ギャップの細分化 pi, qj：ハイブリッドMi, Nj に対しAが1を返す確率 Mm=M’, Nn=N’, M’0=N’0から

ギャップの細分化 «M4¬および«M3¬のサンプルに対し、 p4 p3 p2 Aが１を返す確率の差 p1 p0 = q0 q1 q2

細分の中にも大きいギャップがある 右辺の和の各部分のうち一番大きいものは、 これらの平均値以上である、すなわち 各に対し上を満たすpi-pi-1（or qi-qi-1）がある、 さらに、無限個のに対し上を満たすものもある

無限回ギャップが大きくなる … p4 p3 p2 p1 p0 = q0 q1 q2 q3 ||=1, 2, 3, 4, 5, … 無限個のに対し ()/(m+n) より大きくなる … = q0 q1 q2 q3 ||=1, 2, 3, 4, 5, …

Type-0との矛盾の導出 pi-pi-1は次のようなものであった Aを用いて攻撃者A0を構成、アドバンテージをpi-pi-1を用いて評価

攻撃者A0 pi-pi-1 A0 f この形のM’の部分表現 のみオラクルを利用 g A M’に対応する ビット列 0 or 1

攻撃者A0f,gは、M’をビット列に変換しA(, y)を返す。ただし、 {M*}Kの暗号化関数は K=Kiのとき f K2{J1, …, J, K1, …, Ki-1}のときE(K) K2{Ki+1, …, Km}のとき g 例（i=2）：

i=2の場合でki, k0をランダムな鍵とする f=Eki(¢), g=Ek0(¢)のとき «Mi¬[]のサンプル f=Ek0(0), g=Ek0(0)のとき «Mi-1¬[]]のサンプル

次が成り立つ «Mi¬[]のサンプルyを構成して A(, y)を計算 «Mi-1¬[]]のサンプルyを構成して A(, y)を計算

Type-0暗号がA0に破られる確率を計算 無視できない⇒Type-0暗号でない⇒矛盾

定理の主張について 定理の主張は漸近的（!1）であったが、 証明からはより具体的主張(攻撃に必要な 時間など)を導き出せる 定理の主張は漸近的（!1）であったが、 証明からはより具体的主張(攻撃に必要な 時間など)を導き出せる 定理の逆は成りたたない 例）MおよびNがPlaintextの外のメッセージを暗号化する場合、MとNは等しいensembleに対応するが、MとNが形式的に等価とは限らない このような自明な例以外の場合は不明 （※completenessを証明した後の研究がある）