(57)【要約】【課題】ＭＤ構造を持つハッシュ関数を用いた暗号アルゴリズムが安全であることを証明する。【解決手段】ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造で構成したハッシュ関数ＨＭＤ（ｈＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクル（ＲＯＴ）部１０７を用いて、ハッシュ関数ＨＭＤ（ｈＲＯ）を用いる暗号アルゴリズムＰの安全性を評価する。攻撃アルゴリズムＡ２実行部１０６が、暗号アルゴリズムＰを実施する暗号アルゴリズムＰ実行部１１１と追跡ランダムオラクル（ＲＯＴ）部１０７と通信を行い、条件Ｃ２における暗号アルゴリズムＰの安全性Ｓ２を破る攻撃をシミュレートし、攻撃アルゴリズムＡ１実行部１０５が、暗号アルゴリズムＰが利用する暗号アルゴリズムＸの安全性Ｓ１を条件Ｃ１のもとで破る攻撃をシミュレートして、暗号アルゴリズムＰの安全性を評価する。【選択図】図１
2010039274.tif 000002
【特許請求の範囲】
【請求項１】
第１の値と乱数値である第２の値の組が一つ以上示される組情報を記憶する組情報記憶部と、
任意の値を第２の値とする問い合わせを受けた際に前記組情報記憶部に記憶されている前記組情報を検索し、当該第２の値と組となる第１の値が前記組情報から抽出できた場合に抽出した第１の値を応答し、当該第２の値と組となる第１の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクル部を含み、ＭＤ（Ｍｅｒｋｌｅ−Ｄａｍｇａａｒｄ）構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクル部と、
ＭＤ構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力部と、
前記追跡ランダムオラクル部を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価部とを有することを特徴とする情報処理装置。
【請求項２】
前記追跡ランダムオラクル部は、更に、
任意の値を第１の値とする問い合わせを受けた際に前記組情報記憶部に記憶されている前記組情報を検索し、当該第１の値と組となる第２の値が前記組情報から抽出できた場合に抽出した第２の値を応答し、当該第１の値と組となる第２の値が前記組情報から抽出できない場合に乱数値を生成し、生成した乱数値を当該第１の値と組となる第２の値として応答し、当該第１の値と当該第２の値の組を前記組情報に追加して前記組情報記憶部に記憶させるランダムオラクル部を有することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記情報入力部は、
前記アルゴリズム評価部における前記評価対象暗号アルゴリズムの評価条件と前記評価対象暗号アルゴリズムに要求される安全性が示される条件情報を入力し、
前記アルゴリズム評価部は、
前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートして、前記評価対象暗号アルゴリズムを評価することを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
前記情報入力部は、
前記評価対象暗号アルゴリズムとともに、前記評価対象暗号アルゴリズムが利用する暗号アルゴリズムが関連暗号アルゴリズムとして示される暗号アルゴリズム情報を入力し、
前記アルゴリズム評価部における前記評価対象暗号アルゴリズムの評価条件と前記評価対象暗号アルゴリズムに要求される安全性と、前記アルゴリズム評価部における前記関連暗号アルゴリズムの評価条件と前記関連暗号アルゴリズムに要求される安全性とが示される条件情報を入力し、
前記アルゴリズム評価部は、
前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートする第２の攻撃部と、
前記第２の攻撃部による攻撃内容に基づき、前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記関連暗号アルゴリズムに対してシミュレートする第１の攻撃部とを有することを特徴とする請求項１〜３のいずれかに記載の情報処理装置。
【請求項５】
前記第２の攻撃部は、
前記追跡オラクル部に第２の値として任意の値を問い合わせて前記追跡オラクル部から応答値を取得し、前記ランダムオラクル部に第２の値として任意の値を問い合わせて前記ランダムオラクル部から応答値を取得し、問い合わせ内容と応答内容を解析して、前記評価対象暗号アルゴリズムに対する攻撃をシミュレートすることを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記情報処理装置は、更に、
前記評価対象暗号アルゴリズムを実行する評価対象暗号アルゴリズム実行部を有し、
前記第２の攻撃部は、
所定の問い合わせ値を生成し、生成した問い合わせ値を前記評価対象暗号アルゴリズム実行部に問い合わせて前記評価対象暗号アルゴリズム実行部から対応する応答値を取得して、生成した問い合わせ値と取得した応答値を解析して、前記評価対象暗号アルゴリズムに対する攻撃をシミュレートすることを特徴とする請求項４に記載の情報処理装置。
【請求項７】
前記第１の攻撃部は、
前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性に沿ったデータを生成し、生成したデータを前記第２の攻撃部に出力し、
前記第２の攻撃部は、
前記第１の攻撃部からデータを入力し、
前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部へ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、前記第１の攻撃部から入力したデータについて、前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性を破ることを特徴とする請求項６に記載の情報処理装置。
【請求項８】
前記第１の攻撃部は、
前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性に沿ったデータとして、２つ以上の平文を生成するとともに、前記評価対象暗号アルゴリズムにより各々の平文の暗号文を生成し、生成した２つ以上の平文と、生成した２つ以上の暗号文のうちのいずれか１つの暗号文を前記第２の攻撃部に出力し、
前記第２の攻撃部は、
前記第１の攻撃部から２つ以上の平文と、１つの暗号文を入力し、
前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部へ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、前記第１の攻撃部から入力した暗号文に対応する平文がいずれであるかを識別することを特徴とする請求項７に記載の情報処理装置。
【請求項９】
前記第１の攻撃部は、
前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性に沿ったデータとして、文書データを生成し、生成した文書データを前記第２の攻撃部に出力し、
前記第２の攻撃部は、
前記第１の攻撃部から文書データを入力し、
前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部へ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、前記評価対象暗号アルゴリズムに対応させて前記文書データの電子署名を生成することを特徴とする請求項７に記載の情報処理装置。
【請求項１０】
前記情報処理装置は、更に、
前記関連暗号アルゴリズムを実行する関連暗号アルゴリズム実行部を有し、
前記評価対象暗号アルゴリズム実行部は、
前記第２の攻撃部から問い合わせ値の問い合わせを受けた場合に、問い合わせを受けた問い合わせ値に基づき所定の値を前記ランダムオラクル部に第２の値として問い合わせて前記ランダムオラクル部から応答値を取得するとともに、問い合わせを受けた問い合わせ値に基づき所定の値を前記関連暗号アルゴリズム実行部に問い合わせて前記関連暗号アルゴリズム実行部から応答値を取得し、前記ランダムオラクル部からの応答値及び前記関連暗号アルゴリズム実行部からの応答値を解析して、前記第２の攻撃部から問い合わせのあった問い合わせに対する応答値を生成することを特徴とする請求項６〜９のいずれかに記載の情報処理装置。
【請求項１１】
前記第１の攻撃部は、
前記第２の攻撃部から前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部への問い合せ内容、問い合わせに対する前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部から前記第２の攻撃部への応答内容、前記評価対象暗号アルゴリズム実行部から前記ランダムオラクル部及び前記関連暗号アルゴリズム実行部への問い合わせ内容、及び前記ランダムオラクル部及び前記関連暗号アルゴリズム実行部から前記評価対象暗号アルゴリズム実行部への応答内容のうちの少なくともいずれかを解析して、前記関連暗号アルゴリズムに対する攻撃をシミュレートすることを特徴とする請求項１０に記載の情報処理装置。
【請求項１２】
前記アルゴリズム評価部は、
前記第２の攻撃部が前記評価対象暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破り、前記第１の攻撃部が前記関連暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破った場合に、
前記評価対象暗号アルゴリズムが、前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を満たすと評価することを特徴とする請求項４〜１１のいずれかに記載の情報処理装置。
【請求項１３】
前記関連暗号アルゴリズムは、第１の評価条件のもとで第１の安全性を満たすものであり、
前記情報入力部は、
前記関連暗号アルゴリズムの評価条件として前記第１の評価条件が示され、前記関連暗号アルゴリズムの安全性として前記第１の安全性が示され、前記評価対象暗号アルゴリズムの評価条件として第２の評価条件が示され、前記評価対象暗号アルゴリズムの安全性として第２の安全性が示される条件情報を入力し、
前記第２の攻撃部は、
前記第２の評価条件のもとで前記第２の安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートし、
前記第１の攻撃部は、
前記第２の攻撃部による攻撃内容に基づき、前記第１の評価条件のもとで前記第１の安全性を破る攻撃を前記関連暗号アルゴリズムに対してシミュレートし、
前記アルゴリズム評価部は、
前記第２の攻撃部が前記評価対象暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記第２の評価条件のもとで前記第２の安全性を破り、前記第１の攻撃部が前記関連暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記第１の評価条件のもとで前記第１の安全性を破った場合に、
前記関連暗号アルゴリズムが前記第１の評価条件のもとで前記第１の安全性を満たせば前記評価対象暗号アルゴリズムが前記第２の評価条件のもとで前記第２の安全性を満たすという命題に対する対偶である前記第２の評価条件のもとで前記評価対象暗号アルゴリズムの前記第２の安全性が破られれば前記第１の評価条件のもとで前記関連暗号アルゴリズムの前記第１の安全性が破られることが証明され、対偶の証明により前記命題が証明され、前記関連暗号アルゴリズムは前記第１の評価条件のもとで前記第１の安全性を満たすものであることから、前記評価対象暗号アルゴリズムが、前記第２の評価条件のもとで前記第２の安全性を満たすと評価することを特徴とする請求項１２に記載の情報処理装置。
【請求項１４】
第１の値と乱数値である第２の値の組が一つ以上示される組情報を記憶するコンピュータが行う暗号アルゴリズム評価方法であって、
前記コンピュータが、ＭＤ（Ｍｅｒｋｌｅ−Ｄａｍｇａａｒｄ）構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力ステップと、
任意の値を第２の値とする問い合わせを受けた際に、前記組情報を検索し、当該第２の値と組となる第１の値が前記組情報から抽出できた場合に抽出した第１の値を応答し、当該第２の値と組となる第１の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクルが含まれ、ＭＤ構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクルを前記コンピュータが実行する追跡ランダムオラクル実行ステップと、
前記コンピュータが、前記追跡ランダムオラクル実行ステップでの実行結果を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価ステップとを有することを特徴とする暗号アルゴリズム評価方法。
【請求項１５】
前記追跡ランダムオラクル実行ステップは、
任意の値を第１の値とする問い合わせを受けた際に前記組情報を検索し、当該第１の値と組となる第２の値が前記組情報から抽出できた場合に抽出した第２の値を応答し、当該第１の値と組となる第２の値が前記組情報から抽出できない場合に乱数値を生成し、生成した乱数値を当該第１の値と組となる第２の値として応答し、当該第１の値と当該第２の値の組を前記組情報に追加して記憶させるランダムオラクルが含まれる追跡ランダムオラクルを前記コンピュータが実行することを特徴とする請求項１４に記載の暗号アルゴリズム評価方法。
【請求項１６】
前記情報入力ステップは、
前記コンピュータが、前記評価対象暗号アルゴリズムの評価条件と前記評価対象暗号アルゴリズムに要求される安全性が示される条件情報を入力し、
前記アルゴリズム評価ステップは、
前記コンピュータが、前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートして、前記評価対象暗号アルゴリズムを評価することを特徴とする請求項１４又は１５に記載の暗号アルゴリズム評価方法。
【請求項１７】
第１の値と乱数値である第２の値の組が一つ以上示される組情報を記憶するコンピュータに、
ＭＤ（Ｍｅｒｋｌｅ−Ｄａｍｇａａｒｄ）構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力処理と、
任意の値を第２の値とする問い合わせを受けた際に、前記組情報を検索し、当該第２の値と組となる第１の値が前記組情報から抽出できた場合に抽出した第１の値を応答し、当該第２の値と組となる第１の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクルが含まれ、ＭＤ構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクルを実行する追跡ランダムオラクル実行処理と、
前記追跡ランダムオラクル実行処理での実行結果を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価処理とを実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号アルゴリズムの評価技術に関し、特に、ランダムオラクル関数を用いて暗号アルゴリズムを評価する技術に関する。
【背景技術】
【０００２】
例えば、素因数分解の困難性に基づく暗号アルゴリズムの安全性の評価に関して、特許文献１に記載の技術がある。
【０００３】
また、ハッシュ関数を用いた暗号アルゴリズムの安全性の評価に関して、非特許文献１〜非特許文献５に記載の技術がある。
【０００４】
ハッシュ関数は暗号アルゴリズムでよく用いられるが、その安全性を直接評価することはできない。
通常、ハッシュ関数が用いられている暗号アルゴリズムの安全性の評価方法は、ハッシュ関数を理想化ハッシュ関数であるランダムオラクル（ＲＯ）に置き換え、ランダムオラクル（ＲＯ）を用いた暗号アルゴリズムを評価する。しかし、通常の暗号アルゴリズムの実装では、圧縮関数から構成したハッシュ関数Ｈが用いられる。
ランダムオラクル（ＲＯ）で安全性証明がつけられた暗号アルゴリズムがハッシュ関数Ｈを用いていても安全であることを示すためには、ハッシュ関数Ｈがランダムオラクル（ＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅであることを示さなければならない。
Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｌｅの定義については後述するが、概念的には、Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｌｅとは、２つの対象（ハッシュ関数Ｈとランダムオラクル（ＲＯ））の区別が困難で、２つの対象が等価であるとみなせることである。
【０００５】
ランダムオラクル（ＲＯ）とは、図１３に示すように、ランダムオラクル（ＲＯ）への入力値とそれに対する出力値を記録するハッシュリストＬを持ち、ハッシュリストＬに無い初めての入力値に対しては決まった長さのランダムな値を決めそれを出力し、入力値と出力値をハッシュリストＬに格納し、以前入力された値がハッシュリストＬの中にあった場合、それに対応するハッシュリストＬに記録された出力値を出力する関数である。
ランダムオラクル（ＲＯ）の入力は任意長で、出力は固定長である。
また、ランダムオラクル圧縮関数（ｈＲＯ）はランダムオラクル（ＲＯ）の入力長が固定の関数である。
【０００６】
ハッシュ関数とは、入力長が任意で出力長が固定の関数である。
通常、ハッシュ関数の構成には入力長出力長ともに固定の圧縮関数が用いられ、ハッシュ関数の構成法（圧縮関数の組み合わせ方）にはＭｅｒｋｌｅ−Ｄａｍｇａａｒｄ（ＭＤ）構造が用いられる。
【０００７】
非特許文献２及び非特許文献３で提案されたＭＤ構造を用いたハッシュ関数ＨＭＤは、圧縮関数をｈ（入力長をａ、出力長をｂとおく）とおくと、以下の通りになる。
ＨＭＤ（Ｍ）：
・Ｍ’＝Ｍ｜｜１｜｜０…０｜｜＜Ｍ＞，（パディングする０の数が最小となりかつＭ’の長さがａ−ｂの倍数となるようにする。ただし、＜Ｍ＞はＭのビット長の６４ビット符号語）
・Ｍ’＝（ｍ［１］，…，ｍ［ｎ］），（｜ｍ［ｉ］｜＝ａ−ｂ）
・ｆｏｒ  ｉ＝１，…，ｎ，ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｍ［ｉ］）
・ｃ［ｎ＋１］を出力  つまり、ハッシュ関数への入力値Ｍにパディングを行ったＭ’を、ａ−ｂビット長ごとに分割してｍ［１］，…，ｍ［ｎ］とし、初期値ＩＶ（ｂビット）とｍ［１］をＭＤ構造の最初の圧縮関数ｈに入力し、この最初の圧縮関数ｈの出力（ｂビット）とｍ［２］を２番目の圧縮関数ｈに入力し、２番目の圧縮関数ｈの出力とｍ［３］を３番目の圧縮関数ｈに入力し、以降同様の手順を繰り返し、ｎ番目の圧縮関数ｈからの出力（ｂビット）がハッシュ値となる。
【０００８】
また、非特許文献３では、関数Ｘが関数ＹとＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅでかつ関数Ｙを用いた暗号アルゴリズムＰ（Ｙ）が安全ならば、関数ＹをＸに置き換えた暗号アルゴリズムＰ（Ｘ）も安全であることが示されている。
関数Ｘが関数ＹとＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅであるとの定義は、任意の識別者Ｄに対して｜Ｐｒ［Ｄ（Ｘ）⇒１］−Ｐｒ［Ｄ（Ｙ）⇒１］｜＜ｅ（ｅは無視できるくらい小さい値）が成り立つことである。
【０００９】
以上の説明をもとに、ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造を用いたハッシュ関数ＨＭＤ（ｈＲＯ）について説明する。
図１４は、ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造を用いたハッシュ関数ＨＭＤ（ｈＲＯ）を説明する図である。
図１４では、ＭＤ構造の各圧縮関数が、ランダムオラクル圧縮関数（ｈＲＯ）で構成されている。ランダムオラクル圧縮関数（ｈＲＯ）とは、前述したように、入力長が固定長のランダムオラクル（ＲＯ）である。
この場合にも、ハッシュ関数への入力値Ｍにパディングを行ったＭ’を、ａ−ｂビット長ごとに分割してｍ［１］，…，ｍ［ｎ］とし、初期値ＩＶ（ｂビット）とｍ［１］をＭＤ構造の最初のランダムオラクル圧縮関数（ｈＲＯ）に入力し、この最初のランダムオラクル圧縮関数（ｈＲＯ）の出力（ｂビット）とｍ［２］を２番目のランダムオラクル圧縮関数（ｈＲＯ）に入力し、２番目のランダムオラクル圧縮関数（ｈＲＯ）の出力とｍ［３］を３番目の圧縮関数に入力し、以降同様の手順を繰り返し、ｎ番目のランダムオラクル圧縮関数（ｈＲＯ）からの出力（ｂビット）がハッシュ値となる。
【００１０】
非特許文献２では、ＭＤ構造とランダムオラクル圧縮関数（ｈＲＯ）を用いて構成したハッシュ関数ＨＭＤ（ｈＲＯ）は、ランダムオラクル（ＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅではないことが示されている。
このため、ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造で構成したハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））を、ランダムオラクル（ＲＯ）を用いた暗号アルゴリズムＰ（ＲＯ）に置き換え、暗号アルゴリズムＰ（ＲＯ）について安全性が証明されても、ハッシュ関数ＨＭＤ（ｈＲＯ）は、ランダムオラクル（ＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅでないため、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は安全であるとはいえない。
【特許文献１】特開２００６−０７２３３６号公報
【非特許文献１】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ，  Ｐｈｉｌｌｉｐ  Ｒｏｇａｗａｙ：  Ｒａｎｄｏｍ  Ｏｒａｃｌｅｓ  ａｒｅ  Ｐｒａｃｔｉｃａｌ：  Ａ  Ｐａｒａｄｉｇｍ  ｆｏｒ  Ｄｅｓｉｇｎｉｎｇ  Ｅｆｆｉｃｉｅｎｔ  Ｐｒｏｔｏｃｏｌｓ．  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ  １９９３：  ｐｐ．６２−７３
【非特許文献２】Ｊｅａｎ−Ｓｅｂａｓｔｉｅｎ  Ｃｏｒｏｎ，  Ｙｅｖｇｅｎｉｙ  Ｄｏｄｉｓ，  Ｃｅｃｉｌｅ  Ｍａｌｉｎａｕｄ，  Ｐｒａｓｈａｎｔ  Ｐｕｎｉｙａ：  Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  Ｒｅｖｉｓｉｔｅｄ：  Ｈｏｗ  ｔｏ  Ｃｏｎｓｔｒｕｃｔ  ａ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ．  ＣＲＹＰＴＯ  ２００５：  ｐｐ．４３０−４４８
【非特許文献３】Ｕｅｌｉ  Ｍ．  Ｍａｕｒｅｒ，  Ｒｅｎａｔｏ  Ｒｅｎｎｅｒ，  Ｃｌｅｍｅｎｓ  Ｈｏｌｅｎｓｔｅｉｎ：  Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙ，  Ｉｍｐｏｓｓｉｂｉｌｉｔｙ  Ｒｅｓｕｌｔｓ  ｏｎ  Ｒｅｄｕｃｔｉｏｎｓ，  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  ｔｈｅ  Ｒａｎｄｏｍ  Ｏｒａｃｌｅ  Ｍｅｔｈｏｄｏｌｏｇｙ．  ＴＣＣ  ２００４：  ｐｐ．２１−３９
【非特許文献４】Ｒａｌｐｈ  Ｃ．  Ｍｅｒｋｌｅ：  Ｏｎｅ  Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ＤＥＳ．  ＣＲＹＰＴＯ  １９８９：  ｐｐ．４２８−４４６
【非特許文献５】Ａ  Ｄｅｓｉｇｎ  Ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ．  ＣＲＹＰＴＯ  １９８９：  ｐｐ．４１６−４２７
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ＭＤ構造はＳＨＡ−１（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ−１）やＳＨＡ−２５６など世界標準のハッシュ関数に採用されており、ＭＤ構造を採用したハッシュ関数を用いた暗号アルゴリズムの評価は重要である。
前述したように、非特許文献２において、ＭＤ構造とランダムオラクル圧縮関数（ｈＲＯ）で構成したハッシュ関数ＨＭＤ（ｈＲＯ）はランダムオラクル（ＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅにならないことが示されている。
すなわち、ランダムオラクル（ＲＯ）で安全性証明がついた暗号アルゴリズムに対して、ランダムオラクル（ＲＯ）をランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造で構成したハッシュ関数ＨＭＤ（ｈＲＯ）に置き換えたときの暗号アルゴリズムの安全性を示すことはできないという課題がある。
【００１２】
本発明は、このような課題を解決することを主な目的の一つとしており、ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造で構成したハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムの安全性を証明可能な機構を実現することを主な目的とする。
【課題を解決するための手段】
【００１３】
本発明に係る情報処理装置は、
第１の値と乱数値である第２の値の組が一つ以上示される組情報を記憶する組情報記憶部と、
任意の値を第２の値とする問い合わせを受けた際に前記組情報記憶部に記憶されている前記組情報を検索し、当該第２の値と組となる第１の値が前記組情報から抽出できた場合に抽出した第１の値を応答し、当該第２の値と組となる第１の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクル部を含み、ＭＤ（Ｍｅｒｋｌｅ−Ｄａｍｇａａｒｄ）構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクル部と、
ＭＤ構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力部と、
前記追跡ランダムオラクル部を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価部とを有することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、ＭＤ構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクル部を用いることで、当該ハッシュ関数を用いた暗号アルゴリズムの安全性を証明することができる。
【発明を実施するための最良の形態】
【００１５】
実施の形態１．
本実施の形態では、ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造で構成したハッシュ関数ＨＭＤ（ｈＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅなアルゴリズムである追跡ランダムオラクル（ＲＯＴ）を導入する。
追跡ランダムオラクル（ＲＯＴ）を用いて安全性が証明された場合は、ランダムオラクル圧縮関数（ｈＲＯ）とＭＤ構造で構成したハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムは安全である。
追跡ランダムオラクル（ＲＯＴ）はランダムオラクル（ＲＯ）に新たな機能である追跡オラクル（ＴＯ）を追加したアルゴリズムである。
【００１６】
追跡オラクル（ＴＯ）を次のように定義する。
追跡オラクル（ＴＯ）は、あるアルゴリズムの入力値と出力値のペアが格納されているリストの中身を知ることができ、追跡オラクル（ＴＯ）への質問ｙに対して、追跡オラクル（ＴＯ）はリストの中のペアの中で出力値に対応する部分にｙが存在するかどうか調べ、存在する場合はそれに対応する入力値を返し、存在しない場合は、存在しないことを示す値を返信する。
【００１７】
追跡ランダムオラクル（ＲＯＴ）は、例えば、図２〜図４のいずれかの方式で実現される。
【００１８】
図２に示す例では、追跡ランダムオラクル（ＲＯＴ）は、出力長が固定長（ここではｂビットとする）のランダムオラクル（ＲＯ）と追跡オラクル（ＴＯ）から構成される。
ランダムオラクル（ＲＯ）の動作自体は、図１３を参照して説明した通りである。
追跡ランダムオラクル（ＲＯＴ）は初期状態として空のハッシュリストＬを所有する。
ランダムオラクル（ＲＯ）は質問Ｘが来た場合、∃（Ｘ，Ｙ）∈ＬならばＹを返信する。もしそのようなＹが存在しないならば、ｂビットの乱数Ｚを返信し、ハッシュリストＬに（Ｘ，Ｚ）を追加する。
追跡オラクル（ＴＯ）は質問Ｙに対して、もし∃（Ｘ，Ｙ）∈Ｌならば、Ｘを返信する。
もしそのようなＸが存在しないならば、存在しないことが分かる値を返信する。
【００１９】
また、図３に示す例では、ランダムオラクル（ＲＯ）は初期状態として空のハッシュリストＬを所有する。
ランダムオラクル（ＲＯ）は質問Ｘが来た場合、∃（Ｘ，Ｙ）∈ＬならばＹを返信する。もしそのようなＹが存在しないならば、ｂビットの乱数Ｚを返信し、ハッシュリストＬに（Ｘ，Ｚ）を追加する。
追跡オラクル（ＴＯ）からランダムオラクル（ＲＯ）にハッシュリストＬを見せるように要請された場合は、追跡オラクル（ＴＯ）にハッシュリストＬの中の値を全て追跡オラクル（ＴＯ）に返信する。
追跡オラクル（ＴＯ）は質問Ｙに対してランダムオラクル（ＲＯ）にハッシュリストＬを見せるように要請し、ハッシュリストＬの中身を受け取る。
追跡オラクル（ＴＯ）は、もし∃（Ｘ，Ｙ）∈Ｌならば、Ｘを返信する。もしそのようなＸが存在しないならば、存在しないことが分かる値を返信する。
【００２０】
図４に示す例では、ランダムオラクル（ＲＯ）は初期状態として空のハッシュリストＬを所有する。
ランダムオラクル（ＲＯ）は質問Ｘが来た場合、∃（Ｘ，Ｙ）∈ＬならばＹを返信する。もしそのようなＹが存在しないならば、ｂビットの乱数Ｚを返信し、ハッシュリストＬに（Ｘ，Ｚ）を追加する。
追跡オラクル（ＴＯ）は、ランダムオラクル（ＲＯ）のハッシュリストＬを自由に閲覧することができ、追跡オラクル（ＴＯ）への質問Ｙに対して、ランダムオラクル（ＲＯ）のハッシュリストＬを閲覧し、もし∃（Ｘ，Ｙ）∈Ｌならば、Ｘを返信する。もしそのようなＸが存在しないならば、存在しないことが分かる値を返信する。
【００２１】
ＭＤ構造の圧縮関数にランダムオラクル圧縮関数（ｈＲＯ）を用いたハッシュ関数ＨＭＤ（ｈＲＯ）は、追跡ランダムオラクル（ＲＯＴ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである。
この証明は、後述する。
【００２２】
本実施の形態では、追跡ランダムオラクル（ＲＯＴ）を用いて暗号アルゴリズムを評価する。
この評価で安全であれば、ＭＤ構造とランダムオラクル圧縮関数（ｈＲＯ）を用いたハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムは安全であるといえる。
【００２３】
次に、本実施の形態に係る暗号アルゴリズムの評価方法を図５を用いて説明する。
【００２４】
ＭＤ構造と複数のランダムオラクル圧縮関数（ｈＲＯ）で構成したハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムを評価対象暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））とする。
また、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が利用する暗号アルゴリズムを暗号アルゴリズムＸとする。
また、暗号アルゴリズムＸの評価条件を条件Ｃ１とし、暗号アルゴリズムＸが満たすべき安全性を安全性Ｓ１とする。また、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の評価条件を条件Ｃ２とし、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が満たすべき安全性を安全性Ｓ２とする。
そして、暗号アルゴリズムＸが条件Ｃ１のとき安全性Ｓ１を満たす場合に、ＨＭＤ（ｈＲＯ）を追跡ランダムオラクル（ＲＯＴ）に置き換えた暗号アルゴリズムＰ（ＲＯＴ）が、条件Ｃ２のもとで安全性Ｓ２を満たすことを評価する。
前述のように、ハッシュ関数ＨＭＤ（ｈＲＯ）は追跡ランダムオラクル（ＲＯＴ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅであるため、このような置き換えが可能である。
なお、ＨＭＤ（ｈＲＯ）の追跡ランダムオラクル（ＲＯＴ）への置き換えとは、具体的には、後述するように、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の安全性Ｓ２を破る攻撃をシミュレートする際に追跡ランダムオラクル（ＲＯＴ）を利用することである。
【００２５】
具体的には、図５のように、条件Ｃ２のもとで暗号アルゴリズムＰ（ＲＯＴ）の安全性Ｓ２を破る攻撃者（アルゴリズム）を用いて、条件Ｃ１のもとで暗号アルゴリズムＸを破る攻撃者（アルゴリズム）が構成できるかどうか判定する。これが構成できた場合、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が安全であると判定する。
なお、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））との表記には、複数のハッシュ関数ＨＭＤ１（ｈＲＯ１），…，ＨＭＤｎ（ｈＲＯｎ）が用いられる暗号アルゴリズムＰ（ＨＭＤ１（ｈＲＯ１），…，ＨＭＤｎ（ｈＲＯｎ））が含まれる。
また、同様に、暗号アルゴリズムＰ（ＲＯＴ）との表記には、暗号アルゴリズムＰ（ＨＭＤ１（ｈＲＯ１），…，ＨＭＤｎ（ｈＲＯｎ））に対応する暗号アルゴリズムＰ（ＲＯＴ１，…，ＲＯＴｎ）が含まれる。
また、以下では、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））と暗号アルゴリズムＰ（ＲＯＴ）の区別が必要でないときは、両者を一括して暗号アルゴリズムＰと表記する。
【００２６】
上記の判定の原理は、「暗号アルゴリズムＸが条件Ｃ１のもとで安全性Ｓ１を満たせば、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は条件Ｃ２のもとで安全性Ｓ２を満たす」という命題に対する対偶である「条件Ｃ２のもとで暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の安全性Ｓ２が破られれば、条件Ｃ１のもとで暗号アルゴリズムＸの安全性Ｓ１が破られる」ことを暗号アルゴリズムＰ（ＲＯＴ）を通じて証明することで、上記の命題を証明し、「暗号アルゴリズムＸが条件Ｃ１のもとで安全性Ｓ１を満す」ことは既知であるため、「暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は条件Ｃ２のもとで安全性Ｓ２を満たす」と評価するものである。
なお、暗号アルゴリズムＰは評価対象暗号アルゴリズムの例であり、暗号アルゴリズムＸは関連暗号アルゴリズムの例である。
また、条件Ｃ１は第１の評価条件の例であり、条件Ｃ２は第２の評価条件の例であり、安全性Ｓ１は第１の安全性の例であり、安全性Ｓ２は第２の安全性の例である。
【００２７】
上記の暗号アルゴリズムの評価方法の具体例を説明する。
ＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）関数（ＲＳＡは登録商標）が選択平文攻撃のもとで一方向性を満たすとき、ＲＳＡ−ＯＡＥＰ（ＲＳＡ  ｏｐｔｉｍａｌ  ａｓｙｍｍｅｔｒｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｐａｄｄｉｎｇ）暗号（ＲＳＡは登録商標）が適応的選択暗号文攻撃のもとで識別不可能安全であることを示すためには、ＲＳＡ−ＯＡＥＰ暗号に対して、適応的選択暗号文攻撃を行い、ＲＳＡ−ＯＡＥＰ暗号の識別不可能安全を破る攻撃者を用いて、選択平文攻撃を行い、ＲＳＡ関数のＲＳＡ仮定を破る攻撃者を構成する必要がある。
この場合は、暗号アルゴリズムＸをＲＳＡ関数とし、暗号アルゴリズムＰをＲＳＡ−ＯＡＥＰ暗号アルゴリズムとし、条件１を選択平文攻撃、安全性Ｓ１を一方向性、条件２を適応的選択暗号文攻撃、安全性Ｓ２を識別不可能性とし、追跡ランダムオラクルの個数を２として評価を行う。
【００２８】
上記の暗号アルゴリズムの評価方法の具体例を説明する。
落とし戸付き一方向性関数が選択平文攻撃のもとで一方向性を満たすとき、ＦＤＨ（Ｆｕｌｌ  Ｄｏｍａｉｎ  Ｈａｓｈ）が適応的選択文書攻撃のもとで存在的偽造不可能であることを示すためには、ＦＤＨに対して、適応的選択文書攻撃を行い、ＦＤＨの存在的偽造不可能を破る攻撃者を用いて、直接攻撃を行い、落とし度付き一方向性関数の一方向性を破る攻撃者を構成する必要がある。
この場合は、暗号アルゴリズムＸを落とし戸付き一方向性関数とし、暗号アルゴリズムＰをＦＤＨアルゴリズムとし、条件１を直接攻撃、安全性Ｓ１を一方向性、条件２を適応的選択文書攻撃、安全性Ｓ２を存在的偽造不可能とし、追跡ランダムオラクルの個数を１として評価を行う。
【００２９】
以上の説明を前提に、図１を参照して、本実施の形態に係る暗号アルゴリズム評価装置の構成例を説明する。
図１に示す暗号アルゴリズム評価装置１００は、情報処理装置の例である。
【００３０】
図１において、情報入力部１０１は、各種情報を入力する。情報入力部１０１は、例えば、評価対象の暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が利用する暗号アルゴリズムＸが示される暗号アルゴリズム情報を入力する。
また、情報入力部１０１は、暗号アルゴリズムＸの条件Ｃ１及び安全性Ｓ１、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の条件Ｃ２及び安全性Ｓ２が示される条件情報を入力する。
【００３１】
情報出力部１０２は、後述するアルゴリズム評価部１０４による暗号アルゴリズムの評価結果等を出力（表示、音声出力等）する。
制御部１０３は、暗号アルゴリズム評価装置１００の全体的な制御を行う。
【００３２】
アルゴリズム評価部１０４は、評価対象暗号アルゴリズムＰ（ＲＯＴ）及び暗号アルゴリズムＸの評価を行う。
アルゴリズム評価部１０４は、攻撃アルゴリズムＡ１実行部１０５と攻撃アルゴリズムＡ２実行部１０６を備える。
攻撃アルゴリズムＡ１実行部１０５は、暗号アルゴリズムＸを攻撃する攻撃アルゴリズムＡ１を実行する。
攻撃アルゴリズムＡ２実行部１０６は、暗号アルゴリズムＰ（ＲＯＴ）を攻撃する攻撃アルゴリズムＡ２を実行する。
換言すると、攻撃アルゴリズムＡ２実行部１０６は、条件情報に示される条件Ｃ２のもとで安全性Ｓ２を破る攻撃を評価対象暗号アルゴリズムＰ（ＲＯＴ）に対してシミュレートする。
また、攻撃アルゴリズムＡ１実行部１０５は、攻撃アルゴリズムＡ２実行部１０６による攻撃内容に基づき、条件情報に示される条件Ｃ１のもとで安全性Ｓ１を破る攻撃を暗号アルゴリズムＸに対してシミュレートする。
攻撃アルゴリズムＡ１実行部１０５は、第１の攻撃部の例であり、攻撃アルゴリズムＡ２実行部１０６は、第２の攻撃部の例である。
そして、アルゴリズム評価部１０４は、前述したように、攻撃アルゴリズムＡ２実行部１０６が暗号アルゴリズムＰ（ＲＯＴ）に対する攻撃のシミュレーションにおいて条件Ｃ２のもとでＳ２を破り、攻撃アルゴリズムＡ１実行部１０５が暗号アルゴリズムＸに対する攻撃のシミュレーションにおいて条件Ｃ１のもとで安全性Ｓ１を破った場合に、「暗号アルゴリズムＸが条件Ｃ１のもとで安全性Ｓ１を満たせば、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は条件Ｃ２のもとで安全性Ｓ２を満たす」という命題に対する対偶である「条件Ｃ２のもとで暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の安全性Ｓ２が破られれば、条件Ｃ１のもとで暗号アルゴリズムＸの安全性Ｓ１が破られる」が証明され、対偶の証明により上記の命題が証明され、「暗号アルゴリズムＸが条件Ｃ１のもとで安全性Ｓ１を満す」ことは既知であるため、「暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は条件Ｃ２のもとで安全性Ｓ２を満たす」と評価する。
【００３３】
追跡ランダムオラクル（ＲＯＴ）部１０７は、前述した追跡ランダムオラクル（ＲＯＴ）を実現する。
つまり、追跡ランダムオラクル（ＲＯＴ）部１０７は、ランダムオラクル（ＲＯ）部１０８と追跡オラクル（ＴＯ）部１０９を備え、ＭＤ構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである。
ランダムオラクル（ＲＯ）部１０８は、ランダムオラクル（ＲＯ）を実現する。つまり、ランダムオラクル（ＲＯ）部１０８は、任意の値ｘ（第１の値）についての問い合わせを受けた際に後述するハッシュリスト記憶部１１０に記憶されているハッシュリストＬを検索し、値ｘと組となる値ｙ（第２の値）がハッシュリストＬから抽出できた場合に抽出した値ｙを応答し、当該値ｘと組となる値がハッシュリストＬから抽出できない場合に乱数値を生成し、生成した乱数値を当該値ｘと組となる値ｙとして応答し、当該第値ｘと当該値ｙの組をハッシュリストＬに追加してハッシュリスト記憶部１１０に記憶させる。
追跡オラクル（ＴＯ）部１０９は、追跡オラクル（ＴＯ）を実現する。
つまり、追跡オラクル（ＴＯ）部１０９は、任意の値ｙ（第２の値）についての問い合わせを受けた際にハッシュリスト記憶部１１０に記憶されているハッシュリストＬを検索し、当該値ｙと組となる値ｘ（第１の値）がハッシュリストＬから抽出できた場合に抽出した値ｘを応答し、当該値ｙと組となる値がハッシュリストＬから抽出できない場合に抽出できないことを示す値を応答する。
【００３４】
ハッシュリスト記憶部１１０は、ハッシュリストＬを記憶する。
ハッシュリストＬは、組情報の例であり、また、ハッシュリスト記憶部１１０は組情報記憶部の例である。
【００３５】
暗号アルゴリズムＰ実行部１１１は、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））を実行する。
暗号アルゴリズムＰ実行部１１１は、評価対象暗号アルゴリズム実行部の例である。
また、暗号アルゴリズムＸ実行部１１２は、関連暗号アルゴリズムである暗号アルゴリズムＸを実行する。
暗号アルゴリズムＸ実行部１１２は、関連暗号アルゴリズム実行部の例である。
【００３６】
なお、以下では、攻撃アルゴリズムＡ１実行部１０５をＡ１実行部、攻撃アルゴリズムＡ２実行部１０６をＡ２実行部、追跡ランダムオラクル（ＲＯＴ）部１０７をＲＯＴ部、ランダムオラクル（ＲＯ）部１０８をＲＯ部、追跡オラクル（ＴＯ）部１０９をＴＯ部、暗号アルゴリズムＰ実行部１１１をＰ実行部、暗号アルゴリズムＸ実行部１１２をＸ実行部とも表記する。
【００３７】
次に、図６を用いて、本実施の形態に係る暗号アルゴリズム評価装置１００の動作の概要を説明する。
【００３８】
攻撃アルゴリズムＡ１（攻撃アルゴリズムＡ１実行部１０５）が、攻撃アルゴリズムＡ２（攻撃アルゴリズムＡ２実行部１０６）に安全性Ｓ２に沿ったデータを与える。攻撃アルゴリズムＡ２は、このデータについて、暗号アルゴリズムＰの安全性Ｓ２を破る攻撃を行う。
また、攻撃アルゴリズムＡ２は、暗号アルゴリズムＰ（暗号アルゴリズムＰ実行部１１１）、ランダムオラクル（ＲＯ）（ランダムオラクル（ＲＯ）部１０８）、追跡オラクル（ＴＯ）（追跡オラクル（ＴＯ）部１０９）の各々に対して質問を行い、質問に対する応答を得て、質問内容と応答内容とを解析して、攻撃アルゴリズムＡ１から与えられたデータについて、暗号アルゴリズムＰの安全性Ｓ２を破る攻撃を行う。
攻撃アルゴリズムＡ２は、条件Ｃ２のもとで自由に暗号アルゴリズムＰ、ランダムオラクル（ＲＯ）、追跡オラクル（ＴＯ）を用いることができる。
【００３９】
ランダムオラクル（ＲＯ）は、攻撃アルゴリズムＡ２からの質問ｃｉに対してハッシュリストＬを参照して、出力値ｄｉを応答する。
追跡オラクル（ＴＯ）は、攻撃アルゴリズムＡ２からの質問ｅｉに対してハッシュリストＬを参照して、出力値ｆｉを応答する。
暗号アルゴリズムＰは、攻撃アルゴリズムＡ２からの質問ａｉに対して、質問ａｉに基づいてランダムオラクル（ＲＯ）への質問ｇｉと暗号アルゴリズムＸ（暗号アルゴリズムＸ実行部１１２）への質問ｍｉを生成し、それぞれランダムオラクル（ＲＯ）及び暗号アルゴリズムＸに出力し、ランダムオラクル（ＲＯ）から出力値ｈｉを取得し、暗号アルゴリズムＸから出力値ｎｉを取得し、取得した値ｈｉと値ｎｉから攻撃アルゴリズムＡ２への応答値ｂｉを生成し、出力する。
そして、攻撃アルゴリズムＡ２は、質問内容と応答内容とを解析して、攻撃アルゴリズムＡ１から与えられたデータについて、暗号アルゴリズムＰの安全性Ｓ２を破る攻撃結果を攻撃アルゴリズムＡ１に回答する。
【００４０】
攻撃アルゴリズムＡ１は、すべての通信記録と、暗号アルゴリズムＰと追跡ランダムオラクル（ＲＯＴ）の内部記録データを解析して、暗号アルゴリズムＸの安全性Ｓ１を破る攻撃を行う。
すべての通信記録とは、攻撃アルゴリズムＡ２の攻撃に用いられたすべての質問内容、応答内容であり、具体的には、攻撃アルゴリズムＡ２と暗号アルゴリズムＸとの間で通信された値ａｉと値ｂｉ、攻撃アルゴリズムＡ２とランダムオラクル（ＲＯ）との間で通信された値ｃｉと値ｄｉ、攻撃アルゴリズムＡ２と追跡オラクル（ＴＯ）との間で通信された値ｅｉと値ｆｉ、暗号アルゴリズムＰとランダムオラクル（ＲＯ）との間で通信された値ｇｉと値ｈｉ、暗号アルゴリズムＰと暗号アルゴリズムＸとの間で通信された値ｍｉと値ｎｉである。
【００４１】
そして、攻撃アルゴリズムＡ２が高い確率で暗号アルゴリズムＰの安全性Ｓ２を破り、攻撃アルゴリズムＡ１が高い確率で暗号アルゴリズムＸの安全性Ｓ１を破る場合に、前述の「条件Ｃ２のもとで暗号アルゴリズムＰの安全性Ｓ２が破られれば、条件Ｃ１のもとで暗号アルゴリズムＸの安全性Ｓ１が破られる」という対偶が証明され、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は安全である（安全性Ｓ２を満たす）と評価される。
【００４２】
例えば、暗号アルゴリズムＸをＲＳＡ関数とし、暗号アルゴリズムＰをＲＳＡ−ＯＡＥＰ暗号アルゴリズムとし（ＲＳＡは登録商標）、条件Ｃ１を選択平文攻撃、安全性Ｓ１を一方向性、条件Ｃ２を適応的選択暗号文攻撃、安全性Ｓ２を識別不可能性とし、追跡ランダムオラクルの個数を２とした場合は、攻撃アルゴリズムＡ１は、２つの平文を生成するとともに、暗号アルゴリズムＰにより各々の平文の暗号文を生成し、生成した２つの平文と、生成した２つの暗号文のうちのいずれか１つの暗号文を攻撃アルゴリズムＡ２に出力する。
攻撃アルゴリズムＡ２は、ランダムオラクル（ＲＯ）、追跡オラクル（ＴＯ）、暗号アルゴリズムＰへ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、攻撃アルゴリズムＡ１から入力した暗号文に対応する平文がいずれであるかを識別する。
【００４３】
例えば、暗号アルゴリズムＸを落とし戸付き一方向性関数とし、暗号アルゴリズムＰをＦＤＨアルゴリズムとし、条件Ｃ１を直接攻撃、安全性Ｓ１を一方向性、条件Ｃ２を適応的選択文書攻撃、安全性Ｓ２を存在的偽造不可能とする。
攻撃アルゴリズムＡ２は、ランダムオラクル（ＲＯ）、追跡オラクル（ＴＯ）、暗号アルゴリズムＰへ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、暗号アルゴリズムＰの偽造署名を出力する。
【００４４】
次に、本実施の形態に係る暗号アルゴリズム評価装置１００の動作例を図７及び図８のフローチャートを用いて説明する。
【００４５】
まず、情報入力部１０１が、暗号アルゴリズム情報を入力して、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））及び暗号アルゴリズムＸの指定を受け付ける（Ｓ７０１）（情報入力ステップ）。
次に、情報入力部１０１が、条件情報を入力して、攻撃アルゴリズムＡ１の動作条件、攻撃アルゴリズムＡ２の動作条件を受け付ける（Ｓ７０２）（情報入力ステップ）。
この動作条件には、条件Ｃ１、条件Ｃ２、安全性Ｓ１、安全性Ｓ２のほか、攻撃アルゴリズムＡ１及び攻撃アルゴリズムＡ２を実行するために必要な条件が含まれる。例えば、攻撃アルゴリズムＡ１実行部１０５が、ランダムオラクル（ＲＯ）部１０８、追跡オラクル（ＴＯ）部１０９、暗号アルゴリズムＰ実行部１１１への質問を終了するための終了条件（質問回数、時間等）が含まれる。
【００４６】
次に、制御部１０３が、攻撃アルゴリズムＡ１実行部１０５及び攻撃アルゴリズムＡ２実行部１０６を起動し（Ｓ７０３）、攻撃アルゴリズムＡ１実行部１０５が追跡ランダムオラクル（ＲＯＴ）部１０７、暗号アルゴリズムＰ実行部１１１、暗号アルゴリズムＸ実行部１１２を起動する（Ｓ７０４）。
【００４７】
次に、攻撃アルゴリズムＡ１実行部１０５が条件Ｃ２に沿ったデータを生成し、攻撃アルゴリズムＡ２実行部１０６に渡す（Ｓ７０５）（アルゴリズム評価ステップ）。
例えば、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が、ＲＳＡ（登録商標）−ＯＡＥＰ等の公開鍵暗号アルゴリズムであれば、攻撃アルゴリズムＡ１実行部１０５は、２つの平文を生成するとともに、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））により各々の平文の暗号文を生成し、生成した２つの平文と、生成した２つの暗号文のうちのいずれか１つの暗号文を攻撃アルゴリズムＡ２実行部１０６に出力する。
【００４８】
次に、攻撃アルゴリズムＡ２実行部１０６は、攻撃アルゴリズムＡ１実行部１０５から入力したデータについて、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の安全性Ｓ２を破る攻撃をシミュレートする。
具体的には、Ｓ７０６〜Ｓ７０９の処理を終了条件に合致するまで繰り返すことにより攻撃をシミュレートする。
【００４９】
攻撃アルゴリズムＡ２実行部１０６は、まず、質問対象（ランダムオラクル（ＲＯ）部１０８、追跡オラクル（ＴＯ）部１０９、暗号アルゴリズムＰ実行部１１１）とその質問対象への質問内容を導出する（Ｓ７０６）（アルゴリズム評価ステップ）。
攻撃アルゴリズムＡ２実行部１０６は、既にいずれかの質問対象に対して行った質問内容及びその回答内容を解釈して、次の質問対象及び質問内容を導出する。
次に、攻撃アルゴリズムＡ２実行部１０６は、質問対象に質問内容を問い合わせる（Ｓ７０７）（アルゴリズム評価ステップ）。
【００５０】
攻撃アルゴリズムＡ２実行部１０６から質問を受けた質問対象は、当該質問に回答し（Ｓ７０８）、攻撃アルゴリズムＡ２実行部１０６は、質問対象から回答を受け取り、攻撃アルゴリズムＡ１実行部１０５が参照可能なメモリに質問内容と回答内容を格納する（Ｓ７０９）。
そして、終了条件に合致していない場合（Ｓ７１０でＮＯ）は、Ｓ７０６以降の処理を繰り返し、終了条件に合致している場合（Ｓ７１０でＹＥＳ）は、攻撃アルゴリズムＡ２実行部１０６は攻撃アルゴリズムＡ１実行部１０５に解を答える（Ｓ７１１）（アルゴリズム評価ステップ）。
例えば、攻撃アルゴリズムＡ１実行部１０５から２つの平文と１つの暗号文を入力している場合は、攻撃アルゴリズムＡ２実行部１０６はＳ７０６〜Ｓ７０９の処理で得た質問と回答を解析して、２つの平文のうちのどちらの平文が暗号文に対応しているかを識別し、識別結果を解として攻撃アルゴリズムＡ１実行部１０５に答える。
例えば、攻撃アルゴリズムＡ２実行部１０６はＳ７０６〜Ｓ７０９の処理で得た質問と回答を解析して、暗号アルゴリズムＰの偽造署名を攻撃アルゴリズムＡ１実行部１０５に答える。
【００５１】
次に、攻撃アルゴリズムＡ１実行部１０５が、安全性Ｓ１を破る処理を試行する（Ｓ７１２）（アルゴリズム評価ステップ）。攻撃アルゴリズムＡ２実行部１０６からの解は常に正しいため、攻撃アルゴリズムＡ１実行部１０５は攻撃アルゴリズムＡ２実行部１０６の解が正しいか否かを確認する必要なく、安全性Ｓ１を破る処理を施行する。
Ｓ７１２において、攻撃アルゴリズムＡ１実行部１０５は、Ｓ７０９及び後述のＳ９０８においてメモリに記憶されている内容を解析して、安全性Ｓ１を破る処理を実行する。メモリに記憶されている内容は、攻撃アルゴリズムＡ２実行部１０６の攻撃に用いられたすべての質問内容、応答内容である。
攻撃アルゴリズムＡ１実行部１０５は、例えば、Ｓ７１２において、選択平文攻撃においてＲＳＡ関数（ＲＳＡは登録商標）の一方向性を破る攻撃を行う。
攻撃アルゴリズムＡ１実行部１０５は、例えば、Ｓ７１２において、直接攻撃において落とし度付き一方向性関数の一方向性を破る攻撃を行う。
【００５２】
次に、アルゴリズム評価部１０４が、攻撃アルゴリズムＡ１実行部１０５により暗号アルゴリズムＸの安全性Ｓ１が破られたか否かを判断する（Ｓ７１３）（アルゴリズム評価ステップ）。
暗号アルゴリズムＸの安全性Ｓ１が破られている場合（Ｓ７１４でＹＥＳ）は、アルゴリズム評価部１０４は暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は安全であると評価する（暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は条件Ｃ２のもと安全性Ｓ２を満たすと評価する）（Ｓ７１４）（アルゴリズム評価ステップ）。
一方、暗号アルゴリズムＸの安全性Ｓ１が破られていない場合（Ｓ７１４でＮＯ）は、アルゴリズム評価部１０４は暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が安全か否かの判断ができないと評価する（暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））が条件Ｃ２のもと安全性Ｓ２を満たすとの判断ができないと評価する）（Ｓ７１５）（アルゴリズム評価ステップ）。
最後に、情報出力部１０２が、アルゴリズム評価部１０４の評価結果を出力する（Ｓ７１６）。
【００５３】
次に、図７のＳ７０７及びＳ７０８の処理の詳細を、質問対象ごとに説明する。
図９は、攻撃アルゴリズムＡ２実行部１０６が暗号アルゴリズムＰ実行部１１１に質問を問い合わせ、暗号アルゴリズムＰ実行部１１１が回答を行う際の処理の詳細を示す。
図１０は、攻撃アルゴリズムＡ２実行部１０６がランダムオラクル（ＲＯ）部１０８に質問を問い合わせ、ランダムオラクル（ＲＯ）部１０８が回答を行う際の処理（追跡ランダムオラクル実行ステップ）の詳細を示す。
図１１は、攻撃アルゴリズムＡ２実行部１０６が追跡オラクル（ＴＯ）部１０９に質問を問い合わせ、追跡オラクル（ＴＯ）部１０９が回答を行う際の処理（追跡ランダムオラクル実行ステップ）の詳細を示す。
【００５４】
まず、図９について説明する。
最初に、攻撃アルゴリズムＡ２実行部１０６が条件Ｃ２を満足する値ａｉを暗号アルゴリズムＰ実行部１１１に問い合わせる（Ｓ９０１）。
具体的には、条件Ｃ２が適応的選択暗号文攻撃である場合には、攻撃アルゴリズムＡ２実行部１０６は、攻撃アルゴリズムＡ１実行部１０５から与えられた暗号文とは異なる任意の暗号文を暗号アルゴリズムＰ実行部１１１に問い合わせて、問い合わせた暗号文から復号された平文を暗号アルゴリズムＰ実行部１１１から得ることができる。
具体的には、条件Ｃ２が適応的選択文書攻撃である場合には、攻撃アルゴリズムＡ２実行部１０６は、任意の平文を暗号アルゴリズムＰ実行部１１１に問い合わせて、問い合わせた平文に対する署名を暗号アルゴリズムＰ実行部１１１から得ることができる。
【００５５】
次に、攻撃アルゴリズムＡ２実行部１０６から値ａｉの問い合わせを受けた暗号アルゴリズムＰ実行部１１１は、問い合わせのあった値ａｉに基づいてランダムオラクル（ＲＯ）部１０８への質問値ｇｉを生成し、生成した質問値ｇｉをランダムオラクル（ＲＯ）部１０８に問い合わせる（Ｓ９０２）。
【００５６】
次に、ランダムオラクル（ＲＯ）部１０８が、ハッシュリストＬを作りつつ、質問ｇｉに対する回答値ｈｉを暗号アルゴリズムＰ実行部１１１に回答する（Ｓ９０３）。
つまり、ランダムオラクル（ＲＯ）部１０８は、質問ｇｉと組となる値がハッシュリストＬにある場合は、組となる値を回答値ｈｉとして暗号アルゴリズムＰ実行部１１１に回答し、質問ｇｉと組となる値がハッシュリストＬにない場合は、乱数値を生成し、当該乱数値を回答値ｈｉとして暗号アルゴリズムＰ実行部１１１に回答し、当該乱数値を質問ｇｉと組にしてハッシュリストＬに追加する。
【００５７】
次に、暗号アルゴリズムＰ実行部１１１は、ランダムオラクル（ＲＯ）部１０８からの回答を取得する（Ｓ９０４）。
【００５８】
次に、暗号アルゴリズムＰ実行部１１１は、攻撃アルゴリズムＡ２実行部１０６から問い合わせのあった値ａｉに基づいて暗号アルゴリズムＸ実行部１１２への質問値ｍｉを生成し、生成した質問値ｍｉを暗号アルゴリズムＸ実行部１１２に問い合わせる（Ｓ９０５）。
次に、暗号アルゴリズムＸ実行部１１２が、暗号アルゴリズムＰ実行部１１１から問い合わせのあった値ｍｉに対する回答値ｎｉを暗号アルゴリズムＸに従って導出し、暗号アルゴリズムＸ実行部１１２に回答値ｎｉを回答する（Ｓ９０６）。
【００５９】
次に、暗号アルゴリズムＰ実行部１１１が、回答値ｈｉ及び回答値ｎｉに基づき、攻撃アルゴリズムＡ２実行部１０６からの問い合わせ値ａｉに対する回答値ｂｉを生成し、回答値ｂｉを攻撃アルゴリズムＡ２実行部１０６に回答する（Ｓ９０７）。
例えば、攻撃アルゴリズムＡ２実行部１０６から暗号文の問い合わせを受けている場合は、暗号アルゴリズムＰ実行部１１１は暗号アルゴリズムＰにより復号される平文を攻撃アルゴリズムＡ２実行部１０６に回答する。
例えば、攻撃アルゴリズムＡ２実行部１０６から平文の問い合わせを受けている場合は、暗号アルゴリズムＰ実行部１１１は暗号アルゴリズムＰにより生成される署名を攻撃アルゴリズムＡ２実行部１０６に回答する。
最後に、暗号アルゴリズムＰ実行部１１１は、攻撃アルゴリズムＡ１実行部１０５が参照できるメモリに、Ｓ９０１〜Ｓ９０６において通信された質問と回答を格納する（Ｓ９０８）。ここで格納された質問及び回答は、図８のＳ７１２において攻撃アルゴリズムＡ１実行部１０５により参照される。
【００６０】
なお、図９では、暗号アルゴリズムＰ実行部１１１は、ランダムオラクル（ＲＯ）部１０８へ質問した後に暗号アルゴリズムＸ実行部１１２に質問する順序になっているが、質問の順序はこれに限らず、暗号アルゴリズムＸ実行部１１２へ質問した後にランダムオラクル（ＲＯ）部１０８に質問してもよい。また、ランダムオラクル（ＲＯ）部１０８と暗号アルゴリズムＸ実行部１１２に同時に質問してもよい。また、攻撃アルゴリズムＡ２実行部１０６からの問い合わせの度に、ランダムオラクル（ＲＯ）部１０８への質問と暗号アルゴリズムＸ実行部１１２への質問の質問順序を変えてもよい。
【００６１】
次に、図１０について説明する。
攻撃アルゴリズムＡ２実行部１０６は、安全性Ｓ２を破るための質問ｃｉをランダムオラクル（ＲＯ）部１０８に問い合わせ（Ｓ１００１）、ランダムオラクル（ＲＯ）部１０８はハッシュリストＬを作りつつ、質問ｃｉに対する回答値ｄｉを攻撃アルゴリズムＡ２実行部１０６に回答する（Ｓ１００２）。
つまり、ランダムオラクル（ＲＯ）部１０８は、質問ｃｉと組となる値がハッシュリストＬにある場合は、組となる値を回答値ｄｉとして攻撃アルゴリズムＡ２実行部１０６に回答し、質問ｃｉと組となる値がハッシュリストＬにない場合は、乱数値を生成し、当該乱数値を回答値ｄｉとして攻撃アルゴリズムＡ２実行部１０６に回答し、当該乱数値を質問ｃｉと組にしてハッシュリストＬに追加する。
【００６２】
次に、図１１について説明する。
攻撃アルゴリズムＡ２実行部１０６は、安全性Ｓ２を破るための質問ｅｉを追跡オラクル（ＴＯ）部１０９に問い合わせ（Ｓ１００１）、追跡オラクル（ＴＯ）部１０９はハッシュリストＬを参照して質問ｅｉに対する回答値ｆｉを攻撃アルゴリズムＡ２実行部１０６に回答する（Ｓ１００２）。
つまり、追跡オラクル（ＴＯ）部１０９は、質問ｅｉと組となる値がハッシュリストＬにある場合は、組となる値を回答値ｆｉとして攻撃アルゴリズムＡ２実行部１０６に回答し、質問ｅｉと組となる値がハッシュリストＬにない場合は、組となる値が存在しないことを示す値を回答値ｆｉとして攻撃アルゴリズムＡ２実行部１０６に回答する。
【００６３】
以上説明したように、本実施の形態によれば、追跡ランダムオラクル（ＲＯＴ）を用いることにより、ＭＤ構造とランダムオラクル圧縮関数（ｈＲＯ）で構成したハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の安全性を評価することができる。
前述したように、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））を、ランダムオラクル（ＲＯ）を用いた暗号アルゴリズムＰ（ＲＯ）に置き換えた場合に、暗号アルゴリズムＰ（ＲＯ）について安全性が証明されても、ハッシュ関数ＨＭＤ（ｈＲＯ）は、ランダムオラクル（ＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅでないため、暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））は安全であるとはいえない。
この点、本実施の形態によれば、ハッシュ関数ＨＭＤ（ｈＲＯ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである追跡ランダムオラクル（ＲＯＴ）を用い、追跡ランダムオラクル（ＲＯＴ）を用いた暗号アルゴリズムＰ（ＲＯＴ）の安全性を証明することで、ハッシュ関数ＨＭＤ（ｈＲＯ）を用いた暗号アルゴリズムＰ（ＨＭＤ（ｈＲＯ））の安全性を証明することができる。
【００６４】
（Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｌｅであることの証明）
次に、ＭＤ構造の圧縮関数にランダムオラクルを用いたハッシュ関数Ｈ１は、追跡ランダムオラクル（ＲＯＴ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅであることを以下にて証明する。
【００６５】
識別者Ｄは追跡オラクル（ＴＯ）に質問をしないとする。
識別者Ｄがランダムオラクル（ＲＯ）またハッシュ関数Ｈ１と対話しているときの質問をＭ、それに対する返信値をｚとおくと、識別者Ｄの質問回答を（ＩＶ，Ｍ，ｚ）、識別者ＤがシミュレータＳまたは圧縮関数（ｈＲＯ）と対話しているときの質問を（ｘ，ｍ）、回答をｙとおくと、識別者Ｄの質問回答を（ｘ，ｍ，ｙ）とする。
ｒ［ｉ］を識別者Ｄのｉ番目の質問返信値とし、識別者ＤのｖｉｅｗをＶ［ｉ］＝（ｒ［１］，…，ｒ［ｉ］）とする。
このとき、Ｖ＊［ｉ］を以下のように定義する。
・Ｖ［ｉ］⊂Ｖ＊［ｉ］
・（ａ，ｂ，ｃ），（ｃ，ｄ，ｅ）∈Ｖ＊［ｉ］⇒（ａ，ｂ｜｜ｄ，ｅ）∈Ｖ＊［ｉ］
・（ａ，ｂ｜｜ｄ，ｅ），（ａ，ｂ，ｃ）∈Ｖ＊［ｉ］⇒（ｃ，ｄ，ｅ）∈Ｖ＊［ｉ］
【００６６】
シミュレータＳを以下のように構成する。
シミュレータＳへのｉ番目の質問（ｘ［ｉ］，ｍ［ｉ］）に対して、シミュレータＳは以下のような動きをする。
ここで、ＳＶ［ｉ］はシミュレータに対するｉ番目までの質問返答値の集合とする。
ＳＶ＊［ｉ］はシミュレータＳに対する質問返答値に関してＶ＊［ｉ］と同様の定義である。
・もし∃（ＩＶ，Ｍ，ｘ［ｉ］）∈ＳＶ＊［ｉ−１］ならばｙ［ｉ］＝ＲＯ（Ｍ｜｜ｍ［ｉ］）とし、ｙ［ｉ］を返信する。
・もしｘ［ｉ］＝ＩＶならばｙ［ｉ］＝ＲＯ（ｍ［ｉ］）とし、ｙ［ｉ］を返信する。
・それ以外は、Ａ＝ＴＯ（ｘ［ｉ］）とし、以下の操作を実行する。
・もしＡ≠ｅｒｒｏｒならばｙ［ｉ］＝ＲＯ（Ａ｜｜ｍ［ｉ］）とし、ｙ［ｉ］を返信する。
・それ以外はランダムな値ｙ［ｉ］を選んで、その値を返信する。
【００６７】
次にＴｒｉｖｉａｌ  Ｑｕｅｒｙを定義する。
ｉ番目の質問回答値が以下の条件を満たすときｒ［ｉ］をｔｒｉｖｉａｌ  ｑｕｅｒｙと呼ぶことにする。
・ｒ［ｉ］＝（ＩＶ，Ｍ，ｙ［ｉ］）かつＭ＝ｍ［１］｜｜…｜｜ｍ［ｓ］，かつ
（ＩＶ，ｍ［１］，ｙ［１］），（ｙ［１］，ｍ［２］，ｙ［２］），…，（ｙ［ｓ−１］，ｍ［ｓ］，ｙ［ｓ］）∈Ｖ＊［ｉ−１］、
・ｒ［ｉ］＝（ｙ［ｓ−１］，ｍ［ｓ］，ｙ［ｓ］）かつＭ＝ｍ［１］｜｜…｜｜ｍ［ｓ］，かつ
（ＩＶ，ｍ［１］，ｙ［１］），（ｙ［１］，ｍ［２］，ｙ［２］），…，（ｙ［ｓ−２］，ｍ［ｓ−１］，ｙ［ｓ−１］），（ＩＶ，Ｍ，ｙ）∈Ｖ＊［ｉ−１］
・ｒ［ｉ］∈Ｖ［ｉ−１］
上記の質問返信値ｒ［ｉ］は質問しても識別者Ｄはなにも情報を得ることができないので、識別者Ｄはｔｒｉｖｉａｌ  ｑｕｅｒｙをしないとする。
【００６８】
Ｂａｄイベント
Ｓｕｐｐ（ｊ）＝｛ａ｜∀（ａ，ｂ，ｃ）∈Ｖ［ｉ］｝∪｛ｃ｜∀（ａ，ｂ，ｃ）∈Ｖ［ｉ］｝と定義する。このときＢａｄイベントを次のように定義する。識別者Ｄの全ての質問ｒ［１］，．．．，ｒ［ｑ］に対して、次の性質を満たすｊ∈｛１，．．．，ｑ｝が存在するときＢａｄを真とする。ｒ［ｊ］＝（ａ，ｂ，ｃ）かつｃ∈｛ａ｝∪Ｓｕｐｐ（ｉ−１）。
Ｅ１を識別者Ｄがハッシュ関数Ｈ１とランダムオラクル圧縮関数（ＲＯ）と対話しているときにＢａｄが真となるイベントとし、同様にＥ２を識別者Ｄが追跡ランダムオラクル（ＲＯＴ）とシミュレータＳと対話しているときにＢａｄが真となるイベントとする。
このときＰｒ［Ｄ（ＲＯＴ，Ｓ）⇒１｜¬Ｅ１］＝Ｐｒ［Ｄ（Ｈ１，ｈＲＯ）⇒１｜¬Ｅ２］ならば次の不等式が成り立つ。
Ａｄｖ（Ｄ）＜２×ｍａｘ｛Ｐｒ［Ｅ１］，Ｐｒ［Ｅ２］｝。
この不等式は、
「Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｌｅ  Ｓｅｃｕｒｉｔｙ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｐｏｐｕｌａｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ  ｗｉｔｈ  ｐｒｅｆｉｘ−ｆｒｅｅ  ｐａｄｄｉｎｇ  Ｄｏｎｇｈｏｏｎ  Ｃｈａｎｇ，  Ｓａｎｇｊｉｎ  Ｌｅｅ，  Ｍｒｉｄｕｌ  Ｎａｎｄｉ，  Ｍｏｔｉ  Ｙｕｎｇ」
の論文で示されている。
Ａｄｖ（Ｄ）の値が非常に小さければハッシュ関数Ｈ１と追跡ランダムオラクル（ＲＯＴ）はｉｎｄｉｆｆｅｒｅｎｔｉａｂｌｅであるといえる。
そのため、Ｐｒ［Ｄ（ＲＯＴ，Ｓ）⇒１｜¬Ｅ１］＝Ｐｒ［Ｄ（Ｈ１，ｈＲＯ）⇒１｜¬Ｅ２］を示し、Ｐｒ［Ｅ１］，Ｐｒ［Ｅ２］を求める。
【００６９】
以下、ランダムオラクル（ＲＯ），ランダムオラクル圧縮関数（ＲＯ），ハッシュ関数Ｈ１，シミュレータＳの出力ビット長をｎとおく。
【００７０】
Ｐｒ［Ｄ（ＲＯＴ，Ｓ）⇒１｜¬Ｅ１］＝Ｐｒ［Ｄ（Ｈ１，ｈＲＯ）⇒１｜¬Ｅ２］の証明：
識別者Ｄが追跡ランダムオラクル（ＲＯＴ）、シミュレータＳと対話しているとき、Ｅ１が真ではないので、識別者Ｄに帰ってくる返信値は全て異なる。
識別者Ｄは追跡ランダムオラクル（ＲＯＴ）の中のランダムオラクル（ＲＯ）とシミュレータＳと対話する。返信値は全て初での場合はランダムに選ばれる。また、同じ値が存在しないので、返信値は全て独立にランダムに選ばれている。よって、Ｅ１が真ではないとき、ｉ番目の返信値は｛０，１｝＾ｎ−｛ｉ−１番目までの全ての返信値｝からランダムに選ばれる。
識別者Ｄがハッシュ関数Ｈ１，ランダムオラクル圧縮関数（ＲＯ）と対話しているとき、Ｅ２が真ではないので、識別者Ｄに帰ってくる返信値は全て異なる。返信値は全てランダムに選ばれ、かつ同じ値が存在しないので、返信値は全て独立にランダムに選ばれる。よって、Ｅ１が真ではないとき、ｉ番目の返信値は｛０，１｝＾ｎ−｛ｉ−１番目までの全ての返信値｝からランダムに選ばれる。
よって、Ｐｒ［Ｄ（ＲＯＴ，Ｓ）⇒１｜¬Ｅ１］＝Ｐｒ［Ｄ（Ｈ１，ｈＲＯ）⇒１｜¬Ｅ２］がなりたつ。
【００７１】
Ｐｒ［Ｅ１］の導出：
先ず初めに、Ｐｒ［Ｅ１］の値を求める。
Ｅ１が真のとき、ｉ番目のランダムオラクル圧縮関数（ｈＲＯ）の呼び出しで、ｉ−１番目までの入力の和集合と出力の和集合とｉ番目の入力の和集合の和集合をＡ［ｉ］、ｉ番目のランダムオラクル圧縮関数（ＲＯ）の呼び出し時の出力をｂ［ｉ］とおくと、ｂ［ｉ］∈Ａ［ｉ］となるような、ｉが存在する。
よって、ｑ’を圧縮関数の総呼び出し回数、ｑを識別者Ｄが質問できる最大回数、ｌを識別者Ｄが質問できる最大ブロック長とすると、ｑ’＝ｌｑのときｑ’が最大となる。
よって、Ｐｒ［Ｅ１］＝１−（２＾ｎ−１）（２＾ｎ−３）．．．（２＾ｎ−２ｑ’＋１）／２＾｛ｎｑ’｝＝Ｏ（ｌ＾２ｑ＾２）／２＾ｎ。
次に、Ｐｒ［Ｅ２］の値を求める。
Ｅ２が真のとき、識別者Ｄはｔｒｉｖｉａｌ  ｑｕｅｒｙをしないので、識別者Ｄが受け取る値は全てランダムに選ばれる。
よって、Ｐｒ［Ｅ２］＝１−２＾ｎ（２＾ｎ−１）．．．（２＾ｎ−ｑ＋１）／２＾｛ｎｑ｝≦１−（１−ｑ／２＾ｎ）＾ｑ≦Ｏ（ｑ＾２／２＾ｎ）。
よって、Ａｄｖ（Ｄ）＝Ｏ（ｌ＾２ｑ＾２／２＾ｎ）となり、この値は非常に小さい値なので、ハッシュ関数Ｈ１は追跡ランダムオラクル（ＲＯＴ）とＩｎｄｉｆｆｅｒｅｎｔｉａｂｌｅである（証明終了）。
【００７２】
次に、本実施の形態で説明した内容の概要を以下にて再度述べる。
【００７３】
本実施の形態では、質問ｙに対して、リストの中を見て、ｙに対応する値がリストの中に存在する場合は、対応する値を返信し、存在しない場合は、存在しないことが分かる値を返信する追跡オラクルを説明した。
【００７４】
また、本実施の形態では、追跡オラクルとランダムオラクルから構成される追跡ランダムオラクルを説明した。
ランダムオラクルは、初期状態として空のハッシュリストを持ち、質問ｘに対して、ｘがハッシュリストの質問値格納欄にない場合は、それに対応する返信値格納欄の値ｙを返信し、ｘがハッシュリストの質問値格納欄に無い場合、固定長の値ｙをランダムに決め、ｙを返信し、ｘを質問値格納欄へ、ｙを返信値格納欄にそれぞれ記録する。
ここでの追跡オラクルの動作は、追跡オラクルへの質問値ｙに対して、ｙがハッシュリストの返信値格納欄にある場合、ｙに対応する質問値格納欄の値ｘを返信し、無い場合、無いことが分かる値を返信する。
【００７５】
また、本実施の形態では、上記の追跡ランダムオラクルを有する暗号アルゴリズム評価装置を説明した。
【００７６】
また、本実施の形態では、
暗号アルゴリズムＸと、
追跡ランダムオラクルを用いた暗号アルゴリズムＰの安全性Ｓ２を条件Ｃ２の制約のもとで破る攻撃アルゴリズムＡ２を用いて攻撃アルゴリズムＡ１を構成し、アルゴリズムＡ２の出力結果から、追跡ランダムオラクルを用いた暗号アルゴリズムＰが条件Ｃ２のもとで安全性Ｓ２を満たし、暗号アルゴリズムＸが条件Ｃ１のもとで安全性Ｓ１を満たするかどうかを評価する暗号アルゴリズム評価装置を説明した。
【００７７】
また、本実施の形態では、暗号アルゴリズムＰをＲＳＡ−ＯＡＥＰ暗号、暗号アルゴリズムＸをＲＳＡ関数（ＲＳＡは登録商標）、Ｃ１を選択平文攻撃、Ｃ２を適応的選択暗号文攻撃、Ｓ１をｐａｒｔｉａｌ−ｄｏｍａｉｎ  ｏｎｅｗａｙｎｅｓｓ、Ｓ２を識別不可能性とする暗号アルゴリズム評価装置を説明した。
【００７８】
最後に、本実施の形態に示した暗号アルゴリズム評価装置１００のハードウェア構成例について説明する。
図１２は、本実施の形態に示す暗号アルゴリズム評価装置１００のハードウェア資源の一例を示す図である。
なお、図１２の構成は、あくまでも暗号アルゴリズム評価装置１００のハードウェア構成の一例を示すものであり、暗号アルゴリズム評価装置１００のハードウェア構成は図１２に記載の構成に限らず、他の構成であってもよい。
【００７９】
図１２において、暗号アルゴリズム評価装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７と接続していてもよい。また、磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
通信ボード９１５、キーボード９０２、マウス９０３、スキャナ装置９０７、ＦＤＤ９０４などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。
【００８０】
通信ボード９１５は、ネットワークに接続されている。例えば、通信ボード９１５は、ＬＡＮ（ローカルエリアネットワーク）、インターネット、ＷＡＮ（ワイドエリアネットワーク）などに接続されていている。
【００８１】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【００８２】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【００８３】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
暗号アルゴリズム評価装置１００の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【００８４】
上記プログラム群９２３には、本実施の形態の説明において「〜部」として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【００８５】
ファイル群９２４には、本実施の形態の説明において、「〜の判断」、「〜の計算」、「〜の比較」、「〜の評価」、「〜の更新」、「〜の設定」、「〜の登録」、「〜の選択」、「〜の参照」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、本実施の形態で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００８６】
また、本実施の形態の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、本実施の形態の「〜部」としてコンピュータを機能させるものである。あるいは、本実施の形態の「〜部」の手順や方法をコンピュータに実行させるものである。
【００８７】
このように、本実施の形態に示す暗号アルゴリズム評価装置１００は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【図面の簡単な説明】
【００８８】
【図１】実施の形態１に係る暗号アルゴリズム評価装置の構成例を示す図。
【図２】実施の形態１に係る追跡ランダムオラクルの例を示す図。
【図３】実施の形態１に係る追跡ランダムオラクルの例を示す図。
【図４】実施の形態１に係る追跡ランダムオラクルの例を示す図。
【図５】実施の形態１に係る暗号アルゴリズムの評価原理を示す図。
【図６】実施の形態１に暗号アルゴリズムの評価手順の概要を示す図。
【図７】実施の形態１に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図８】実施の形態１に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図９】実施の形態１に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図１０】実施の形態１に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図１１】実施の形態１に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図１２】実施の形態１に係る暗号アルゴリズム評価装置のハードウェア構成例を示す図。
【図１３】ランダムオラクルを説明する図。
【図１４】ランダムオラクル圧縮関数とＭＤ構造を用いたハッシュ関数を説明する図。
【符号の説明】
【００８９】
１００  暗号アルゴリズム評価装置、１０１  情報入力部、１０２  情報出力部、１０３  制御部、１０４  アルゴリズム評価部、１０５  攻撃アルゴリズムＡ１実行部、１０６  攻撃アルゴリズムＡ２実行部、１０７  追跡ランダムオラクル（ＲＯＴ）部、１０８  ランダムオラクル（ＲＯ）部、１０９  追跡オラクル（ＴＯ）部、１１０  ハッシュリスト記憶部、１１１  暗号アルゴリズムＰ実行部、１１２  暗号アルゴリズムＸ実行部。
【図１】
2010039274.tif 000003
【図２】
2010039274.tif 000004
【図３】
2010039274.tif 000005
【図４】
2010039274.tif 000006
【図５】
2010039274.tif 000007
【図６】
2010039274.tif 000008
【図７】
2010039274.tif 000009
【図８】
2010039274.tif 000010
【図９】
2010039274.tif 000011
【図１０】
2010039274.tif 000012
【図１１】
2010039274.tif 000013
【図１２】
2010039274.tif 000014
【図１３】
2010039274.tif 000015
【図１４】
2010039274.tif 000016