(57)【要約】【課題】タイミング攻撃対策を行う。【解決手段】本方法は、秘密情報の複数の値の各々について、当該秘密情報の値について行われた処理の実行時間の確率分布のデータを格納する第１のデータ格納部に格納されたデータに基づき、実行時間に遅延時間を加える場合における複数の時間区間の各々の確率を定義し且つ秘密情報の複数の値について共通である第２の確率分布を生成するステップと、秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布と第２の確率分布とに基づき、当該秘密情報の値についての実行時間の確率分布を第２の確率分布に変換するためのデータを生成し、第２のデータ格納部に格納するステップとを含む。【選択図】図１
2020031263.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報の複数の値の各々について、当該秘密情報の値について行われた処理の実行時間の確率分布のデータを格納する第１のデータ格納部に格納された前記データに基づき、実行時間に遅延時間を加える場合における複数の時間区間の各々の確率を定義し且つ前記秘密情報の複数の値について共通である第２の確率分布を生成するステップと、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布と前記第２の確率分布とに基づき、当該秘密情報の値についての実行時間の確率分布を前記第２の確率分布に変換するためのデータを生成し、第２のデータ格納部に格納するステップと、
を、コンピュータに実行させるためのプログラム。
【請求項２】
前記第２の確率分布は  当該第２の確率分布において最も遅い時間区間以外のいずれかの時間区間に０を超える確率が設定されている確率分布である
請求項１記載のプログラム。
【請求項３】
前記第２の確率分布は、
０から１までのいかなる実数ｑに対しても、前記秘密情報の複数の値の各々に係る実行時間の確率分布をｑ対（１−ｑ）に分割するｑ−分位数のうち最も大きなものと同一の値のｑ−分位数を持つ確率分布又は当該確率分布に近似する確率分布である
請求項１記載のプログラム。
【請求項４】
０から１までの複数の実数が予め設定されており、
前記第２の確率分布は、
前記複数の実数のうちいかなる実数ｑに対しても、前記秘密情報の複数の値の各々に係る実行時間の確率分布をｑ対（１−ｑ）に分割するｑ−分位数のうち最も大きなものと同一の値のｑ−分位数を持つ確率分布又は当該確率分布に近似する確率分布である
請求項１記載のプログラム。
【請求項５】
前記変換するためのデータが、
前記時間区間内で遅延時間を加える確率と他の各時間区間に至るまで遅延時間を加える確率とを含む
請求項１乃至４のいずれか１つ記載のプログラム。
【請求項６】
前記変換するためのデータと、当該変換するためのデータに基づき実際の実行時間についての遅延時間を決定するプログラム又はハードウエアモジュールのデータとを合わせて出力するステップ
をさらに前記コンピュータに実行させるための請求項１乃至５のいずれか１つ記載のプログラム。
【請求項７】
前記変換するためのデータと、当該変換するためのデータに基づき実際の実行時間についての遅延時間を決定するプログラムと、前記処理のためのプログラムとを含む、プロセッサで実行可能なプログラムを生成するステップ
をさらに前記コンピュータに実行させるための請求項１乃至５のいずれか１つ記載のプログラム。
【請求項８】
秘密情報の複数の値のうちのある値と、当該ある値について行われた処理の実行時間とを取得する取得部と、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布を、前記秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第２の確率分布へ変換するためのデータを格納するデータ格納部と、
前記データ格納部における、前記ある値についてのデータに基づき、前記ある値について行われた処理の実行時間についての遅延時間を決定する決定部と、
を有する情報処理システム。
【請求項９】
前記データが、
確率分布について予め定義されている複数の時間区間のうち各時間区間内で遅延時間を加える確率と他の各時間区間に至るまで遅延時間を加える確率とを含む
請求項８記載の情報処理システム。
【請求項１０】
前記ある値について行われた処理の実行時間と決定された前記遅延時間とから決まる出力時刻に、前記ある値について行われた処理の結果を出力する出力部
をさらに有する情報処理システム。
【請求項１１】
前記第２の確率分布は、当該第２の確率分布において定義される複数の時間区間のうち最も遅い時間区間以外のいずれかの時間区間に０を超える確率が設定されている確率分布である
請求項８乃至１０のいずれか１つ記載の情報処理システム。
【請求項１２】
前記秘密情報の複数の値の各々について、前記取得部により取得された、当該秘密情報の値について行われた処理の実行時間を格納する第２のデータ格納部と、
前記第２のデータ格納部に格納されたデータに基づき、前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の第３の確率分布を生成する第１の生成部と、
前記秘密情報の複数の値の各々についての第３の確率分布に基づき、前記秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第４の確率分布を生成する第２の生成部と、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の第３の確率分布と前記第４の確率分布とに基づき、当該秘密情報の値についての実行時間の第３の確率分布を前記第４の確率分布に変換するためのデータを生成し、前記データ格納部に格納する第３の生成部と、
をさらに有する請求項８乃至１１のいずれか１つ記載の情報処理システム。
【請求項１３】
秘密情報の複数の値の各々について、当該秘密情報の値について行われた処理の実行時間の確率分布のデータを格納する第１のデータ格納部に格納された前記データに基づき、実行時間に遅延時間を加える場合における複数の時間区間の各々の確率を定義し且つ前記秘密情報の複数の値について共通である第２の確率分布を生成するステップと、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布と前記第２の確率分布とに基づき、当該秘密情報の値についての実行時間の確率分布を前記第２の確率分布に変換するためのデータを生成し、第２のデータ格納部に格納するステップと、
を含み、コンピュータが実行するデータ生成方法。
【請求項１４】
前記変換するためのデータと、当該変換するためのデータに基づき実際の実行時間についての遅延時間を決定するプログラムと、前記処理のためのプログラムとを含む、プロセッサで実行可能なプログラムを生成するステップ
をさらに含む請求項１３記載のデータ生成方法。
【請求項１５】
秘密情報の複数の値の各々について、当該秘密情報の値について行われた処理の実行時間の確率分布のデータを格納する第１のデータ格納部と、
前記第１のデータ格納部に格納された前記データに基づき、実行時間に遅延時間を加える場合における複数の時間区間の各々の確率を定義し且つ前記秘密情報の複数の値について共通である第２の確率分布を生成する第１の生成部と、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布と前記第２の確率分布とに基づき、当該秘密情報の値についての実行時間の確率分布を前記第２の確率分布に変換するためのデータを生成し、第２のデータ格納部に格納する第２の生成部と、
を有する情報処理システム。
【請求項１６】
秘密情報の複数の値のうちのある値と、当該ある値について行われた処理の実行時間とを取得するステップと、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布を、前記秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第２の確率分布へ変換するためのデータを格納するデータ格納部における、前記ある値についてのデータに基づき、前記ある値について行われた処理の実行時間についての遅延時間を決定するステップと、
を含み、コンピュータが実行する情報処理方法。
【請求項１７】
秘密情報の複数の値のうちのある値と、当該ある値について行われた処理の実行時間とを取得するステップと、
前記秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布を、前記秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第２の確率分布へ変換するためのデータを格納するデータ格納部における、前記ある値についてのデータに基づき、前記ある値について行われた処理の実行時間についての遅延時間を決定するステップと、
を、コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、耐タンパー技術に関する。
【背景技術】
【０００２】
ソフトウエアやハードウエアの動作の実行時間は、通常ばらつきがあり、確率的に異なるため、何らかの確率分布に従っていると見做すことができる。ソフトウエアやハードウエアの動作の実行時間が秘密情報に依存し、秘密情報の内容に応じて実行時間の確率分布が異なるとき、繰り返し実行時間を観測し、実行時間の確率分布を推定することによって、秘密情報の内容を推測できることがある。このような秘密情報の推測やこれに基づく攻撃をタイミング攻撃と呼ぶ。
【０００３】
タイミング攻撃対策についての主な従来技術としては、以下のものが知られている。
（Ａ）一定時間の遅延を加える方式（例えば、非特許文献１）
（Ｂ）ランダムな時間の遅延を加える方式（例えば、特許文献１）
（Ｃ）バケッティング（bucketing）（例えば、非特許文献２）
（Ｄ）出力時刻が一定時刻になるように遅延を加える方式（例えば、非特許文献３）
（Ｅ）ランダム化（例えば、非特許文献４におけるブラインディング（blinding））
【０００４】
方式（Ａ）は、例えば２種類の秘密情報がある場合、それぞれについて実行時間の確率分布を生成し、それらの期待値又は中央値の差だけ、期待値又は中央値の小さい方の実行時間に、遅延を加える技術である。このような方式（Ａ）を採用しても、実行時間の確率分布がそのままシフトするだけなので、タイミング攻撃を行って確率分布の差から秘密情報の推測を行うことができる。
【０００５】
方式（Ｂ）は、一様な確率分布から遅延時間をランダムに選び、実行時間を遅延させる技術である。しかしながら、例えば２種類の秘密情報がある場合、ランダムな遅延時間を実行時間に加えるだけでは、それらの実行時間の確率分布は完全には一致しない。そのため、タイミング攻撃を行って確率分布の差から秘密情報の推測を行うことができる。
【０００６】
方式（Ｃ）は、実行時間を、それぞれ時間範囲を表す複数のバケットに分類し、分類先の時間範囲の最終時刻まで実行時間を遅延させる技術である。実行時間からの情報漏洩についてそれほど効果はなく、バケット数が多いほど情報漏洩が多くなり、バケット数を減らすと遅延によるオーバーヘッドが大きくなることが知られている。
【０００７】
方式（Ｄ）は、実行時間がどのような時間であっても、最長の実行時間になるように遅延を加える技術である。実行時間は常に同じであるから、実行時間からの情報漏洩を完全になくすことができるが、オーバーヘッドは非常に大きい。
【０００８】
方式（Ｅ）は、同じ計算結果を得られるが実行時間が異なるような別の計算方式をランダムに選択する技術である。一般的に、同じ計算結果を得られる別の計算方式が存在するとは限られないため、特定の用途にのみ適用可能な技術である。例えば、方式（Ｅ）の一種であるブラインディングは、特定の暗号にのみ適用可能な技術である。
【０００９】
このように、十分なタイミング攻撃対策がなされているとはいえない場合がある。また、情報漏洩を少なくすると、遅延によるオーバーヘッドが大きくなる場合もある。さらに、汎用的に適用できない場合もある。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１４−１９２７９３号公報
【非特許文献】
【００１１】
【非特許文献１】Tom Chothia, Apratim Guha:"A Statistical Test for Information Leaks Using Continuous Mutual Information", Proc. the 24th IEEE Computer Security Foundations Symposium, pp.177-190, 2011.
【非特許文献２】B.Koepf and M. Duermuth, "A provably secure and efficient countermeasure against timing attacks," Proc. the 22nd IEEE Computer Security Foundations Symposium, pp.324-335, 2009.
【非特許文献３】Andreas Haeberlen, Benjamin C. Pierce, and Arjun Narayan, "Differential Privacy Under Fire", USENIXSecurity Symposium 2011.
【非特許文献４】Boris Koepf, Geoffrey Smith: "Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks", Proc. the 23rd IEEE Computer Security Foundations Symposium, pp.44-56, 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、本発明の目的は、一側面として、タイミング攻撃対策の新たな技術を提供することである。
【課題を解決するための手段】
【００１３】
本発明に係る第１の情報処理方法は、（Ａ）秘密情報の複数の値の各々について、当該秘密情報の値について行われた処理の実行時間の確率分布のデータを格納する第１のデータ格納部に格納されたデータに基づき、実行時間に遅延時間を加える場合における複数の時間区間の各々の確率を定義し且つ秘密情報の複数の値について共通である第２の確率分布を生成するステップと、（Ｂ）秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布と第２の確率分布とに基づき、当該秘密情報の値についての実行時間の確率分布を第２の確率分布に変換するためのデータを生成し、第２のデータ格納部に格納するステップとを含む。
【００１４】
本発明に係る第２の情報処理方法は、（Ａ）秘密情報の複数の値のうちのある値と、当該ある値について行われた処理の実行時間とを取得するステップと、（Ｂ）秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布を、秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第２の確率分布へ変換するためのデータを格納するデータ格納部における、当該ある値についてのデータに基づき、当該ある値について行われた処理の実行時間についての遅延時間を決定するステップとを含む。
【発明の効果】
【００１５】
一側面によれば、タイミング攻撃に対抗可能になる。
【図面の簡単な説明】
【００１６】
【図１】図１は、実施の形態の概要（設計フェーズ）を説明するための図である。
【図２】図２は、実施の形態の概要（適用フェーズ）を説明するための図である。
【図３】図３は、実施の形態において設計フェーズの処理を実行する情報処理装置の機能ブロック図である。
【図４】図４は、実施の形態において設計フェーズの処理フローを示す図である。
【図５】図５は、最遅分布生成処理の処理フローを示す図である。
【図６】図６は、部分分布算出処理の処理フローを示す図である。
【図７】図７は、確率分布の２つの例を示す図である。
【図８】図８（ａ）及び（ｂ）は、最遅分布生成処理の第１段階を説明するための図である。
【図９】図９（ａ）及び（ｂ）は、最遅分布生成処理の第２段階を説明するための図である。
【図１０】図１０は、最遅分布の一例を示す図である。
【図１１】図１１は、テーブル生成処理の処理フローを示す図である。
【図１２】図１２は、テーブル生成処理の処理フローを示す図である。
【図１３】図１３（ａ）及び（ｂ）は、テーブル生成処理で生成されるテーブルの例を示す図である。
【図１４】図１４は、実施の形態において適用フェーズで用いられるプログラム又はハードウエアのモジュール構成例を示す図である。
【図１５】図１５は、適用フェーズの処理フローを示す図である。
【図１６】図１６は、出力時刻を模式的に示す図である。
【図１７】図１７は、テーブルを更新する際の処理フローを示す図である。
【図１８】図１８は、近似最遅分布生成処理の処理フローを示す図である。
【図１９】図１９は、近似最遅分布生成処理の処理フローを示す図である。
【図２０】図２０は、不定区間ベース目標分布生成処理の処理フローを示す図である。
【図２１】図２１は、他の目標確率分布の一例を示す図である。
【図２２】図２２は、コンピュータ装置のブロック構成図である。
【発明を実施するための形態】
【００１７】
［実施の形態１］
まず、本実施の形態に係る処理の概要を説明する。
【００１８】
本実施の形態では、処理は２つのフェーズに分けられる。すなわち、設計フェーズと適用フェーズである。
【００１９】
図１を用いて設計フェーズの概要を説明する。例えば、秘密情報の値がｓ0とｓ1の２つであるものとする。そして、ｓ0について所定の処理（例えば暗号化処理）を実行する場合における実行時間の確率分布λ0と、ｓ1について同じ所定の処理を実行する場合における実行時間の確率分布λ1とを得る。図１の左側には、確率分布λ0及びλ1の例を示す。
【００２０】
確率分布λ0では、実行時間が０秒以上１秒未満である区間１の確率が０．２であり、実行時間が１秒以上２秒未満である区間２の確率が０．５であり、実行時間が２秒以上３秒未満である区間３の確率が０．３である。また、確率分布λ1では、実行時間が０秒以上１秒未満である区間１の確率が０．３あり、実行時間が１秒以上２秒未満である区間２の確率が０．２であり、実行時間が２秒以上３秒未満である区間３の確率が０．５である。
【００２１】
このように秘密情報の値毎に異なる実行時間の確率分布が得られると、タイミング攻撃によって秘密情報の値が分かってしまう恐れがあるため、本実施の形態では、秘密情報の値がどのような値であっても、あたかも実行時間の確率分布が同一に見えるように、実行時間に確率的に遅延時間を加えて処理結果を出力することにする。「確率的に」というのは、一様分布に従ってランダムに、ということとは異なる。
【００２２】
そのため、本実施の形態では、実行時間に遅延時間を加えた処理時間の確率分布が、秘密情報のいずれの値についても同一になるようにするため、目標とする確率分布（以下、目標確率分布）を、秘密情報の各値についての確率分布から生成する。特に、遅延時間を加える場合のオーバーヘッドを最小化すべく、本実施の形態では、平均遅延時間も最悪遅延時間も最小になるような最遅分布（laziest distribution）を目標確率分布として生成する。
【００２３】
例えば、図１の右上に示す目標確率分布を生成する。この例では、実行時間が０秒以上１秒未満である区間１の確率が０．２であり、実行時間が１秒以上２秒未満である区間２の確率が０．３であり、実行時間が２秒以上３秒未満である区間３の確率が０．５である。
【００２４】
なお、本実施の形態では、実際には、区間１に属する場合には、区間１の終期である１秒で処理結果を出力し、区間２に属する場合には、区間２の終期である２秒で処理結果を出力し、区間３に属する場合には、区間３の終期である３秒で処理結果を出力する。出力時間についてこのような完全に離散化された形で処理結果を出力する。
【００２５】
このような目標確率分布を生成した場合、秘密情報の値ｓ0についての実行時間の確率分布λ0とは差があるため、図１の左上に模式的に示すように、区間２に属する実行時間が得られた場合、０．２／０．５＝０．４の確率で、区間３に属するように遅延時間を加えることになる。同様に、秘密情報の値ｓ1についての実行時間の確率分布λ0とは差があるため、図１の左下に模式的に示すように、区間１に属する実行時間が得られた場合、０．１／０．３＝０．３３３の確率で、区間２に属するように遅延時間を加えることになる。
【００２６】
すなわち、設計フェーズでは、秘密情報の値毎に、当該値についての実行時間の確率分布を目標確率分布に変換するための変換ルールを生成しておく。秘密情報の値ｓ0については変換ルール０として、区間２に属する実行時間が得られた場合０．４の確率で区間３に属するように遅延時間を加える、というルールが設定される。また、秘密情報の値ｓ1については変換ルール１として、区間１に属する実行時間が得られた場合０．３３３の確率で区間２に属するように遅延時間を加える、というルールが設定される。なお、変換と述べたが、変形や変更という場合もある。
【００２７】
このようなルールは、以下の説明ではテーブル形式でデータが用意される。
【００２８】
次に、図２を用いて適用フェーズの概要を説明する。実際に、秘密情報の値について所定の処理を実行する場合には、その秘密情報の値ｓiと、実行時間ｔuとを取得して、ｓiに対応する変換ルールｉを適用する。例えば、ｓi＝ｓ0であれば、変換ルール０が適用される。また、実行時間ｔuが属する初期的な区間が区間２であるとする。そうすると、０．４の確率で、区間３に属するように遅延時間が加えられることになる。ここで確率的に該当区間が決定されることになる。
【００２９】
そして、該当区間が区間２のままであれば２秒で処理結果は出力され、該当区間が区間３に変更されれば３秒で処理結果が出力される。このようにして出力時刻が決定される。
【００３０】
以上のような処理を行うことで、λ0のような確率分布は、秘密情報の各値について共通の目標確率分布に変換されることになるので、秘密情報の値がタイミング攻撃にて漏洩することはなくなる。また、目標確率分布が最遅分布であれば、遅延時間によるそのオーバーヘッドも最小化される。
【００３１】
なお、プロセッサがプログラムを実行することで所定の処理を実行する場合もあれば、所定の処理を実行するための回路を含むハードウエアにより所定の処理を実行する場合もある。これに対して、適用フェーズの実装態様は、所定の処理の実装態様に合わせることができ、ハードウエアでもソフトウエアでもよい。
【００３２】
次に、設計フェーズに係る処理を行う情報処理装置の構成例を図３に示す。
【００３３】
本実施の形態に係る情報処理装置１００は、入力データ格納部１０１と、第１確率分布生成部１０３と、第１確率分布格納部１０５と、第２確率分布生成部１０７と、第２確率分布格納部１０９と、テーブル生成部１１１と、テーブル格納部１１３と、モジュール格納部１１５と、出力処理部１１６と、出力データ格納部１１７とを有する。
【００３４】
入力データ格納部１０１は、例えば、秘密情報の各値について所定の処理を実行するプログラム等のデータを格納する。なお、入力データ格納部１０１は、秘密情報の各値について実行時間の計測結果を格納している場合や、所定の処理を実行するプログラムのソースコードを格納している場合もある。
【００３５】
第１確率分布生成部１０３は、入力データ格納部１０１に格納されているプログラム等のデータを用いて、秘密情報の各値についての実行時間の情報を取得し、秘密情報の各値についての確率分布を生成して、そのデータを第１確率分布格納部１０５に格納する。
【００３６】
第２確率分布生成部１０７は、第１確率分布格納部１０５に格納されている、秘密情報の各値についての確率分布から、目標確率分布を生成し、そのデータを第２確率分布格納部１０９に格納する。テーブル生成部１１１は、第１確率分布格納部１０５に格納されていている、秘密情報の各値についての確率分布と、第２確率分布格納部１０９に格納されている目標確率分布とから、秘密情報の各値について、当該値についての確率分布を目標確率分布に変換するための変換ルールを表すテーブルを生成し、テーブル格納部１１３に格納する。
【００３７】
モジュール格納部１１５は、例えば、適用フェーズの処理を実行する出力遅延モジュール（プログラムのソースコード等）のデータを格納する。出力処理部１１６は、例えば、モジュール格納部１１５に格納されている出力遅延モジュールと、テーブル格納部１１３に格納されているテーブルとを併せて出力データ格納部１１７に格納する。
【００３８】
なお、プログラムで実装する場合には、出力処理部１１６は、コンパイラの機能を有している場合がある。この場合、出力処理部１１６は、入力データ格納部１０１に格納されている所定の処理を実行するプログラムのソースコードと、モジュール格納部１１５に格納されている出力遅延モジュールのプログラムのソースコードと、テーブル格納部１１３に格納されているテーブルとをコンパイルして、目的とする情報処理装置のプロセッサで実行可能なプログラムを生成して、出力データ格納部１１７に格納する。
【００３９】
次に、図４乃至図１３を用いて、図３に示した情報処理装置の処理内容について説明する。
【００４０】
まず、第１確率分布生成部１０３は、秘密情報の各値ｓi（ここではｋ個の値があるものとする）について実行時間をＮ回計測し、確率分布λiを生成し、第１確率分布格納部１０５に格納する（図４：ステップＳ１）。
【００４１】
例えば、入力データ格納部１０１に格納されているプログラムを、目的とする実行環境をシミュレートした上で秘密情報の値毎にＮ回実行することで実行時間を計測してもよい。目的とする実行環境で実際にプログラムを実行して計測した実行時間を取得してもよい。
【００４２】
実行時間ｔは連続値を取り得るため、本実施の形態では、時間軸を複数の区間（時間区間とも呼ぶ）に分割し、ｔを離散化する。ｍ個区間が存在する場合、各区間を、［ｌ0，ｌ1），［ｌ1，ｌ2），...，［ｌm-1，ｌm）と表すものとする。また、時刻ｔが属する区間の最小値をｌ（ｔ）と表し、その次の区間の最小値をｒ（ｔ）と表し、ｔの属する区間を［ｌ（ｔ），ｒ（ｔ））と表すものとする。なお、区間については予め定義しておく。
【００４３】
従って、Ｎ回測定した実行時間のうち、各区間［ｌj，ｌj+1）（ｊ＝０，１，２，．．．，ｍ−１）に含まれる計測値の個数ｃjをカウントして、確率λ［ｌj，ｌj+1］＝ｃj／Ｎとする。
【００４４】
なお、本ステップでは、所定の処理を実行するプログラムのソースコードを静的に解析し、秘密情報の各値ｓi毎に実行ステップ数の確率分布を推定し、確率分布λiとして用いるようにしてもよい。
【００４５】
また、事前に確率分布λiが取得できるのであれば、上で述べたような計測処理などは行わずに済むが、上で述べたような区間の定義に従って離散化しておくものとする。
【００４６】
次に、第２確率分布生成部１０７は、目標確率分布生成処理を実行し、生成した目標確率分布μのデータを第２確率分布格納部１０９に格納する（ステップＳ３）。本実施の形態では、最遅分布を目標確率分布とする。
【００４７】
最遅分布とは、加える平均遅延時間及び最悪遅延時間が最も短い分布である。より詳細には以下のように定義される。すなわち、ｋ個の確率分布λ1，λ2，...，λkの最遅分布μとは、任意のｑ∈［０，１］に対して、μのｑ分位点がλ1，λ2，...，λkのｑ分位点のうち最大のものに等しいような分布である。例えば、μの０．２５分位点（最小時刻から最大時刻に向かって０．２５：０．７５でμを分割するような時刻）は、全てのλiの０．２５分位点の中で最も遅い時刻である。
【００４８】
なお、一般的に、実数ｑ∈［０，１］に対して、分布をｑ：（１−ｑ）に分割する値をｑ分位点（q-quantile）という。但し、本実施の形態では、各確率分布λiは離散化されており、区間毎に確率が定義されているので、λiのｑ分位点Ｑq,iは、上で定義した区間の端点と一般的には一致しない。このような場合に線形補間によりｑ分位点を計算することが一般的であるが、本実施の形態では、切り上げ計算で簡略化する。具体的には、０≦ｑ'＜ｑ≦ｑ"≦１と区間［ｌj，ｌj+1）に対して、ｌjがλiのｑ'分位点であり、ｌj+1がλiのｑ"分位点である場合、λiのｑ分位点Ｑq,iをＱq,i＝ｌj+1と定義する。
【００４９】
目標確率分布として最遅分布を生成する処理を、図５乃至図１０を用いて説明する。
【００５０】
まず、第２確率分布生成部１０７は、最遅分布μを初期化する（図５：ステップＳ１１）。具体的には、最遅分布μを空にする。次に、第２確率分布生成部１０７は、ｑが非ゼロであるか否かを判断する（ステップＳ１３）。ｑは、ここではローカルな変数であり、初期的にはｑには非ゼロの任意の値を入れておく。
【００５１】
ｑが非ゼロであれば、第２確率分布生成部１０７は、各ｉ＝１，２，...，ｋについて確率分布λiの最短実行時間を計算し、これらのｋ個の最短実行時間のうち最大のものをｖmaxに設定する（ステップＳ１５）。なお、ｑがゼロであれば、処理は完了したので、呼び出し元の処理に戻る。
【００５２】
ここで、確率について記法を定義しておく。確率分布λに従う実行時間ｔがａ以上である確率を、λ［ｔ≧ａ］と記し、ｂ未満である確率をλ［ｔ＜ｂ］と記し、ａ以上ｂ未満である確率をλ［ａ≦ｔ＜ｂ］と記すものとする。また、λ［ｊ］＝λ［ｌj≦ｔ＜ｌj+1］とおく。
【００５３】
そして、離散化された確率分布λのサポートを、supp（λ）＝｛ｔ∈［ｌj，ｌj+1）｜λ［ｌj≦ｔ＜ｌj+1］＞０｝とする。そうすると、確率分布λに従う実行時間が取り得る値の最小値（すなわち離散化された最短実行時間）は、min supp（λ）と書ける。
【００５４】
すなわち、ステップＳ１５の処理では、ｋ個の確率分布λ1，λ2，...，λkの最短実行時間min supp（λ1），min supp（λ2），...，min supp（λk）のうちの最大値を特定する。
【００５５】
そして、第２確率分布生成部１０７は、ｖmaxが属する区間［ｌj，ｌj+1）を特定する（ステップＳ１７）。すなわち、［ｌj，ｌj+1）＝［ｌ（ｖmax），ｒ（ｖmax））とする。
【００５６】
その後、第２確率分布生成部１０７は、各ｉ＝１，２，...，ｋについて、確率分布λiにおいて実行時間がｌj+1未満である確率λi［ｔ＜ｌj+1］を計算し、これらのｋ個の確率のうち最小のものをｑに設定する（ステップＳ１９）。第２確率分布生成部１０７は、このようにして得られたｑを、最遅分布μの区間［ｌj，ｌj+1）の確率として設定する（ステップＳ２１）。
【００５７】
その後、第２確率分布生成部１０７は、各確率分布λiについて、部分分布算出処理を実行する（ステップＳ２３）。すなわち、λiからｑだけを取り除いた部分分布（sub-distribution）を、新たなλiに設定する処理を実行する。なお、通常の確率分布と違い、部分分布では、確率の総和が１以下である。この部分分布算出処理については、図６を用いて説明する。なお、部分分布算出処理の後、処理はステップＳ１３に戻る。
【００５８】
なお、図６に示す処理は、１つの確率分布λiについての処理を示すものであり、ステップＳ２３では、各確率分布λiについて図６の処理を繰り返すことになる。
【００５９】
第２確率分布生成部１０７は、ｑが非ゼロであるか否かを判断する（図６：ステップＳ３１）。ｑは、初期的には、目標確率分布生成処理から渡された値である。もし、ｑがゼロであれば、処理は呼び出し元の処理に戻る。但し、ｑの値を呼び出し元の処理には戻さない。
【００６０】
一方、ｑが非ゼロであれば、第２確率分布生成部１０７は、確率分布λiの最短実行時間min supp（λi）をｗiに設定する（ステップＳ３３）。そして、第２確率分布生成部１０７は、ｗiが属する区間［ｌj，ｌj+1）を特定する（ステップＳ３５）。
【００６１】
そして、第２確率分布生成部１０７は、λi［ｌj≦ｔ＜ｌj+1］＞ｑであるか否かを判断する（ステップＳ３７）。ｗiが属する区間［ｌj，ｌj+1）の確率がｑより大きいか否かを判断するものである。
【００６２】
この条件を満たす場合には、第２確率分布生成部１０７は、区間［ｌj，ｌj+1）の確率からｑを差し引き、ｑを０に設定する（ステップＳ３９）。そして処理はステップＳ３１に戻る。
【００６３】
式で表せば、以下のとおりである。
λi［ｌj≦ｔ＜ｌj+1］＝λi［ｌj≦ｔ＜ｌj+1］−ｑ
ｑ＝０
【００６４】
一方、ステップＳ３７の条件を満たさない場合には、第２確率分布生成部１０７は、取り除きたい確率ｑから、ｗiが属する区間［ｌj，ｌj+1）の確率を差し引き、ｗiが属する区間［ｌj，ｌj+1）の確率をゼロに設定する（ステップＳ４１）。そして処理はステップＳ３１に戻る。
【００６５】
式に表せば、以下のとおりである。
ｑ＝ｑ−λi［ｌj≦ｔ＜ｌj+1］
λi［ｌj≦ｔ＜ｌj+1］＝０
【００６６】
以上のような処理を実行すれば、部分分布が算出され、最遅分布生成処理において区間の確率を決定することができるようになる。
【００６７】
ここまでの処理について、図７で示した例を用いて具体的に説明しておく。なお、これらの確率分布λ0及びλ1は、図１の左側に示した２つの確率分布λ0及びλ1と同じである。
【００６８】
これらの確率分布に対して最遅分布μを生成する場合には、最遅分布生成処理の１回目のループでは、最短実行時間を含む区間１が特定され、区間１以下の確率のうち最も小さい確率０．２がｑに設定される。すなわち、図８（ａ）に示すように、最遅分布μの区間１の確率は０．２になる。また、図８（ｂ）に示すように、部分分布算出処理において、確率分布λ0の区間１の確率はゼロになり、確率分布λ1の区間１の確率は０．１に減ぜられる。
【００６９】
最遅分布生成処理の２回目のループでは、図８（ｂ）から、最短実行時間が最大となる区間２が特定され、区間２以下の確率のうち最も小さい確率０．３がｑに設定される。すなわち、図９（ａ）に示すように、最遅分布μの区間２の確率は０．３になる。また、図９（ｂ）に示すように、部分分布算出処理において、確率分布λ0の区間２の確率は０．２に減ぜられ、確率分布λ1の区間１及び２の確率はゼロになる。
【００７０】
最遅分布生成処理の３回目のループでは、図９（ｂ）から、最短実行時間が最大となる区間３が特定され、区間３以下の確率のうち最も小さい確率０．５がｑに設定される。すなわち、図１０に示すように、最遅分布μの区間３の確率は０．５になる。また、部分分布算出処理において、確率分布λ0の区間２及び３の確率は合わせて０．５減ぜられてともにゼロになり、確率分布λ1の区間３の確率もゼロになる。以上のように、図１０に示すような最遅分布μが得られる。
【００７１】
図４の処理の説明に戻って、テーブル生成部１１１は、第１確率分布格納部１０５に格納された各確率分布λiに対して、各確率分布λiを目標確率分布へ変換する変換ルールに対応するテーブルの生成処理を実行し、生成されたテーブルをテーブル格納部１１３に格納する（ステップＳ５）。テーブル生成処理の処理フローについては、図１１乃至図１３を用いて説明する。なお、図１１及び図１２に示す処理は、１つの確率分布λiについての処理を示すものであり、ステップＳ５では、各確率分布λiについて図１１及び図１２の処理を繰り返すことになる。
【００７２】
テーブル生成部１１１は、初期処理として、λにλiを設定し、ローカルな配列γiについては空に設定する（図１１：ステップＳ５１）。
【００７３】
そして、テーブル生成部１１１は、λが非空である（λ≠φ）か否かを判断する（ステップＳ５３）。この条件を満たす場合には、テーブル生成部１１１は、確率分布λにおける実行時間の最小値をｗ1に設定する（ステップＳ５５）。すなわち、ｗ1＝min supp（λ）とする。
【００７４】
そして、テーブル生成部１１１は、ｗ1が属する区間［ｌu，ｒu）（＝［ｌ(ｗ1)，ｒ（ｗ1））。ここでは区間ｕとも記す。）を特定する（ステップＳ５７）。
【００７５】
また、テーブル生成部１１１は、目標確率分布μにおける実行時間の最小値をｗ2に設定する（ステップＳ５９）。すなわち、ｗ2＝min supp（μ）とする。さらに、テーブル生成部１１１は、ｗ2が属する区間［ｌv，ｒv）（＝［ｌ(ｗ2)，ｒ（ｗ2））。ここでは区間ｖとも記す。）を特定する（ステップＳ６１）。そして処理は端子Ａを介して図１２の処理に移行する。
【００７６】
図１２の処理の説明に移行して、テーブル生成部１１１は、確率分布λにおいてｗ1が属する区間ｕの確率と、目標確率分布μにおいてｗ2が属する区間ｖの確率のうち、小さい方の確率をｑに設定する（ステップＳ６５）。すなわち、以下のように表される。
ｑ＝ｍｉｎ（λ［ｌu≦ｔ＜ｒu］，μ［ｌv≦ｔ＜ｒv］）
【００７７】
そして、テーブル生成部１１１は、γi［ｕ］［ｖ］＝ｑと設定する（ステップＳ６７）。
【００７８】
その後、テーブル生成部１１１は、確率分布λについての区間ｕの確率がｑとなっているか否かを判断する（ステップＳ６９）。すなわち、確率分布λにおいてｗ1が属する区間ｕの確率は、目標確率分布μにおいてｗ2が属する区間ｖの確率より大きくないか否かを判断している。
【００７９】
ステップＳ６９の条件が満たされる場合には、テーブル生成部１１１は、確率分布λについてのｗ1が属する区間ｕの確率をゼロに設定する（ステップＳ７１）。すなわち、λ［ｌu≦ｔ＜ｒu］＝０である。
【００８０】
また、テーブル生成部１１１は、目標確率分布μについてのｗ2が属する区間ｖの確率からｑを差し引く（ステップＳ７３）。すなわち、μ［ｌv≦ｔ＜ｒv］＝μ［ｌv≦ｔ＜ｒv］−ｑである。そして処理は端子Ｂを介して図１１のステップＳ５３に戻る。
【００８１】
一方、ステップＳ６９の条件が満たされない場合には、テーブル生成部１１１は、目標確率分布μについてのｗ2が属する区間ｖの確率をゼロに設定する（ステップＳ７５）。すなわち、μ［ｌv≦ｔ＜ｒv］＝０である。
【００８２】
また、テーブル生成部１１１は、確率分布λについてのｗ1が属する区間ｕの確率からｑを差し引く（ステップＳ７７）。すなわち、λ［ｌu≦ｔ＜ｒu］＝λ［ｌu≦ｔ＜ｒu］−ｑである。そして処理は端子Ｂを介して図１１のステップＳ５３に戻る。
【００８３】
図１１の処理の説明に戻って、ステップＳ５３でλが空であると判断されると、テーブル生成部１１１は、ｕ（１乃至ｍ）及びｖ（１乃至ｍ）の組み合わせ毎に、Ｔi［ｕ，ｖ］＝γi［ｕ］［ｖ］／λi［ｕ］を算出して、テーブルを生成し、テーブル格納部１１３に格納する（ステップＳ６３）。そして呼び出し元の処理に戻る。
【００８４】
テーブル生成処理について、図７乃至図１０を用いて説明した例で説明する。
【００８５】
確率分布λ0については、図１１及び１２の１回目のループにおいて、ｗ1＝１、ｗ2＝１となり、図７上段のλ0と図１０のμからして、ｑ＝０．２が設定される。すなわち、γ0[1][1]＝０．２となる。
【００８６】
確率分布λ0について、図１１及び１２の２回目のループにおいて、ｗ1＝２、ｗ2＝２となり、図７上段のλ0から確率０．２を除いたものと図１０のμから確率０．２を除いたものからして、ｑ＝０．３が設定される。すなわち、γ0[2][2]＝０．３となる。
【００８７】
確率分布λ0について、図１１及び１２の３回目のループにおいて、ｗ1＝２、ｗ2＝３となり、図７上段のλ0から確率０．５を除いたものと図１０のμから確率０．５を除いたものからして、ｑ＝０．２が設定される。すなわち、γ0[2][3]＝０．２となる。
【００８８】
確率分布λ0について、図１１及び１２の４回目のループにおいて、ｗ1＝３、ｗ2＝３となり、図７上段のλ0から確率０．７を除いたものと図１０のμから確率０．７を除いたものからして、ｑ＝０．３が設定される。すなわち、γ0[3][3]＝０．３となる。
【００８９】
従って、ステップＳ６３で図１３（ａ）に示すようなテーブルが生成されるようになる。具体的には、確率分布λ0の区間ｕ＝１に属する実行時間であれば、目標確率分布μにおける区間ｖ＝１に必ず属することになる。区間ｕ＝２に属する実行時間であれば、６０％（＝０．３／０．５＝０．６）の確率で区間ｖ＝２に属することになるが、４０％（＝０．２／０．５＝０．４）の確率で区間ｖ＝３に変更される。すなわち、このような確率で区間を超えた遅延時間が付加される。区間ｕ＝３に属する実行時間であれば、区間ｖ＝３に必ず属することになる。
【００９０】
また、確率分布λ1については、図１１及び１２の１回目のループにおいて、ｗ1＝１、ｗ2＝１となり、図７下段のλ1と図１０のμからして、ｑ＝０．２が設定される。すなわち、γ1[1][1]＝０．２となる。
【００９１】
確率分布λ1について、図１１及び１２の２回目のループにおいて、ｗ1＝１、ｗ2＝２となり、図７下段のλ1から確率０．２を除いたものと図１０のμから確率０．２を除いたものからして、ｑ＝０．１が設定される。すなわち、γ1[1][2]＝０．１となる。
【００９２】
確率分布λ1について、図１１及び１２の３回目のループにおいて、ｗ1＝２、ｗ2＝２となり、図７下段のλ1から確率０．３を除いたものと図１０のμから確率０．３を除いたものからして、ｑ＝０．２が設定される。すなわち、γ1[2][2]＝０．２となる。
【００９３】
確率分布λ1について、図１１及び１２の４回目のループにおいて、ｗ1＝３、ｗ2＝３となり、図７下段のλ1から確率０．５を除いたものと図１０のμから確率０．５を除いたものからして、ｑ＝０．５が設定される。すなわち、γ1[3][3]＝０．５となる。
【００９４】
従って、ステップＳ６３で図１３（ｂ）に示すようなテーブルが生成されるようになる。具体的には、確率分布λ1の区間ｕ＝１に属する実行時間であれば、目標確率分布μにおける区間ｖ＝１に２／３（＝０．２／０．３＝０．６６６）の確率で属することになるが、１／３（＝０．１／０．３＝０．３３３）の確率で区間ｖ＝２に変更される。すなわち、このような確率で区間を超えた遅延時間が付加される。また、区間ｕ＝２に属する実行時間であれば、区間ｖ＝２に必ず属することになる。さらに、区間ｕ＝３に属する実行時間であれば、区間ｖ＝３に必ず属することになる。
【００９５】
このように各区間について、区間内において遅延時間を加える確率、区間を超えて遅延時間を加える確率を含むテーブルが得られる。
【００９６】
以上述べたような変換ルールとしてのテーブルが用意されれば、適用フェーズでは簡単な処理で、どのような遅延時間を加えればよいのかを決定できるようになる。
【００９７】
図４の処理の説明に再度戻って、出力処理部１１６は、例えば、生成されたテーブルと出力遅延モジュールと他の機能モジュール（所定の処理を実行するプログラムなどのモジュール等）とを含むプログラム又はハードウエアのデータを、出力データ格納部１１７に出力して格納する（ステップＳ７）。
【００９８】
本ステップについては様々なバリエーションが存在する。生成されたテーブルを出力して、情報処理装置１００のユーザが、当該テーブルを用いる出力遅延モジュールと他の機能モジュールとを組み合わせる場合もある。
【００９９】
プログラムで実装する場合には、生成されたテーブルと、出力遅延モジュールと、他の機能モジュールとをコンパイルして、目的とする実行環境のプロセッサで実行可能なプログラムを生成する場合もある。
【０１００】
ハードウエアで実装する場合には、例えば、生成されたテーブルを出力遅延モジュールに組み込んだ回路などの設計データや、そのような回路をさらに他の機能モジュールに組み入れた回路などの設計データなどを出力するような場合もある。
【０１０１】
さらに、上で生成したテーブルを適用フェーズにおいて更新する処理を行う場合には、テーブル更新モジュールを追加する場合もある。
【０１０２】
いずれにせよ、秘密情報の各値についての実行時間の確率分布から、それらに共通の目標確率分布μを生成し、実行時間の各確率分布を目標確率分布μに変換するためのデータが生成できるようになった。
【０１０３】
次に、適用フェーズにおいて用いられるプログラム又はハードウエアのモジュール構成例を、図１４に示す。適用フェーズにおいて用いられるプログラム又はハードウエア２００は、本来の機能モジュール２１０と、出力遅延モジュール２２０と、場合によってはテーブル更新モジュール２３０とを含む。本来の機能モジュール２１０は、例えば暗号化処理など秘密情報についての処理を行うためのモジュールであり、その他の処理を行うためのモジュールを含むようにしてもよい。出力遅延モジュール２２０は、設計フェーズで生成したテーブル２２１のデータを含み、概要で説明したように実行時間の該当区間を決定し、処理結果の出力時刻を決定するとともに、当該出力時刻に処理結果を出力するためのモジュールである。
【０１０４】
テーブル更新モジュール２３０は、秘密情報の各値について実際の実行時間のデータを蓄積する実行時間データベース（ＤＢ）２３１を含み、実際の実行時間が十分に蓄積されたのちに、設計フェーズと同様の処理（確率分布を生成する処理以降）を実行することで、テーブル２２１を更新するためのモジュールである。設計フェーズでは、あくまで模擬的に実行した結果として実行時間を測定したり、ソースコードの実行ステップ数から推定するなどして実行時間の確率分布を生成していたが、適用フェーズでは実際の環境下における実際の実行時間を収集できるので、より適切な確率分布さらには目標確率分布を生成でき、適切な遅延時間を決定できるようになる。
【０１０５】
なお、プログラムで実装する場合には、実行環境において採用されているプロセッサによって図１４で示したような構成を有するプログラムが実行され、以下で述べる機能が当該プロセッサを有する情報処理装置において実現される。以下の説明では、出力遅延モジュール２２０及びテーブル更新モジュール２３０を処理主体として便宜的に用いるが、これらのモジュールをプロセッサが実行することによって実現される出力遅延部及びテーブル更新部が本来の処理主体である。
【０１０６】
次に、図１５乃至図１７を用いて、図１４に示したような構成を有するプログラム又はハードウエアの動作フローを説明する。
【０１０７】
出力遅延モジュール２２０は、本来の機能モジュール２１０から秘密情報の値ｓiを取得する（図１５：ステップＳ１０１）。
【０１０８】
また、出力遅延モジュール２２０は、本来の機能モジュール２１０からｓiに対する実行時間ｔuを取得し、区間ｕを特定する（ステップＳ１０３）。例えば、本来の機能モジュール２１０の動作を監視しておき、実行時間を計測する。なお、出力遅延モジュール２２０は、テーブル２２１と共に区間の定義を保持しておくものとする。また、テーブル更新モジュール２３０が設けられている場合には、ｓiとｔuの組のデータを、実行時間ＤＢ２３１に蓄積する。
【０１０９】
さらに、出力遅延モジュール２２０は、０から１の間の実数ｐを一様分布からランダムに抽出する（ステップＳ１０５）。
【０１１０】
そして、出力遅延モジュール２２０は、ｓiに対応するテーブルＴi［ｕ，ｖ］をｖ＝１から累積してｐを超える最小のｖを特定する（ステップＳ１０７）。ステップＳ１０５とＳ１０７で、区間内で遅延時間を加えるのか、区間を超えて遅延時間を加えるのかが決定される。ｖ＝ｕであれば、区間内で遅延時間を加えることになり、ｖ＞ｕであれば、区間を超えて遅延時間を加えることになる。
【０１１１】
ｖが特定されると、出力遅延モジュール２２０は、ｌv+1になるまで遅延を付加して、処理結果を出力する（ステップＳ１０９）。すなわち、区間ｖの終期であるｌv+1に処理結果を出力する。単純に、区間ｖの終期ｌv+1−実行時間ｔuを遅延時間に設定して出力時刻を決定してもよい。出力遅延モジュール２２０が本処理を実行する時間を考慮するならば、実行時間ｔuの開始時刻を取得して、当該開始時刻＋ｌv+1を出力時刻として決定してもよい。
【０１１２】
なお、上で述べた目標確率分布（図１６上段）が生成されても、実際の確率分布は、図１６下段のように、出力時刻は、１秒、２秒、３秒とさらに離散化される。
【０１１３】
以上のような処理を実行すれば、どのような秘密情報の値であっても、同じ確率分布で処理結果が出力されるようになり、タイミング攻撃に対抗できるようになる。
【０１１４】
また、最遅分布が採用されれば、遅延時間を加えることによるオーバーヘッドも最小化される。
【０１１５】
さらに、ソフトウエアで実装する場合にもハードウエアで実装する場合でも、秘密情報を処理する所定の処理がどのような処理であっても実施の形態を適用できる。
【０１１６】
なお、上で述べたように、テーブル更新モジュール２３０が設けられる場合には、当該テーブル更新モジュール２３０は、図１７に示すような処理を実行する。
【０１１７】
すなわち、テーブル更新モジュール２３０は、例えば所定時間毎に、実行時間ＤＢ２３１に十分な量の実行時間のデータが蓄積されたか否かを判断する（図１７：ステップＳ１１１）。例えば、秘密情報の各値について所定個数の実行時間のデータが蓄積されているか否かを判断する。この条件を満たしていない場合には、処理は終了する。
【０１１８】
一方、ステップＳ１１１の条件を満たしている場合には、テーブル更新モジュール２３０は、設計フェーズのテーブル生成処理までを実行して、テーブル２２１を更新する（ステップＳ１１３）。具体的には、図４のステップＳ１のうち確率分布を生成する部分と、ステップＳ３及びＳ５を実行する。但し、設計フェーズとは異なる種類の目標確率分布を生成するようにしてもよい。例えば計算時間を優先してもよい。そして処理は終了する。
【０１１９】
このような処理を行えば、実際の実行環境における実際の実行時間による確率分布に従って、適切な目標確率分布を生成でき、さらには変換ルールを表すテーブルを更新できるようになる。さらに、設計段階で観測されていない希少事象における実行時間を考慮したり、物理的環境の変化などによって、実行時間の分布が変化したりした場合にも、テーブルが更新されるため、対処できるようになる。
【０１２０】
［実施の形態２］
第１の実施の形態では、目標確率分布として最遅分布を採用する場合を述べたが、秘密情報の各値についての確率分布λiによっては、ｑの値が非常に小さくなって、ループの実行回数が多くなってしまい、その結果として最遅分布の生成に時間がかかる場合があり得る。
【０１２１】
この計算時間を短縮するために、最遅分布を用いる場合よりもある程度長い遅延時間を加えることを許容し、最遅分布に近い分布（以下、近似最遅分布と呼ぶ）を生成するようにしてもよい。
【０１２２】
本実施の形態では、最遅分布を用いる場合と比べて、平均遅延時間をδだけ余分に遅延することを許容するものとする。最遅分布からの追加の平均遅延時間がδ以下である分布をδ−近似最遅分布（δ-approximate laziest distribution）と呼び、δを遅延の許容範囲と呼ぶ。そして、ｑの値がある閾値ξよりも小さいときに、δの範囲内で追加の遅延を加えてｑの値を大きくすることで、ループの実行回数を減らす。
【０１２３】
具体的には、図５の代わりに図１８及び図１９に示すような処理を実行する。
【０１２４】
まず、第２確率分布生成部１０７は、近似最遅分布μを初期化する（図１８：ステップＳ２０１）。具体的には、近似最遅分布μを空にする。次に、第２確率分布生成部１０７は、ｑが非ゼロであるか否かを判断する（ステップＳ２０３）。ｑは、ここではローカルな変数であり、初期的にはｑには非ゼロの任意の値を入れておく。
【０１２５】
ｑが非ゼロであれば、第２確率分布生成部１０７は、各ｉ＝１，２，...，ｋについて確率分布λiの最短実行時間を計算し、これらのｋ個の最短実行時間のうち最大のものをｖmaxに設定する（ステップＳ２０５）。なお、ｑがゼロであれば、処理は完了したので、呼び出し元の処理に戻る。
【０１２６】
そして、第２確率分布生成部１０７は、ｖmaxが属する区間［ｌj，ｌj+1）を特定する（ステップＳ２０７）。すなわち、［ｌj，ｌj+1）＝［ｌ（ｖmax），ｒ（ｖmax））とする。
【０１２７】
その後、第２確率分布生成部１０７は、各ｉ＝１，２，...，ｋについて、確率分布λiにおいて実行時間がｌj+1未満である確率λ［ｔ＜ｌj+1］を計算し、これらのｋ個の確率の中で最小のものをｑに設定する（ステップＳ２０９）。ここまでの処理は、図５のステップＳ１１乃至Ｓ１９とほぼ同じである。
【０１２８】
その後、本実施の形態では、第２確率分布生成部１０７は、ｑがξ以上であるか否かを判断する（ステップＳ２１１）。ξについてはあらかじめ設定しておく。この条件を満たす場合には、第２確率分布生成部１０７は、上で得られたｑを、近似最遅分布μの区間［ｌj，ｌj+1）の確率として設定する（ステップＳ２１３）。
【０１２９】
その後、第２確率分布生成部１０７は、各確率分布λiについて、ｑについての部分分布算出処理を実行する（ステップＳ２１５）。すなわち、λiからｑだけを取り除いた部分分布を、新たなλiに設定する処理を実行する。部分分布算出処理は、図６で示した処理である。なお、部分分布算出処理の後、処理はステップＳ２０３に戻る。
【０１３０】
一方、ステップＳ２１１の条件を満たさない場合には、処理は端子Ｃを介して図１９の処理に移行する。
【０１３１】
図１９の処理の説明に移行して、第２確率分布生成部１０７は、第１の緩和条件を満たす正の整数ｃが存在するか否かを判断する（ステップＳ２１７）。第１の緩和条件とは、各ｉ＝１，２，...，ｋについてλi［ｔ＜ｌj+c］≧ξ且つｌj+c−ｌj+1≦δである。そして処理はステップＳ２２１に移行する。すなわち、区間ｊではなく区間ｊ＋ｃ−１まで拡張してその範囲の最小の確率が閾値ξ以上となり、区間ｊ＋ｃ−１と区間ｊとの時間差がδ以下であるという条件である。
【０１３２】
第１の緩和条件を満たさない場合には、第２確率分布生成部１０７は、第２の緩和条件を満たす最大の正の整数ｃを特定する（ステップＳ２１９）。第２の緩和条件は、第１の緩和条件の後半部分であるｌj+c−ｌj+1≦δである。そして処理はステップＳ２２１に移行する。
【０１３３】
そして、第２確率分布生成部１０７は、各ｉ＝１，２，...，ｋについて、確率分布λiにおいて実行時間がｌj+c未満である確率λi［ｔ＜ｌj+c］を計算し、これらのｋ個の確率の中で最小のものをｑ'に設定する（ステップＳ２２１）。
【０１３４】
そして、第２確率分布生成部１０７は、ｑ'を近似最遅分布μの区間［lj，ｌj+1）の確率として設定する（ステップＳ２２３）。
【０１３５】
その後、第２確率分布生成部１０７は、各確率分布λiについて、ｑ'についての部分分布算出処理を実行する（ステップＳ２２５）。すなわち、λiからｑ'だけを取り除いた部分分布を、新たなλiに設定する処理を実行する。部分分布算出処理は、図６で示した処理である。なお、部分分布算出処理の後、処理は端子Ｄを介して図１８のステップＳ２０３に戻る。
【０１３６】
以上のような処理を実行するようにすれば、最遅分布に近似した近似最遅分布を、最遅分布よりも高速に生成することができるようになる。
【０１３７】
［実施の形態３］
なお、最遅分布でも近似最遅分布でもない他の目標確率分布を生成するようにしてもよい。本実施の形態では、不定区間ベース目標分布（indefinite-interval-based target distribution）と呼ぶ目標確率分布を生成する例を示す。不定区間ベース目標分布を採用すれば、遅延時間は長くなるが、処理の高速化が図られる。
【０１３８】
本実施の形態では、ｍ個の実数０＜ｑ1＜ｑ2＜．．．＜ｑm＝１を選択する。典型的には、ｑu＝ｕ／ｍ（ｕは１以上ｍ以下）とする。
【０１３９】
そして、本実施の形態では、各ｕと各ｉ＝１，２，...，ｋに対して、λiのｑu分位点（すなわち、分布をｑu：（１−ｑu）に分割する値）Ｑqu,1．．．Ｑqu,kを計算し、その中で最大のＱqu,iを不定区間ベース目標分布μのｑu分位点に採用する。
【０１４０】
このような不定区間ベース目標分布μを生成するための処理フローを、図２０を用いて説明する。
【０１４１】
第２確率分布生成部１０７は、初期化としてｑ0＝０を設定する（図２０：ステップＳ３０１）。その後、第２確率分布生成部１０７は、ｌ0に、全てのλiの０分位点の中で最大の値を設定する（ステップＳ３０２）。また、第２確率分布生成部１０７は、分位点についてのパラメータｕに１を設定する（ステップＳ３０３）。さらに、第２確率分布生成部１０７は、確率分布についてのパラメータｉに１を設定する（ステップＳ３０５）。
【０１４２】
そして、第２確率分布生成部１０７は、分布λiのｑu分位点Ｑqu,iを算出する（ステップＳ３０７）。その後、第２確率分布生成部１０７は、ｉがｋ以上であるか否かを判断する（ステップＳ３０９）。ｉがｋ未満であれば、第２確率分布生成部１０７は、ｉを１インクリメントして（ステップＳ３１１）、処理はステップＳ３０７に戻る。
【０１４３】
一方、ｉがｋ以上である場合には、第２確率分布生成部１０７は、ｌuに、全てのλiのｑu分位点Ｑqu,iのうち最大の値を設定する（ステップＳ３１３）。さらに、第２確率分布生成部１０７は、μ［ｌu-1，ｌu］に、ｑu−ｑu-1を設定する（ステップＳ３１５）。
【０１４４】
そして、第２確率分布生成部１０７は、ｕがｍ以上となったか否かを判断する（ステップＳ３１７）。ｕがｍ未満であれば、第２確率分布生成部１０７は、ｕを１インクリメントする（ステップＳ３１９）。そして処理はステップＳ３０５に戻る。
【０１４５】
一方、ｕがｍ以上となると、不定区間ベース目標分布μは生成完了となるが、各確率分布λiと不定区間ベース目標分布μとでは区間の定義が異なることがある。従って、例えば、第２確率分布生成部１０７は、各確率分布λiを、不定区間ベース目標分布μの区間に合わせるように変換する処理を実行する（ステップＳ３２１）。
【０１４６】
なお、分位点の計算において、線形補間ではなく切り上げを採用することにしているので、不定区間ベース目標分布における区間は、各確率分布λiについての区間と同じか、隣接する複数の区間を併合したものに等しくなる。
【０１４７】
よって、ステップＳ３２１では、具体的には、不定区間ベース目標分布μの各区間［ｌu，ｌu+1）に対して、以下のような形で各確率分布λiの区間［ｌu，ｌu+1）の確率λi［ｌu，ｌu+1］を算出する。
λi［ｌu，ｌu+1］＝Σ｛λi［ｌ，ｒ］｜［ｌ，ｒ）は、元のλiの区間であってｌu＜ｒ≦ｌu+1を満たすもの｝
【０１４８】
以上のような処理にて、不定区間ベース目標分布μを目標確率分布として生成できる。
【０１４９】
なお、最遅分布の場合、区間があらかじめ定義されているので、遅延の長さを予め見積もることができるが、不定区間ベース目標分布の場合には、各区間は、上でも述べたように確率分布λi及びｑu分位点に応じて異なり、区間サイズは不定区間ベース目標分布を生成する際に決まるので、遅延の長さを事前に見積もるのは難しい。場合によっては、区間が非常に大きくなることもあり、遅延は最遅分布の場合よりも長くなる場合がある。しかし、不定区間ベース目標分布の生成は、最遅分布の生成よりも高速に行うことができ、分位点の個数ｍに比例するため、計算時間を見積もることができる。
【０１５０】
なお、区間の個数ｍを増やしてゆくにつれ、不定区間ベース目標分布は、最遅分布に近づいてゆく。但し、ｍは１より大きい整数とする。
【０１５１】
［その他の変形例］
目標確率分布は、最も遅い区間の確率が１００％とならなければ、最も遅延時間が長いケースよりも遅延時間の短縮になるので、最も遅い区間以外の区間の確率が０以外の確率となっていればよい。但し、遅延時間を加えることを前提に秘密情報の各値についての確率分布λiから目標確率分布を生成するので、任意の目標確率分布が可能というわけではない。具体的には、各確率分布λiの最短実行時間のうち最大のものが属する区間より前の区間に、０を超える確率を有するような目標確率分布は採用できない。負の遅延時間を加えることはできないためである。
【０１５２】
このような条件を満たしていれば、どのような分布を目標確率分布に採用することもできる。
【０１５３】
図７に示したような確率分布λ0及びλ1の場合、最短実行時間のうち最大のものが属する区間は区間１で共通であるので、例えば最も遅い区間３以外の区間１及び２については、両者の最小の確率を採用して、残りの確率を最も遅い区間３に割り当てるようにしてもよい。
【０１５４】
すなわち、図２１に示すように、区間１では、λ0の０．２とλ1の０．３のうち小さい方の０．２を採用し、区間２では、λ0の０．５とλ1の０．２のうち小さい方の０．２を採用し、区間３に残余の０．６を割り当てるようにしてもよい。
【０１５５】
このようにすれば、当然図１６等で示したような最遅分布よりも平均遅延時間が長くなるが、それでも最も遅延が長いケースよりも平均遅延時間の短縮になり、目標確率分布の生成にかかる時間は短縮される。
【０１５６】
そのほか、全ての確率分布λiに共通してスパースになっている区間（一定の確率よりも小さい確率の区間）については、区間を併合するような処理を行ってもよい。これにより、設計段階で観測されていない希少事象における実行時間が、攻撃者による実行時間の確率分布の識別を助けてしまう可能性を小さくできる。
【０１５７】
本発明の実施の形態に係る方法では、区間の数は実験的に好ましい数を事前に決めることになる。区間の数が増えれば情報漏洩リスクが高まるが、区間の数を減らせば遅延時間は伸びることになるので、それらのトレードオフで区間の数を決定すべきである。
【０１５８】
以上、本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で述べた機能ブロック構成又はモジュール構成は一例であって、異なる構成を採用してもよい。具体的には、１つの機能ブロック又はモジュールを複数に分割したり、複数の機能ブロック又はモジュールを１つに統合したりしてもよい。
【０１５９】
また、処理フローについても、処理結果が変わらない限り、処理の順番を入れ替えたり、複数ステップを並列実行するようにしてもよい。
【０１６０】
なお、上で述べた情報処理装置１００は、コンピュータ装置であって、図２２に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。なお、ＨＤＤはソリッドステート・ドライブ（ＳＳＤ：Solid State Drive）などの記憶装置でもよい。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１６１】
なお、上で述べたような処理を実行することで用いられるデータは、処理途中のものであるか、処理結果であるかを問わず、メモリ２５０１又はＨＤＤ２５０５等の記憶装置に格納される。
【０１６２】
もし、適用フェーズでもプログラムで実装される場合には、当該プログラムを実行する情報処理装置は、図２２で示すようなコンピュータの場合もある。
【０１６３】
以上述べた実施の形態をまとめると以下のようになる。
【０１６４】
本実施の形態に係る第１の情報処理方法は、（Ａ）秘密情報の複数の値の各々について、当該秘密情報の値について行われた処理の実行時間の確率分布のデータを格納する第１のデータ格納部に格納されたデータに基づき、実行時間に遅延時間を加える場合における複数の時間区間の各々の確率を定義し且つ秘密情報の複数の値について共通である第２の確率分布を生成するステップと、（Ｂ）秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布と第２の確率分布とに基づき、当該秘密情報の値についての実行時間の確率分布を第２の確率分布に変換するためのデータを生成し、第２のデータ格納部に格納するステップとを含む。
【０１６５】
タイミング攻撃に対抗するために、秘密情報の値にかかわらず共通の第２の確率分布に従う処理時間（＝実行時間＋遅延時間）で秘密情報に対する処理結果が出力されることが好ましい。このように、秘密情報の各値について、当該秘密情報の値についての実行時間の確率分布を第２の確率分布に変換するためのデータが用意されれば、実際の実行時間が得られた時点において、容易に、外から見ると第２の確率分布に従う実行時間で処理結果を出力できるようになる。
【０１６６】
なお、上で述べた第２の確率分布は  当該第２の確率分布において最も遅い時間区間以外のいずれかの時間区間に０を超える確率が設定されている確率分布である場合もある。遅延時間を少しでも短くする場合には、このような特性を有する第２の確率分布が好ましい。なお、実行時間を短くすること（すなわち負の遅延時間を加えること）はできないので、その点でも制限はある。
【０１６７】
また、上で述べた第２の確率分布は、０から１までのいかなる実数ｑに対しても、秘密情報の複数の値の各々に係る実行時間の確率分布をｑ対（１−ｑ）に分割するｑ−分位数のうち最も大きなものと同一の値のｑ−分位数を持つ確率分布又は当該確率分布に近似する確率分布である場合もある。例えば、平均遅延時間及び最悪遅延時間を最短化するためには、上記のような第２の確率分布を採用することが好ましい。なお、秘密情報の各値についての確率分布についても時間区間で分割して離散化しておいてもよいが、離散化によって分位数が近似になる場合もある。また、計算時間のため近似の確率分布を採用する場合もある。
【０１６８】
さらに、０から１までの複数の実数が予め設定されている場合において、上で述べた第２の確率分布は、上記複数の実数のうちいかなる実数ｑに対しても、秘密情報の複数の値の各々に係る実行時間の確率分布をｑ対（１−ｑ）に分割するｑ−分位数のうち最も大きなものと同一の値のｑ−分位数を持つ確率分布又は当該確率分布に近似する確率分布である場合もある。高速に第２の確率分布を生成することができる。この場合、第２の確率分布の時間区間は、複数の実数のうち隣り合う２つの実数についての分位数に基づき設定される。
【０１６９】
また、上で述べた変換するためのデータが、時間区間内で遅延時間を加える確率と他の各時間区間に至るまで遅延時間を加える確率とを含むようにしてもよい。このように、他の時間区間に至るまで遅延時間を加えることで、実際の実行時間が得られた場合に共通の第２の確率分布を実現できるようになる。
【０１７０】
なお、上記情報処理方法は、上記変換するためのデータと、当該変換するためのデータに基づき実際の実行時間についての遅延時間を決定するプログラム又はハードウエアモジュールのデータとを合わせて出力するステップをさらに含むようにしてもよい。出力されたデータを基に暗号処理装置などを実装すれば、タイミング攻撃に対する耐タンパー性の高い装置が得られる。
【０１７１】
また、上記情報処理方法は、上記変換するためのデータと、当該変換するためのデータに基づき実際の実行時間についての遅延時間を決定するプログラムと、上記処理のためのプログラムとを含む、プロセッサで実行可能なプログラムを生成するステップをさらに含むようにしてもよい。このようにすれば、タイミング攻撃に対する耐タンパー性の高いプログラムが自動的に生成される。
【０１７２】
本実施の形態に係る第２の情報処理方法は、（Ａ）秘密情報の複数の値のうちのある値と、当該ある値について行われた処理の実行時間とを取得するステップと、（Ｂ）秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の確率分布を、秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第２の確率分布へ変換するためのデータを格納するデータ格納部における、上記ある値についてのデータに基づき、上記ある値について行われた処理の実行時間についての遅延時間を決定するステップとを含む。
【０１７３】
このようにすれば、秘密情報のどのような値についても、外部から見た処理時間が第２の確率分布に従うように、実行時間に対する遅延時間を決定でき、タイミング攻撃に対抗できるようになる。
【０１７４】
なお、上で述べたデータは、確率分布について予め定義されている複数の時間区間のうち各時間区間内で遅延時間を加える確率と他の各時間区間に至るまで遅延時間を加える確率とを含むようにしてもよい。このようにすれば、容易に時間区間内で遅延を加えるのか、他の時間区間に至るまで遅延を加えるのかを決定できるようになる。
【０１７５】
さらに、第２の情報処理方法は、上記ある値について行われた処理の実行時間と決定された遅延時間とから決まる出力時刻に、上記ある値について行われた処理の結果を出力するステップをさらに含むようにしてもよい。例えば、該当する時間区間の終期で出力する。
【０１７６】
なお、上で述べた第２の確率分布は、当該第２の確率分布において定義される複数の時間区間のうち最も遅い時間区間以外のいずれかの時間区間に０を超える確率が設定されている確率分布である場合もある。
【０１７７】
また、第２の情報処理方法は、（Ｃ）秘密情報の複数の値の各々について、取得された、当該秘密情報の値について行われた処理の実行時間を格納する第２のデータ格納部に格納されたデータに基づき、秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の第３の確率分布を生成するステップと、（Ｄ）秘密情報の複数の値の各々についての第３の確率分布に基づき、秘密情報の複数の値について共通であって且つ実行時間に遅延時間を加える場合における第４の確率分布を生成するステップと、（Ｅ）秘密情報の複数の値の各々について、当該秘密情報の値についての実行時間の第３の確率分布と第４の確率分布とに基づき、当該秘密情報の値についての実行時間の第３の確率分布を第４の確率分布に変換するためのデータを生成し、データ格納部に格納するステップとをさらに含むようにしてもよい。
【０１７８】
このように、実際の実行時間に基づき、上記変換するためのデータを更新することで、実際の実行環境に合わせたタイミング攻撃に対抗できるようになる。
【０１７９】
以上述べた情報処理方法をコンピュータに実行させるためのプログラムを作成することができて、そのプログラムは、様々な記憶媒体に記憶される。
【０１８０】
また、上で述べたような情報処理方法を実行する情報処理装置は、１台のコンピュータで実現される場合もあれば、複数台のコンピュータで実現される場合もあり、それらを合わせて情報処理システム又は単にシステムと呼ぶものとする。
【符号の説明】
【０１８１】
１００  情報処理装置
１０１  入力データ格納部    １０３  第１確率分布生成部
１０５  第１確率分布格納部  １０７  第２確率分布生成部
１０９  第２確率分布格納部  １１１  テーブル生成部
１１３  テーブル格納部      １１５  モジュール格納部
１１６  出力処理部          １１７  出力データ格納部
２００  プログラム／ハードウエア
２１０  本来の機能モジュール    ２２０  出力遅延モジュール
２２１  テーブル
２３０  テーブル更新モジュール  ２３１  実行時間ＤＢ
【図１】
2020031263.tif 000003
【図２】
2020031263.tif 000004
【図３】
2020031263.tif 000005
【図４】
2020031263.tif 000006
【図５】
2020031263.tif 000007
【図６】
2020031263.tif 000008
【図７】
2020031263.tif 000009
【図８】
2020031263.tif 000010
【図９】
2020031263.tif 000011
【図１０】
2020031263.tif 000012
【図１１】
2020031263.tif 000013
【図１２】
2020031263.tif 000014
【図１３】
2020031263.tif 000015
【図１４】
2020031263.tif 000016
【図１５】
2020031263.tif 000017
【図１６】
2020031263.tif 000018
【図１７】
2020031263.tif 000019
【図１８】
2020031263.tif 000020
【図１９】
2020031263.tif 000021
【図２０】
2020031263.tif 000022
【図２１】
2020031263.tif 000023
【図２２】
2020031263.tif 000024