(57)【特許請求の範囲】
【請求項１】
プログラムの変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝に対する変更を隠蔽するシステムであって、
前記変数ｖ１，ｖ２，．．．，ｖｎのうちの変数ｖｉの値ｗｉであって、ｗは集合Ｗの要素である、値ｗｉを、表現ｒｉにより表現する値表現手段であって、
【数１】
0006303073.tif 000209
であり、ｒｉは、表現の集合
【数２】
0006303073.tif 000210
の要素であり、σｉは、集合Σの要素であって、ｗｉの前記表現ｒｉに冗長性を提供する状態変数であり、
【数３】
0006303073.tif 000211
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、値表現手段と、
ｉ＝１，２，．．．，ｎについて、更新された表現
【数４】
0006303073.tif 000212
を得るために、Ｖの部分集合Ｖ’内の変数の値に対するアクションを、Ｖ’に対するアクションと、
【数５】
0006303073.tif 000213
に対するアクションと、により表現するアクション表現手段であって、
【数６】
0006303073.tif 000214
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、アクション表現手段と、
を有し、
Ｖ’に対する前記アクションは、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更するよう構成され、
【数７】
0006303073.tif 000215
に対する前記アクションは、
【数８】
0006303073.tif 000216
内の各変数ｖｋの表現ｒｋを、状態変数σｋの変更された値σ’ｋに応じて変更するよう構成される、システム。
【請求項２】
前記部分集合Ｖ’内の前記変数の前記値に対する前記アクションは、条件が成立する場合の変数の集合Ｖ１に対するアクションと、前記条件が成立しない場合の変数の集合Ｖ２に対するアクションと、を定義しているｉｆ文を含み、前記変数の集合Ｖ１は、前記変数の集合Ｖの部分集合であり、前記変数の集合Ｖ２も、前記変数の集合Ｖの部分集合であり、前記アクション表現手段は、前記条件が成立する場合には、前記変数の集合Ｖ’として前記変数の集合Ｖ１を使用し、前記条件が成立しない場合には、前記変数の集合Ｖ’として前記変数の集合Ｖ２を使用するよう構成される、請求項１記載のシステム。
【請求項３】
前記変数の集合Ｖ１及び前記変数の集合Ｖ２は、前記変数の集合Ｖ１に対する前記アクション及び前記変数の集合Ｖ２に対する前記アクションの両方により影響が及ぼされる変数の積集合Ｖ３を有し、したがって、Ｖ３＝Ｖ１∩Ｖ２であり、前記アクションは、前記条件が成立する場合には、関数ｆｍに従って、前記条件が成立しない場合には、関数
【数９】
0006303073.tif 000217
に従って、集合Ｖ３の各変数ｖｍを変更し、前記アクション表現手段は、前記条件が成立するかどうかに基づいて、
ｗ’ｍ＝ｆｍ（ｗｍ）及び
【数１０】
0006303073.tif 000218
であるか、又は、
【数１１】
0006303073.tif 000219
及びσ’ｍ＝ｆｍ（ｈｍ（ｗｍ，σｍ））であるか、
のいずれかであるように、前記集合Ｖ３の各変数ｖｍの表現
【数１２】
0006303073.tif 000220
を決定するよう構成され、ｈｍは、Ｗ×ΣからＷへの写像である、請求項２記載のシステム。
【請求項４】
前記アクション表現手段は、前記表現ｒｉ及び条件に関する入力に対応する前記表現ｒ’ｉのルックアップを、前記表現ｒｉ及び前記条件に関する前記入力のタプルを、対応する前記表現ｒ’ｉにマッピングしている少なくとも１つのルックアップテーブルを使用して生じさせるよう構成される、請求項１記載のシステム。
【請求項５】
｜Σ｜＝｜Ｗ｜であり、前記アクション表現手段は、条件ｂを判定する１つ以上の入力変数を特定するよう構成され、
前記アクション表現手段は、
【数１３】
0006303073.tif 000221
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数１４】
0006303073.tif 000222
であるように、少なくとも１つの表現ｒであって、ｒは前記集合Ｖ内の変数ｖｉのｒｉに等しい、少なくとも１つの表現ｒと、前記１つ以上の入力変数と、に基づいて、隠蔽されたスワップ演算を実行する第１のスワップユニットであって、
【数１５】
0006303073.tif 000223
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数１６】
0006303073.tif 000224
は、
【数１７】
0006303073.tif 000225
とは異なり、ｒ’’は表現である、第１のスワップユニット、及び／又は
【数１８】
0006303073.tif 000226
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数１９】
0006303073.tif 000227
であるように、表現ｒ’’’と、前記の１つ以上の変数と、に基づいて、隠蔽されたスワップ演算を実行する第２のスワップユニットであって、
【数２０】
0006303073.tif 000228
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数２１】
0006303073.tif 000229
は、
【数２２】
0006303073.tif 000230
とは異なり、ｒ’は、前記更新された表現ｒ’ｉである、第２のスワップユニット
を有する、請求項１記載のシステム。
【請求項６】
前記アクション表現手段は、
【数２３】
0006303073.tif 000231
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数２４】
0006303073.tif 000232
であるように、前記表現ｒ’’に基づいて表現ｒ’’’を得るための関数を計算する関数評価ユニットを有し、ｆは、Ｗ上で定義された写像であり、ｇは、Ｗ上で定義された写像である、請求項５記載のシステム。
【請求項７】
【数２５】
0006303073.tif 000233
及び
【数２６】
0006303073.tif 000234
である、請求項５又は６記載のシステム。
【請求項８】
ｗ及びσの全ての値、並びに、｛１，２，３，．．．，ｎ｝内のｍの少なくとも１つの値について、ｈｍ（ｗ，σ）＝σである、請求項３記載のシステム。
【請求項９】
Ｖ’に対する前記アクションは、ｗ’ｊ＝ｆｊ（ｗｊ）及びσ’ｊ＝σｊであるように、前記変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを変更するよう構成され、
【数２７】
0006303073.tif 000235
に対する前記アクションは、ｗ’ｋ＝ｗｋ及びσ’ｋ＝ｆｋ（ｈｋ（ｗｋ，σｋ））であるように、
【数２８】
0006303073.tif 000236
内の各変数ｖｋの表現ｒｋを変更するよう構成され、
ｉ＝１，２，．．．，ｎについて、ｆｉは、Ｗ上で定義された関数であり、
【数２９】
0006303073.tif 000237
内の各変数ｖｋについて、ｈｋは、Ｗ×Σの要素をＷへ写像する関数である、請求項１記載のシステム。
【請求項１０】
第１の複数のネストされた条件を伴うネストされた条件付き演算を、第２の複数の条件を伴う機能的に等価な一連のネストされていない条件付き演算により表現する変換ユニットをさらに有する、請求項２又は３記載のシステム。
【請求項１１】
前記変換ユニットは、
前記ネストされた条件付き演算のそれぞれの条件分岐のそれぞれの式であって、前記それぞれの式は、特定の変数に割り当てられる代替値に関連付けられる、それぞれの式を、補助式の項に組み合わせ、
上記のステップを繰り返して、項が異なる様式で組み合わされる複数の補助式が生成されるように、それぞれの条件分岐のそれぞれの式を、補助式の項に組み合わせ、
前記補助式を評価し、それらの結果を記憶するためのコードを生成し、
組み合わされた条件であって、前記組み合わされた条件は、前記条件の観点から関連しない分岐に対応する項が相殺するような、前記複数の条件の組合せである、組み合わされた条件に応じて、前記補助式の前記結果を組み合わせるためのコードを生成する
よう構成される、請求項１０記載のシステム。
【請求項１２】
前記アクション表現手段は、前記一連のネストされていない条件付き演算のうちの少なくとも１つの条件付き演算と、前記第２の複数の条件のうちの対応する条件と、を特定するよう構成され、前記アクション表現手段は、前記の特定された条件付き演算をアクションとして、前記の特定された対応する条件を前記ｉｆ文の条件として、使用するよう構成される、請求項１０記載のシステム。
【請求項１３】
プログラムの変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝に対する変更を隠蔽する方法であって、
プロセッサが、前記変数ｖ１，ｖ２，．．．，ｖｎのうちの変数ｖｉの値ｗｉであって、ｗは集合Ｗの要素である、値ｗｉを、表現ｒｉにより表現するステップであって、
【数３０】
0006303073.tif 000238
であり、ｒｉは、表現の集合
【数３１】
0006303073.tif 000239
の要素であり、σｉは、集合Σの要素であって、ｗｉの前記表現ｒｉに冗長性を提供する状態変数であり、
【数３２】
0006303073.tif 000240
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
前記プロセッサが、ｉ＝１，２，．．．，ｎについて、更新された表現
【数３３】
0006303073.tif 000241
を得るために、Ｖの部分集合Ｖ’の値に対するアクションを、Ｖ’に対するアクションと、
【数３４】
0006303073.tif 000242
に対するアクションと、により表現するステップであって、
【数３５】
0006303073.tif 000243
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
を含み、
Ｖ’に対する前記アクションは、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更するよう構成され、
【数３６】
0006303073.tif 000244
に対する前記アクションは、
【数３７】
0006303073.tif 000245
内の各変数ｖｋの表現ｒｋを、σｋの変更された値σ’ｋに応じて変更するよう構成される、方法。
【請求項１４】
プロセッサに請求項１３記載の方法を実行させる命令を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム実行の詳細の隠蔽に関する。より詳細には、本発明は、条件付き演算の隠蔽に関する。より詳細には、本発明は、条件付き演算を含むプログラムにおけるプログラムフロー及びデータフローの隠蔽に関する。
【背景技術】
【０００２】
演算子の機能を明らかにする該演算子を使用するのではなく暗号化された値を使用する演算は、テーブル駆動手法を用いて実現され得る。プログラムコード、すなわち、その演算は、ルックアップテーブルを使用することにより、隠蔽され得る。これらのテーブルを暗号化されたデータに適用することは、隠蔽された演算の結果である暗号化された結果を与える。しかしながら、比較（＜、＝、．．．）のような演算子を認識することは、これらの命令が、数の点で制限され、通常は、制御フローの変化をもたらす結果となり、それらの結果が、暗号化されたブーリアン型であるので、かなり容易である。この暗号化されたブーリアンが、例えばｉｆ−ｔｈｅｎ構造又はｉｆ−ｔｈｅｎ−ｅｌｓｅ構造の場合において、条件付き演算を保護する場合、攻撃者は、演算の制御フローから演算の側面を認識できるであろう。さらに、攻撃者は、比較された暗号化された値に関する順序を生成できるであろう。最終的に、これは、暗号化を破ることにつながるおそれがある。
【０００３】
ソフトウェアプログラムにおいて、比較を実行することがしばしば必要である。例えば、所定の閾値に達したかどうか又は何らかの入力が予め定められた値に等しいかどうかをチェックするために、比較が実行される。難読化プログラムにおいて、このような比較は、攻撃者がこの符号化を破るのを助けることがある。
【０００４】
特許文献１は、暗号化関数を有するソフトウェアにより使用されるキーの暗号化セキュリティを高めることに関する方法及びシステムを開示している。これは、ソフトウェアの数学的複雑さを増大させることにより、行われる。ソフトウェアにより使用されるコンポーネント及び関数が、最初に決定され、これらのコンポーネントと関数とこれらの間で交換されるデータとを使用して、ソフトウェアは、解析に対する耐性が高められる。解析耐性を高める際に使用されるこれらの方法は、３つの一般タイプにグループ化される。すなわち、コンポーネント間で交換される情報を調整するタイプと、いくつかのコンポーネントを、異なるが関連するコンポーネントで置換するタイプと、コンポーネント間のデータフローを調整するタイプと、である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第７８０９１３５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
プログラムの実行中にプログラムから情報が漏洩するのを防止する改善された方法及びシステムを有することは、有利であろう。
【課題を解決するための手段】
【０００７】
この問題に対処するために、第１の態様において、プログラムの変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝に対する変更を隠蔽するシステムが提供される。本システムは、
変数ｖ１，ｖ２，．．．，ｖｎのうちの変数ｖｉの値ｗｉであって、ｗｉは集合Ｗの要素である、値ｗｉを、表現ｒｉにより表現する値表現手段であって、
【数１】
0006303073.tif 000002
であり、ｒｉは、表現の集合
【数２】
0006303073.tif 000003
の要素であり、σｉは、集合Σの要素であって、ｗｉの表現ｒｉに冗長性を提供する状態変数であり、
【数３】
0006303073.tif 000004
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、値表現手段と、
Ｖの部分集合Ｖ’の値に対するアクションを、Ｖ’に対するアクションと、
【数４】
0006303073.tif 000005
に対するアクションと、により表現するアクション表現手段と、
を有し、
Ｖ’に対するアクションは、
【数５】
0006303073.tif 000006
であるように、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更し、
【数６】
0006303073.tif 000007
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数７】
0006303073.tif 000008
に対するアクションは、
【数８】
0006303073.tif 000009
であるように、
【数９】
0006303073.tif 000010
内の各変数ｖｋの表現ｒｋを、σｋの変更された値σ’ｋに応じて変更する。
【０００８】
本システムを使用すると、これらの変数のうちどの変数がプログラム内で実際に変更されたかを攻撃者が発見することが難しくなる。なぜならば、変化していない変数の表現も、状態変数σを変更することにより、変更されるからである。
【０００９】
例えば、アクションは、条件が成立する場合の変数の集合Ｖ１に対するアクションと、条件が成立しない場合の変数の集合Ｖ２に対するアクションと、を定義しているｉｆ文を含み、変数の集合Ｖは、Ｖ１及びＶ２の和集合（合併）であり、したがって、Ｖ＝Ｖ１∪Ｖ２であり、アクション表現手段は、条件が成立するかどうかに応じて、変数の集合Ｖ’として変数の集合Ｖ１又は変数の集合Ｖ２を使用するよう構成される。これは、条件と、条件付きコードセグメントのどの分岐が選択されたかと、に関する情報の漏洩を防ぐのに役立つ。アクション表現手段は、上述したように、Ｖ’に対するアクションと、
【数１０】
0006303073.tif 000011
に対するアクションと、により、部分集合Ｖ’に対するアクションを表現したときの選択された集合Ｖ’を使用することができる。
【００１０】
変数の集合Ｖ１及び変数の集合Ｖ２は、これらのアクションの両方により影響が及ぼされる変数の積集合（共通部分）Ｖ３を有することができ、したがって、Ｖ３＝Ｖ１∩Ｖ２であり、アクションは、条件が成立する場合には、関数ｆに従って、条件が成立しない場合には、関数
【数１１】
0006303073.tif 000012
に従って、集合Ｖ３の各変数ｖｍを変更し、アクション表現手段は、入力に応じて条件が成立するかどうかに基づいて、
ｗ’ｍ＝ｆｍ（ｗｍ）及び
【数１２】
0006303073.tif 000013
であるか、又は、
【数１３】
0006303073.tif 000014
及びσ’ｋ＝ｆｍ（ｈｍ（ｗｍ，σｍ））であるか、
のいずれかであるように、集合Ｖ３の各変数ｖｍの表現
【数１４】
0006303073.tif 000015
を決定するよう構成され、ｈｍは、Ｗ×ΣからＷへの写像である。
【００１１】
この特徴を使用すると、ｆｍが変数ｗｍに実際に適用されたか又は
【数１５】
0006303073.tif 000016
が変数ｗｍに適用されたかを攻撃者が発見することが難しくなる。
【００１２】
アクション表現手段は、表現ｒｉ及び条件に関する入力に対応する表現ｒ’ｉのルックアップを、表現ｒｉ及び条件に関する入力のタプルを、対応する表現ｒ’ｉにマッピングしている少なくとも１つのルックアップテーブルを使用して生じさせるよう構成され得る。入力は、例えば、（任意的に暗号化される）ブーリアン変数を含み得る。代替的に、入力は、条件を定義する述語において現れる変数を含んでもよい。この述語及び実際のアクションは、少なくとも１つのルックアップテーブルにおいて隠蔽され得る。
【００１３】
特定の例において、｜Σ｜＝｜Ｗ｜であり、アクション表現手段（１０３）は、条件ｂを判定する１つ以上の入力変数を特定するよう構成され、
アクション表現手段（１０３）は、
【数１６】
0006303073.tif 000017
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数１７】
0006303073.tif 000018
であるように、少なくとも１つの表現ｒであって、ｒは集合Ｖ内の変数ｖｉのｒｉに等しい、少なくとも１つの表現ｒと、１つ以上の入力変数と、に基づいて、隠蔽されたスワップ演算を実行するスワップユニット（３０５）であって、
【数１８】
0006303073.tif 000019
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数１９】
0006303073.tif 000020
は、
【数２０】
0006303073.tif 000021
とは異なり、ｒ’’は表現である、スワップユニット（３０５）、及び／又は
【数２１】
0006303073.tif 000022
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数２２】
0006303073.tif 000023
であるように、表現ｒ’’’と、１つ以上の入力変数と、に基づいて、隠蔽されたスワップ演算を実行するスワップユニット（３０６）であって、
【数２３】
0006303073.tif 000024
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数２４】
0006303073.tif 000025
は、
【数２５】
0006303073.tif 000026
とは異なり、ｒ’は、更新された表現ｒ’ｉである、スワップユニット（３０６）
を有する。
【００１４】
これらのスワップ演算はそれぞれ、表現ｒ’を計算するときの前処理ステップ及び／又は後処理ステップとして使用され得、したがって、実際の関数ｆ及び／又は関数ｇの隠蔽された実装を単純化することができる。これらのスワップユニットのうちの１つのスワップユニットのみが使用される場合、アクション前後のｗ及びσの役割が入れ替えられ得る。これは、本システムの残りの部分においてこれを考慮することにより、例えば、符号化
【数２６】
0006303073.tif 000027
が変化したことを想定している適切なプログラムコードによって処理され得る。
【００１５】
アクション表現手段は、
【数２７】
0006303073.tif 000028
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数２８】
0006303073.tif 000029
であるように、表現ｒ’’に基づいて表現ｒ’’’を得るための関数を計算する関数評価ユニットをさらに有することができ、ｆは、Ｗ上で定義された写像であり、ｇは、Ｗ上で定義された写像である。
【００１６】
このように、関数ｆ及び関数ｇは、前に実行されたスワップ演算に応じて、表現ｒ’’のｗ側又はσ側に適用され得、したがって、条件が成立するかどうかにかかわらず、ｆ及びｇの隠蔽された実装は同じにすることができる。後に実行され得るスワップ演算は、条件に応じて、最初のスワップ演算により実行されたスワップ演算を元に戻すために、ｗ側とσ側とを再度交換する。
【００１７】
特定の例において、
【数２９】
0006303073.tif 000030
である。これは、これら２つのスワップ演算が、同一の暗号符号化を用いることを意味する。したがって、同じ符号及び／又はテーブルが、両方のスワップ演算に再使用され得る。
【００１８】
一例において、ｗ及びσの全ての値、並びに、｛１，２，３，．．．，ｎ｝内の少なくとも１つのｍについて、ｈｍ（ｗ，σ）＝σである。これは、単純化された且つ／又はより対称的な実装を提供することができる。
【００１９】
一例において、Ｖ’に対するアクションは、ｗ’ｊ＝ｆｊ（ｗｊ）及びσ’ｊ＝σｊであるように、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを変更するよう構成され、
【数３０】
0006303073.tif 000031
に対するアクションは、ｗ’ｋ＝ｗｋ及びσ’ｋ＝ｆｋ（ｈｋ（ｗｋ，σｋ））であるように、
【数３１】
0006303073.tif 000032
内の各変数ｖｋの表現ｒｋを変更するよう構成され、
ｉ＝１，２，．．．，ｎについて、ｆｉは、Ｗ上で定義された関数であり、
【数３２】
0006303073.tif 000033
内の各変数ｖｋについて、ｈｋは、Ｗ×Σの要素をＷへ写像する関数である。
【００２０】
これは、表現に対してどのような変更を行うかの一例である。
【００２１】
請求項２又は３記載のシステムは、第１の複数のネストされた条件を伴うネストされた条件付き演算を、第２の複数の条件を伴う機能的に等価な一連のネストされていない条件付き演算に表現する、ネストされた条件表現手段をさらに有する。
【００２２】
本システムは、第１の複数のネストされた条件を伴うネストされた条件付き演算を、第２の複数の条件を伴う機能的に等価な一連のネストされていない条件付き演算に変換する変換ユニットをさらに有することができる。これは、情報漏洩の防止を向上させるのに役立つ。なぜならば、ネストされていない条件付き演算の各々が、例えば、第１の生成ユニット及び第２の生成ユニットにより生成されたコードにより評価され、したがって、条件付き演算において現れる全ての式が、評価され、表現ｒ’に影響を及ぼし得るからである。より少ない分岐はスキップされる。
【００２３】
例えば、変換ユニットは、ネストされた条件付き演算のそれぞれの条件分岐のそれぞれの式であって、それぞれの式は、特定の変数に割り当てられる代替値に関連付けられる、それぞれの式を、補助式の項に組み合わせ、このステップを繰り返して、項が異なる様式で組み合わされる複数の補助式が生成されるように、それぞれの条件分岐のそれぞれの式を、補助式の項に組み合わせ、補助式を評価し、それらの結果を記憶するためのコードを生成し、組み合わされた条件であって、組み合わされた条件は、条件の観点から関連しない分岐に対応する項が相殺するような、複数の条件の組合せである、組み合わされた条件に応じて、補助式の結果を組み合わせるためのコードを生成するよう構成され得る。このようなシステムを使用して、ネストされたｉｆ文を、ネストされていない一連のｉｆ文にフラット化することにより、ネストされたｉｆ文を隠蔽することができる。異なる条件分岐において現れる式を組み合わせ、次いで、条件の観点から関連しない式が相殺するように補助式を組み合わせることにより、これらの式の多くが、プログラムにおいて評価され、暗号化された結果に影響を及ぼし得、暗号化された結果に対応する復号化された値ｗ’にどの式が実際に影響を及ぼすかを解析することが難しくなる。
【００２４】
アクション表現手段は、一連のネストされていない条件付き演算のうちの少なくとも１つの条件付き演算と、第２の複数の条件のうちの対応する条件と、を特定するよう構成され得、アクション表現手段は、特定された条件付き演算をアクションとして、特定された対応する条件をｉｆ文の条件として、使用するよう構成される。このような組合せは、特に、条件付きコード片において何が生じるかの良好な隠蔽を提供する。さらに、特定ユニットは、一連のネストされていない条件付き演算の各条件付き演算と、第２の複数の条件の各対応する条件と、を特定するよう構成され得、第１の生成ユニット及び第２の生成ユニットは、各特定された条件付き演算及び各対応する条件を処理するよう構成される。
【００２５】
別の態様において、プログラムの変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝に対する変更を隠蔽する方法が提供される。本方法は、
変数ｖ１，ｖ２，．．．，ｖｎのうちの変数ｖｉの値ｗｉであって、ｗは集合Ｗの要素である、値ｗｉを、表現ｒｉにより表現するステップであって、
【数３３】
0006303073.tif 000034
であり、ｒｉは、表現の集合
【数３４】
0006303073.tif 000035
の要素であり、σｉは、集合Σの要素であって、ｗｉの表現ｒｉに冗長性を提供する状態変数であり、
【数３５】
0006303073.tif 000036
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
ｉ＝１，２，．．．，ｎについて、更新された表現
【数３６】
0006303073.tif 000037
を得るために、Ｖの部分集合Ｖ’の値に対するアクションを、Ｖ’に対するアクションと、
【数３７】
0006303073.tif 000038
に対するアクションと、により表現するステップであって、
【数３８】
0006303073.tif 000039
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
を含み、
Ｖ’に対するアクションは、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更するよう構成され、
【数３９】
0006303073.tif 000040
に対するアクションは、
【数４０】
0006303073.tif 000041
内の各変数ｖｋの表現ｒｋを、σｋの変更された値σ’ｋに応じて変更するよう構成される。
【００２６】
別の態様に従うと、条件付き演算を隠蔽するシステムが提供される。本システムは、
値ｗであって、ｗは集合Ｗの要素である、値ｗを、表現ｒにより表現する表現ユニットであって、
【数４１】
0006303073.tif 000042
であり、ｒは、表現の集合
【数４２】
0006303073.tif 000043
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数４３】
0006303073.tif 000044
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、表現ユニットと、
条件に関する入力に基づいて、表現ｒから、値ｗ’の表現ｒ’を導出する導出ユニットであって、ｗ’は集合Ｗの要素であり、ｒ’は、表現の集合
【数４４】
0006303073.tif 000045
の要素であり、
【数４５】
0006303073.tif 000046
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数４６】
0006303073.tif 000047
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、入力に応じて条件が成立するかどうかに基づいて、ｗ’がｆ（ｗ）に関連付けられるか、又は、σ’がｆ（ｈ（ｗ，σ））に関連付けられるか、のいずれかであり、ｆは、Ｗ上で定義された非自明写像であり、ｈは、Ｗ×ΣからＷへの写像である、導出ユニットと、
を有する。
【００２７】
表現ユニットは、値ｗの冗長表現である表現ｒを提供する。すなわち、ｗのいかなる単一の値も、多くの異なる表現ｒを有することができる。なぜならば、ｒは、Ω（ｗ）の任意の要素とすることができるからである。これは、ｒの変更が、必ずしもｗの変更を意味するとは限らないことを意味する。なぜならば、ｒは、同じ値のｗについて、Ω（ｗ）の異なる要素に単に変更されることがあるからである。このような表現は、条件付き演算、例えば、条件ｂが成立する場合にはｗをｗ’＝ｆ（ｗ）に更新すること、が隠蔽されることを可能にする。すなわち、条件が実際に成立する場合には、表現ｒは、ｆ（ｗ）の表現、すなわち、集合Ω’（ｆ（ｗ））のメンバーである表現ｒ’になるように更新される。一方、条件が成立しない場合には、表現ｒは、やはり更新されるが、同じ値ｗの異なる表現、すなわち、集合Ω’（ｗ）の（異なる）メンバーに更新される。後者の場合、関数ｆは、集合Ω’（ｗ）の特定のメンバーを選択するために使用されるので、ｆに基づく同じ関数が、条件が成立するか否かにかからわず、表現ｒに対して実行及び適用される演算に影響を及ぼす。したがって、関数ｆにより提供される任意のエントロピー効果は、条件が成立するかどうかにかかわらず、表現ｗ’において広げられる。すなわち、攻撃者が、値ｒ又は条件ｂを変更し、結果ｒ’に対するその何らかの影響を見るときでさえも、プログラム及びその変数に関する情報を抽出することがやはり難しくなる。さらに、関数ｆが値ｗに適用されたか否かを悪意のある観察者が発見することも難しくなる。
【００２８】
決定ユニットは、入力に応じて条件が成立するかどうかに基づいて、ｗ’がｆ（ｗ）に関連付けられるとともにσ’が
【数４７】
0006303073.tif 000048
に関連付けられるか、又は、ｗ’が
【数４８】
0006303073.tif 000049
に関連付けられるとともにσ’がｆ（ｈ（ｗ，σ））に関連付けられるか、のいずれかであるように、表現
【数４９】
0006303073.tif 000050
を決定するよう構成され得、ｇは、Ｗ上で定義された（非自明）写像である。これは、例えば、ｅｌｓｅ部を有するｉｆ文（例えば、if  b  then  w=f(w)  else  w=g(w)）の隠蔽された実装を作成するのに特に有用である。関数ｆ及び関数ｇの両方が、最終結果ｒ’に影響を及ぼすが、これらの関数のうちの一方の関数のみが、ｗ部分、すなわち、表現ｒ’の選択元の集合Ω’に影響を及ぼす。他方の関数は、Ω’のどの要素が選択されるかに影響を及ぼすに過ぎない。したがって、（条件ｂにより決定される、）関数ｆ及び関数ｇのうちの一方の関数のみが、表現ｒ’の基礎となる復号化された値ｗ’を決定する。
【００２９】
導出ユニットは、表現ｒ及び条件に関する入力に対応する表現ｒ’を、表現ｒ及び入力のタプルを対応する表現ｒ’にマッピングしている少なくとも１つのルックアップテーブルを使用して、ルックアップするよう構成され得る。ルックアップテーブルによる実装は、入力変数及び関数ｆから条件を計算することに伴う何らかの情報の漏洩を防止することを可能にする。さらに、条件に依存するｉｆ文又はジャンプ命令を回避することができる。
【００３０】
例えば、｜Σ｜＝｜Ｗ｜である。導出ユニットは、条件ｂを判定する１つ以上の変数を特定するよう構成され得、
導出ユニットは、
【数５０】
0006303073.tif 000051
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数５１】
0006303073.tif 000052
であるように、表現ｒと、１つ以上の変数と、に基づいて、隠蔽されたスワップ演算を実行し、ここで、
【数５２】
0006303073.tif 000053
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数５３】
0006303073.tif 000054
は、
【数５４】
0006303073.tif 000055
とは異なり、ｒ’’は表現であり、且つ／又は
【数５５】
0006303073.tif 000056
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数５６】
0006303073.tif 000057
であるように、表現ｒ’’’と、１つ以上の変数と、に基づいて、隠蔽されたスワップ演算を実行し、ここで、
【数５７】
0006303073.tif 000058
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、
【数５８】
0006303073.tif 000059
は、
【数５９】
0006303073.tif 000060
とは異なる、スワップユニット
を有することができる。
【００３１】
これらのスワップ演算はそれぞれ、表現ｒ’を計算するときの前処理ステップ及び／又は後処理ステップとして使用され得、したがって、実際の関数ｆ及び／又は関数ｇの隠蔽された実装を単純化することができる。
【００３２】
導出ユニットは、
【数６０】
0006303073.tif 000061
であるｐ∈Ｗ及びｑ∈Ｗについて、
【数６１】
0006303073.tif 000062
であるように、表現ｒ’’に基づいて表現ｒ’’’を得るための関数を計算する関数評価ユニットをさらに有することができ、ｇは、Ｗ上で定義された写像である。
【００３３】
このように、関数ｆ及び関数ｇは、前に実行されたスワップ演算に応じて、表現ｒ’’のｗ側又はσ側に適用され得、したがって、条件が成立するかどうかにかかわらず、ｆ及びｇの隠蔽された実装は同じにすることができる。
【００３４】
例えば、ｗ及びσの全ての値について、ｈ（ｗ，σ）＝σである。この例において、条件が真でないときには、表現のσ側は、表現のｗ側により影響が及ぼされない。これは、このスキームの対称性を向上させる。
【００３５】
決定ユニットは、条件に基づいて、ｗ’＝ｆｊ（ｗｊ）及びσ’＝σ、又は、ｗ’＝ｗ及びσ’＝ｆ（ｈ（ｗ，σ））のいずれかであるように、表現
【数６２】
0006303073.tif 000063
を決定するよう構成され得る。これは、例えば、ｅｌｓｅ部を有さないｉｆ文（例えば、if  b  then  w=f(w)）の隠蔽された実装を作成するのに使用され得る。
【００３６】
本発明の別の態様に従うと、演算を条件付きで実行する方法が提供される。本方法は、
値ｗであって、ｗは集合Ｗの要素である、値ｗを、表現ｒにより表現するステップであって、
【数６３】
0006303073.tif 000064
であり、ｒは、表現の集合
【数６４】
0006303073.tif 000065
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数６５】
0006303073.tif 000066
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
条件に関する入力に基づいて、表現ｒから、値ｗ’の表現ｒ’を導出するステップであって、ｗ’は集合Ｗの要素であり、ｒ’は、表現の集合
【数６６】
0006303073.tif 000067
の要素であり、
【数６７】
0006303073.tif 000068
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数６８】
0006303073.tif 000069
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、入力に応じて条件が成立するかどうかに基づいて、ｗ’がｆ（ｗ）に関連付けられるか、又は、σ’がｆ（ｈ（ｗ，σ））に関連付けられるか、のいずれかであり、ｆは、Ｗ上で定義された非自明写像であり、ｈは、Ｗ×ΣからＷへの写像である、ステップと、
を含む。
【００３７】
本発明の別の態様に従うと、演算を条件付きで実行するためのコンピュータコードを作成するシステムが提供される。本システムは、
条件と、変数ｗに対して実行される条件付き演算ｆであって、条件が成立する場合、ｗ’＝ｆ（ｗ）であるように変数ｗ’が計算されるように実行される条件付き演算ｆと、を特定する特定ユニットであって、ｗ’は集合Ｗの要素であり、ｆは、Ｗ上で定義された写像である、特定ユニットと、
第１のコンピュータコードを生成する第１の生成ユニットであって、第１のコンピュータコードは、実行されたときに、変数ｗであって、ｗは集合Ｗの要素である、変数ｗを、表現ｒにより表現するよう構成され、
【数６９】
0006303073.tif 000070
であり、ｒは、表現の集合
【数７０】
0006303073.tif 000071
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数７１】
0006303073.tif 000072
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、第１の生成ユニットと、
第２のコンピュータコードを生成する第２の生成ユニットであって、第２のコンピュータコードは、実行されたときに、条件に関する入力に基づいて、値ｗ’の表現ｒ’を決定するよう構成され、ｒ’は、表現の集合
【数７２】
0006303073.tif 000073
の要素であり、
【数７３】
0006303073.tif 000074
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数７４】
0006303073.tif 000075
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、第２の生成ユニットと、
を有し、
入力に応じて条件が成立する場合、ｗ’＝ｆ（ｗ）であり、入力に応じて条件が成立しない場合、σ’＝ｆ（ｈ（ｗ，σ））であり、ｈは、Ｗ×ΣからＷへの写像である。
【００３８】
このようなシステムを使用して、プレーンの（隠蔽されていない）演算を、隠蔽コードに変換することができる。例えば、本システムは、隠蔽コードを生成するコンパイラの一部として実装され得る。例えば、生成されるコンピュータコードは、マシンコード、擬似コード、又は仮想マシンコードを含み得る。
【００３９】
別の態様に従うと、演算を条件付きで実行するためのマシンコードを作成する方法が提供される。本方法は、
条件と、変数ｗに対して実行される条件付き演算ｆであって、条件が成立する場合、ｗ’＝ｆ（ｗ）であるように変数ｗ’が計算されるように実行される条件付き演算ｆと、を特定するステップであって、ｗ’は集合Ｗの要素であり、ｆは、Ｗ上で定義された写像である、ステップと、
第１のコンピュータコードを生成するステップであって、第１のコンピュータコードは、実行されたときに、変数ｗであって、ｗは集合Ｗの要素である、変数ｗを、表現ｒにより表現するよう構成され、
【数７５】
0006303073.tif 000076
であり、ｒは、表現の集合
【数７６】
0006303073.tif 000077
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数７７】
0006303073.tif 000078
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
第２のコンピュータコードを生成するステップであって、第２のコンピュータコードは、実行されたときに、条件に関する入力に基づいて、値ｗ’の表現ｒ’を決定するよう構成され、ｒ’は、表現の集合
【数７８】
0006303073.tif 000079
の要素であり、
【数７９】
0006303073.tif 000080
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数８０】
0006303073.tif 000081
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である、ステップと、
を含み、
入力に応じて条件が成立する場合、ｗ’＝ｆ（ｗ）であり、入力に応じて条件が成立しない場合、σ’＝ｆ（ｈ（ｗ，σ））であり、ｈは、Ｗ×ΣからＷへの写像である。
【００４０】
別の態様に従うと、プロセッサに上記の方法のうちの１つ以上の方法を実行させる命令を含むコンピュータプログラム製品が提供される。
【００４１】
本発明の上述した実施形態、実装、及び／又は態様のうちの２つ以上が、有用とみなされる何らかの形で組み合わされてもよいことが、当業者には理解されよう。
【００４２】
当業者であれば、本説明に基づいて、これらのシステムの説明された変更形態及び変形形態に対応する、これらの方法及び／又はコンピュータプログラム製品の変更形態及び変形形態を実施できるであろう。
【図面の簡単な説明】
【００４３】
本発明のこれらの態様及び他の態様が、以下で説明される実施形態から明らかであり、以下で説明される実施形態を参照すると明瞭になるであろう。
【図１】条件に応じて変換を実行するシステムのブロック図。
【図２】条件付き演算を隠蔽するシステムのブロック図。
【図３】条件付き演算を隠蔽する導出ユニットのブロック図。
【図４】条件付き演算を隠蔽する方法のフローチャート。
【図５】演算を条件付きで実行するためのマシンコードを作成するシステムのブロック図。
【図６】演算を条件付きで実行するためのマシンコードを作成する別のシステムのブロック図。
【図７】ネストされた条件付き演算を変換する方法のフローチャート。
【図８】隠蔽された演算を条件付きで実行するためのマシンコードを作成する方法のフローチャート。
【図９】変数の集合に対する変更を隠蔽するシステムのブロック図。
【図１０】変数の集合に対する変更を隠蔽する方法のブロック図。
【発明を実施するための形態】
【００４４】
以下において、データ値の暗号化をどのように改善させ、プログラムの内部動作をどのように隠蔽するかの説明が与えられる。このような技術は、例えば、セキュアな仮想マシンを作成するために適用され得る。また、他の種類のシステムが、本明細書で開示される技術を使用して、情報漏洩に対して保護され得る。本文書を通じて、隠蔽という用語は、例えばリバースエンジニアリングにより、プログラムの機能を発見することが難しいということを示すために、使用される。難読化が、どのような機能的演算がプログラムコードにおいて実行されるかを発見することが難しいということを示すために使用される別の用語である。
【００４５】
図１は、条件付き演算を実行するよう構成される変換ユニット１０１を有するシステムを示している。すなわち、変換ユニット１０１は、値ｗ及び条件ｂを受信し、ｂに応じたｗ’を出力する。条件ｂが真である場合、変換ユニットは、ｗ’＝ｆ（ｗ）を出力する。条件ｂが偽である場合、変換ユニット１０１は、
【数８１】
0006303073.tif 000082
を出力する。ここで、ｆ及びｇは、異なる関数である。代替の構成において、変換ユニット１０１は、条件自体の代わりにいくつかの変数（図示せず）を受信するよう構成され、変換ユニット１０１は、最初に、これらの変数に基づいて、条件ｂが真であるかどうかを判定するための式を評価する。その後に、変換ユニット１０１は、ｗ’＝ｆ（ｗ）（条件が真である場合）又は
【数８２】
0006303073.tif 000083
（条件が偽である場合）を出力する。以下において、ｗ及びｗ’並びに必要に応じてｂの値が暗号化される実施形態が開示される。
【００４６】
図２は、条件付き変換を隠蔽された形で実行するシステムを示している。このシステムは、値ｗの暗号化表現を特定する表現ユニット１０２を有する。例えば、ｗの値は、表現ユニット１０２の入力１０５で提供され、表現ユニット１０２は、ｗの値を暗号化して、ｗの暗号化された表現ｒを生成するよう構成される。代替的に、表現ユニット１０２は、入力値１０１として表現ｒを受信し、表現ｒを導出ユニット１０３に転送するよう構成されてもよい。いずれの場合においても、値ｗとその暗号化表現ｒとの間の例示的な関係は、以下のように説明され得る。
【００４７】
Ｗが、符号化されるべきオペランド（演算の入力値）の集合を表すとする。状態の有限集合Σと、Ｗの濃度とΣの濃度との積に等しい濃度を有する有限集合Ｖと、を定義する。Ｗ×Σの要素が、秘密符号化関数（secret  encoding  function）
【数８３】
0006303073.tif 000084
により、１対１の形でＶに写像される。要素ｗ∈Ｗの符号化された代表元（representatives）は、集合
【数８４】
0006303073.tif 000085
のメンバーである。
【００４８】
したがって、各要素ｗ∈Ｗの代表元の数は、Σの濃度に等しい。結果として、Ｖからのシンボルを伝達するデータパスは、Ｗからのシンボルを伝達するデータパスに等しい（Σの濃度＝１）か、又は、Ｗからのシンボルを伝達するデータパスより広い（Σの濃度＞１）か、である。すなわち、Σの濃度が、１より大きいときは、ｗの任意の特定の値を表現することができるより多くの値が存在する。なぜならば、表現
【数８５】
0006303073.tif 000086
は、ｗだけでなく、必ずしも何らかの意味を有するわけではない、ランダムに選択され得る状態変数σにも依存するからである。この状態変数σは、ｗの値を暗号化し、ｗに対して実行される任意の演算を隠蔽するために、単に導入される。好ましくは、Ｗ＝Σである、すなわち、少なくとも、Ｗの濃度は、Σの濃度に等しい。しかしながら、これは限定ではない。
【００４９】
符号化される（又は隠蔽される）関数ｆ：Ｗ→Ｗについて検討する。
【数８６】
0006303073.tif 000087
及びσ∈Σについて、
【数８７】
0006303073.tif 000088
であるような、Ｆ：Ｖ→Ｖを構築する。したがって、Ｆは、ｗの代表元をｆ（ｗ）の代表元に写像する。一般的な定義は、
【数８８】
0006303073.tif 000089
であり得る。
【００５０】
この例において、ｆ（ｗ）の代表元
【数８９】
0006303073.tif 000090
は、関数
【数９０】
0006303073.tif 000091
により、部分的に決定される。すなわち、ｆ（ｗ）の代表元に関連付けられる状態値は、値ｗと、関係
【数９１】
0006303073.tif 000092
を使用してｗの代表元に関連付けられる状態σと、の両方に依存し得る。特定の例において、ｇは、
【数９２】
0006303073.tif 000093
であるように、σのみに依存する。しかしながら、以下は、この特定の例に限定されるものではない。
【００５１】
したがって、式１において定義される値表現
【数９３】
0006303073.tif 000094
及び演算ｆ（ｗ）の符号化は、さらに、何らかの写像
【数９４】
0006303073.tif 000095
を使用して隠蔽される。この写像
【数９５】
0006303073.tif 000096
は、プログラム内で発生する演算ごとに異なり得る。したがって、それぞれの演算ｆｉを伴う複数の命令は、それぞれの関係
【数９６】
0006303073.tif 000097
を伴う対応する複数の命令を導入する。演算ｆｉを伴う複数の命令の実行順序は、関係
【数９７】
0006303073.tif 000098
を伴う複数の命令に対する実行の順序を生じさせ得る。実際、演算ｆｉにより構成される計算の他に、
【数９８】
0006303073.tif 000099
を計算するための新たな計算が発生する。この後者の計算は、以下では、σ計算又はσ軌道（trajectory）と呼ばれる。同様に、暗号化関数
【数９９】
0006303073.tif 000100
は、一連のそれぞれの暗号化関数
【数１００】
0006303073.tif 000101
を導入することにより、プログラム内の演算ごとに異なり得、したがって、任意の値ｗの表現は、各演算後に異なり得る。このような場合、式１は、以下の式１ａに一般化される：
【数１０１】
0006303073.tif 000102
【００５２】
命令の記述に関して、式１の対称性の一般化が利用され得る。関数ｑ０：Ｗ×Σ→Ｗ、関係ｑ１：Ｗ×Σ→Σについて検討する。式１は、以下の式２に一般化され得る：
【数１０２】
0006303073.tif 000103
【００５３】
このような場合、式１におけるｆ（ｗ）のおそらく部分的な情報が、ｑ０又はｑ１の一部として渡され得る。２つの観測がなされ得る。最初の観測は、特定の例において、ｑ０及びｑ１は暗号化であり得、
【数１０３】
0006303073.tif 000104
「のみ」が、値を組み合わせることである。２番目の観測は、値としてのｗ及び状態としてのσの役割が、小さくなる（diminishing）として確認され得ることである。これは、ｆ（ｗ）又はｗ、
【数１０４】
0006303073.tif 000105
又はσを決定することができるのに十分である。
【００５４】
プログラムフローを分かりにくくするために、ジャンプ演算が、排除され、上述した表現に関して代替の演算で置換され得る。しかしながら、現代のプロセッサアーキテクチャのｉｆ変換機能の場合とは異なり、このｉｆ変換は、犠牲の大きいパイプライン分裂（costly  pipeline  disruption）を防止するためではなく、制御フローにおける観測可能な変更を除去するために、行われる。このように、制御フローの解析は、プログラム内でなされるいかなる選択も明らかにしない。さらに、「if  Boolean  b  is  true,  then  operation  F  else  operation  G」等の条件付きプログラムを符号化するとき、条件（「if  Boolean  b  is  true」）の結果にかかわらず、両方の分岐（「operation  F（演算Ｆ）」及び「operation  G（演算Ｇ）」）が、
【数１０５】
0006303073.tif 000106
に寄与することが、本明細書で開示される技術により、確実にされ得る。そうすることにより、プログラム全体にわたる条件の統計学的な広がり（statistical  spread）が実現され得る。例えば、
・ｗの展開が、条件の結果に対応する分岐により決定され、
・σの展開が、条件の結果に対応しない分岐により決定される。
【００５５】
ｗ及びσの両方が、同時に計算され得る、且つ／又は、
【数１０６】
0006303073.tif 000107
により、不可分に結び付けられ得る。結果として生じたデータを解析することによっては、進んだ分岐、条件の値のいずれも判別することができない。条件の結果に基づく、従来技術において実装されるであろうジャンプ演算は、排除され得るので、プログラムの制御フローから情報を抽出するのは難しくなる。値
【数１０７】
0006303073.tif 000108
は、ｉｆ−ｔｈｅｎ−ｅｌｓｅ構文の両方の分岐に依存するようにされ得る。情報理論の観点からは、ｗ及びσのエントロピーは、非常に良好に広がる。
【００５６】
例えば、図１の変換ユニット１０１により実行される変換のプログラム表現は、以下であり得る：
【数１０８】
0006303073.tif 000109
【００５７】
図２に示される例示的な実施形態において、導出ユニット１０３は、上述したように、値ｗの暗号化された表現ｒと、条件ｂ１０４に関する入力情報と、を受信する。この入力情報は、ブーリアン変数又は暗号化されたブーリアン変数であり得る。代替的に、この入力情報は、条件を定義する述語において、例えば変換ユニット１０１により組み合わされ得る１つ以上の変数を含んでもよい。
【００５８】
図１の上記の条件付きプログラムは、上述したように状態変数を使用して冗長性を導入することにより、再プログラムされ得、ここで、
【数１０９】
0006303073.tif 000110
は、オペランドｗの表現であり、ｒ’は、結果ｗ’の表現であり、したがって、σ及びσ’のいくつかの値について、
【数１１０】
0006303073.tif 000111
である。導出ユニット１０３の出力は、以下のようにまとめられ得る：
【数１１１】
0006303073.tif 000112
【００５９】
演算
【数１１２】
0006303073.tif 000113
及び演算
【数１１３】
0006303073.tif 000114
はそれぞれ、ルックアップテーブルの形態で実装され得る。しかしながら、ｉｆ文及び導出ユニット１０３内部の対応する条件付きジャンプ演算の実行を回避するために、ｂと表現ｒとの組合せを、ｒ’の対応する値に直接的にマッピングするルックアップテーブルにより、導出ユニット１０３を実装することが可能である。ここで、ｂは、暗号化されたブーリアン変数であり得る。さらに、ｂは、１つ以上の入力変数で置換され得、ここで、条件ｂは、１つ以上の入力変数の関数である。このような場合、１つ以上の入力変数と表現ｒとの組合せが、ルックアップテーブルにより、ｒ’の対応する値にマッピングされ得る。このような場合、条件ｂを定義する関数は、ルックアップテーブルにおいてｆ及びｇとともに符号化され得る。ルックアップテーブルの代わりに、ルックアップテーブルのネットワークが使用されてもよい。ルックアップテーブルのネットワークとして関数を実装する方法は、それ自体当分野において既知である。
【００６０】
上記から分かるように、演算ｆ及び演算ｇの両方が、条件（「if  b」）の結果にかかわらず、表現ｒ’に影響を及ぼす。したがって、ｆ及びｇの両方が、ｒ’の「エントロピー」に寄与し、これらの条件付き演算から情報を抽出するのを難しくする。
【００６１】
図３は、導出ユニット１０３の例示的な実装を示している。この特定の実装において、ｉｆ文（又は条件付きジャンプ演算）は、スワップ演算３０５及びスワップ演算３０６の２つのスワップ演算で置換されている。このようなスワップ演算は、例えば、ルックアップテーブルの形態で実装され得る。以下の３つのラインのそれぞれのラインにおいて記述される演算は、例えば、それぞれのルックアップテーブルにより実装され得る。
入力：ｂ及びｒ、ここで、
【数１１４】
0006303073.tif 000115
ライン１：
【数１１５】
0006303073.tif 000116
ライン２：
【数１１６】
0006303073.tif 000117
ライン３：
【数１１７】
0006303073.tif 000118
出力：ｒ’’’、ここで、
【数１１８】
0006303073.tif 000119
又は
【数１１９】
0006303073.tif 000120
【００６２】
上記のコードフラグメントのライン１は、表現
【数１２０】
0006303073.tif 000121
の値（ｗ）部分と状態（σ）部分とを、条件ｂ（符号１０４）に基づいて、条件付きで交換するスワップ演算３０５の機能を明らかにするものである。上記のコードフラグメントのライン２は、ブロック３０７において関数ｆ及び関数ｇが表現ｒ’にどのように適用されるかを明らかにするものである。ライン３は、再度、表現
【数１２１】
0006303073.tif 000122
の値（ｗ）部分と状態（σ）部分とを、条件ｂ（符号１０４）に基づいて、条件付きで交換するスワップ演算３０６の機能を明らかにするものである。
【００６３】
ライン１の後、ｒ’は、ｂに応じて、
【数１２２】
0006303073.tif 000123
又は
【数１２３】
0006303073.tif 000124
のいずれかであり得ることに留意されたい。ライン２において、シンボルｐ及びシンボルｑは、
【数１２４】
0006303073.tif 000125
であるように定義される。ライン２において、関数ｆは、ｂが真である場合、ｗに実効的に適用される。一方、ｂが真でない場合、関数ｇが、ｗに実効的に適用されるが、ライン１の先行するスワップ演算に起因して、ｗは、表現ｒ’の「状態」の部分、すなわち、「σ」部分になっている。したがって、ｒ’の「ｗ」部分と「σ」部分とを交換するために、追加のスワップ演算が、ライン３において提供される。ライン３において、シンボルｕ及びシンボルｖは、
【数１２５】
0006303073.tif 000126
であるように定義される。すなわち、ｕ＝ｆｉ（ｐ）及び
【数１２６】
0006303073.tif 000127
である。ライン３において、ｂが真でない場合、表現ｒ’’の「状態」すなわち「σ」部分において得られた所望の値が、表現ｒ’’’の「ｗ」部分に移される。
【００６４】
ライン１及びライン３はそれぞれ、スワップ関数を表す。このようなスワップ関数は、ルックアップテーブルとして実装され得、ルックアップテーブルにおいて、適切な値が、ｂ及び表現ｒ（又はｒ’’）の値に基づいて、ルックアップされる。
【数１２７】
0006303073.tif 000128
及び
【数１２８】
0006303073.tif 000129
であるように
【数１２９】
0006303073.tif 000130
、
【数１３０】
0006303073.tif 000131
、
【数１３１】
0006303073.tif 000132
、及び
【数１３２】
0006303073.tif 000133
を選択することにより、ライン１及びライン３の両方について同じルックアップテーブルを使用することが可能である。ｒ及びｂの値をｒ’’’の対応する値に直接的にマッピングする単一のルックアップテーブルにおいてライン１〜ライン３の結果を符号化することも可能である。
【００６５】
図２を参照すると、このコードフラグメントに対応する隠蔽された演算を実行する導出ユニット１０３はまた、以下のように出力を決定するよう構成され得る：
入力：条件ｂ及び表現ｒ、ここで、
【数１３３】
0006303073.tif 000134
【数１３４】
0006303073.tif 000135
ここで、ｈは、Ｗ×ΣからＷへの写像である。この場合、スワップ演算は使用されない。また、この実装は、Ｗ≠Σである場合又はＷの濃度がΣの濃度と異なる場合に適している。ｉｆ節の両方の分岐をルックアップテーブルの形態で実装し、条件ｂに応じて、これらのルックアップテーブルのうちの１つのルックアップテーブルを適用することが可能である。関数ｆ及び関数ｇは、条件ｂにかかわらず、結果ｒ’に影響を及ぼすことになる。代替的に、ｒ及びｂ（又はｂを判定する変数）のタプルを対応する表現ｒ’にマッピングする１つのルックアップテーブルが実装されてもよい。
【００６６】
特別なケースは、プログラムの隠蔽されていないバージョンにおいてｅｌｓｅ分岐が存在しない場合、すなわち、プログラム
【数１３５】
0006303073.tif 000136
を考慮する場合である。この場合、前述の例の関数
【数１３６】
0006303073.tif 000137
は、恒等式（identity）に等しい。すなわち、決定ユニット１０３は、条件に基づいて、
ｗ’＝ｆ（ｗ）及びσ’＝σ（条件が真である場合）であるか、又は
ｗ’＝ｗ及びσ’＝ｆ（ｈ（ｗ，σ））（条件が偽である場合）であるか、
のいずれかであるように、表現
【数１３７】
0006303073.tif 000138
を決定するよう構成される。これは、本質的にセキュリティリスクをもたらさない。なぜならば、何らかの展開が常に存在し、関数ｆを、暗号化されたドメインのｗ又は状態σのいずれかに適用することにより、エントロピーの広がりが維持されるからである。しかしながら、この状況は、さらに、影響が及ぼされない変数についてダミー演算を挿入することによって両方の分岐をバランスさせることにより、改善され得る。条件に応じて、異なる変数に影響が及ぼされ得る場合、何らかのｉｆ文をバランスさせることにより、プログラムをさらに隠蔽することを目的とする演算「Ｂａｌａｎｃｅ」について検討する。
【数１３８】
0006303073.tif 000139
上記について、例えば、Ｂａｌａｎｃｅ（ｘ：＝ｘ＋１，ｙ：＝ｆ（５））は、ｘ：＝ｘ＋１；Ｄｕｍｍｙ（ｙ）を意味する。ここで、Ｄｕｍｍｙ（ｙ）は、変数に対する任意の演算であって、該変数を変更しない任意の演算を表すことができる。例えば、Ｄｕｍｍｙ（ｙ）は、ｙ：＝ｙ＊１、ｙ：＝ｙ＋０、
【数１３９】
0006303073.tif 000140
のうちのいずれか１つを意味し得る。本開示に鑑みれば、他のダミー演算も、当業者には明らかであろう。
【００６７】
すなわち、複数の分岐であって、各分岐が条件に応じて条件付きで実行される、複数の分岐を含む条件付きコードセグメントが、
・条件分岐のうちの少なくとも１つの分岐において変更される変数であって、条件分岐のうちの少なくとも１つの他の分岐においては変更されない変数を判別し、
・その判別された変数についてダミー演算を作成し、
・そのダミー演算を、条件分岐のうちの上記少なくとも１つの他の分岐に含める
ことにより、バランスされ得る。上記の３つのステップは、条件分岐に関わる各変数について繰り返され得る。
【００６８】
図４は、演算を条件付きで実行する方法を示している。ステップ４０１において、値ｗであって、ｗは集合Ｗの要素である、値ｗが、表現ｒにより表現され、ここで、
【数１４０】
0006303073.tif 000141
であり、ｒは、表現の集合
【数１４１】
0006303073.tif 000142
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数１４２】
0006303073.tif 000143
は、Ｗ×Σから予め定められた集合への暗号化写像である。この表現ｒは、例えば、受信され得る。代替的に、この表現は、状態変数σを乱数として決定し、
【数１４３】
0006303073.tif 000144
を計算又はルックアップすることにより、入力値ｗから生成されることもある。
【００６９】
ステップ４０２において、値ｗ’の表現ｒ’が決定され、ここで、ｗ’は、集合Ｗの要素であり、ｒ’は、表現の集合
【数１４４】
0006303073.tif 000145
の要素であり、
【数１４５】
0006303073.tif 000146
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数１４６】
0006303073.tif 000147
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。例えば、ｒ’の値は、条件ｂを判定する１つ以上の入力変数及び表現ｒに基づいて、ルックアップテーブルにおいてルックアップされる。任意的に、上記で説明されたように、スワップ演算、関数演算、及び別のスワップ演算を伴う一連のテーブルルックアップが、実行される。これらのテーブルは、条件ｂに応じて、ｗ’がｆ（ｗ）に関連付けられるか、又は、σ’がｆ（ｈ（ｗ，σ））に関連付けられるか、のいずれかであるように、設計される。ここで、ｆは、Ｗ上で定義された写像であり、ｈは、Ｗ×ΣからＷへの写像である。
【００７０】
特定の例において、上記の方法は、条件に基づいて、例えば条件が真である場合、
【数１４７】
0006303073.tif 000148
であるように、ｆを、暗号化された表現
【数１４８】
0006303073.tif 000149
の「ｗ」部分に適用する。そうでなければ、例えば条件が偽である場合、
【数１４９】
0006303073.tif 000150
であるように、ｆは、
【数１５０】
0006303073.tif 000151
の「σ」部分に適用される。この方法のさらなる変形例が、図１〜図３を参照して上述したように、提供され得る。例えば、「ｅｌｓｅ」分岐を伴う変形例は、条件に基づいて、
【数１５１】
0006303073.tif 000152
又は
【数１５２】
0006303073.tif 000153
のいずれかであるように、なされ得る。
【００７１】
図５は、演算を条件付きで実行するためのマシンコードを作成するシステムを示している。このシステムは、条件と、変数ｗに対して実行される条件付き演算ｆであって、条件が成立する場合、ｗ’＝ｆ（ｗ）であるように変数ｗ’が計算されるように実行される条件付き演算ｆと、を特定する特定ユニット５０１を有し、ここで、ｗ’は、集合Ｗの要素であり、ｆは、Ｗ上で定義された写像である。例えば、特定ユニット５０１は、条件及び条件付き演算を特定するためにコンピュータプログラムの式を抽出する、コンパイラのパーサモジュール（図示せず）に接続され得る。
【００７２】
特定ユニット５０１は、特定された条件及び条件付き演算に関する情報を、マシンコードを生成する第１の生成ユニット５０２に提供することができる。生成されたマシンコードは、実行されたときに、変数ｗであって、ｗは集合Ｗの要素である、変数ｗを、表現ｒにより表現し、ここで、
【数１５３】
0006303073.tif 000154
であり、ｒは、表現の集合
【数１５４】
0006303073.tif 000155
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数１５５】
0006303073.tif 000156
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。例えば、マシンコードは、実際の入力値ｗ及び乱数σから、表現ｒを生成することができる。代替的に、第１の生成ユニット５０２により生成されたマシンコードは、実行されたときに、表現が記憶されているメモリ位置を参照することもできるし、別のソフトウェアコンポーネント又は入力デバイスから、表現ｒを受信することもできる。
【００７３】
このシステムは、第２の生成ユニット５０３をさらに有する。第２の生成ユニット５０３は、表現ｒと条件に関する入力とに基づいて、ｗ’の表現ｒ’を決定するためのマシンコードを生成する。ここで、ｒ’は、表現の集合
【数１５６】
0006303073.tif 000157
の要素であり、
【数１５７】
0006303073.tif 000158
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数１５８】
0006303073.tif 000159
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。条件が成立する場合、ｗ’＝ｆ（ｗ）であり、条件が成立しない場合、σ’＝ｆ（ｈ（ｗ，σ））であり、ここで、ｈは、Ｗ×ΣからＷへの写像である。第２の生成ユニット５０３は、関数を実装するために使用され得る上述したルックアップテーブルのうちの１つ以上のルックアップテーブルを生成するテーブル生成器（図示せず）を有することができる。このシステムは、上述した計算又はテーブルルックアップを実行するために必要なマシンコードを生成するように拡張され得る。
【００７４】
図６は、演算を条件付きで実行するためのマシンコードを生成するシステムのさらなる実施形態を示している。図５におけるアイテムと同様のアイテムには、同じ参照符号が付与されており、それらのアイテムは、再度詳細に説明される必要はない。このシステムは、複数の条件を伴うネストされた条件付き演算を、一連のネストされていない条件付き演算に変換する変換ユニット６０１を有する。詳細には、対応する条件を伴う一連のネストされていない条件付き演算は、出力値が同一であるという点で、ネストされた条件付き演算と等価である。さらに、対応する条件を伴うネストされていない条件付き演算は、特定ユニット５０１並びにコード生成ユニット５０２及びコード生成ユニット５０３により処理され得る。
【００７５】
図７は、複数の条件を伴うネストされた条件付き演算を、一連のネストされていない条件付き演算に変換する例示的な方法を示している。図６の変換ユニット６０１が、図７に示される方法を実行するよう構成され得る。
【００７６】
ステップ７０１において、ネストされた条件付き演算のそれぞれの条件分岐のそれぞれの式が、補助式の項に変換される。これらのそれぞれの式は、条件に応じて、特定の変数に割り当てられる代替値に関連付けられる。すなわち、これらの式は、生成されたコードの同じ変数に割り当てられるように定められるが、この変数にどの式が最終的に割り当てられることになるかを条件が決定する。ステップ７０２において、ステップ７０１が繰り返される必要があると判定された場合、フローはステップ７０１に戻り、項が異なる様式で組み合わされる複数の補助式が生成される。ステップ７０２において、各条件付き演算が、補助項の特定の組合せに等価であるように、十分な補助式が生成されていると判定された場合、この方法は、ステップ７０３に進む。ステップ７０３において、補助式を評価し、これらの補助式の結果を記憶するためのコードが、生成される。このステップは、複数の条件のうちの少なくとも１つの条件の組合せを評価するためのコードを生成することを含み得る。次いで、ステップ７０４において、組み合わされた条件に応じて、補助式の結果を組み合わせるためのコードが、生成され、ここで、組み合わされた条件は、条件の観点から関連しない分岐に対応する項が相殺するような、複数の条件の組合せである。
【００７７】
再度、条件付きコードセグメント「if  b  then  F  else  G  fi」について検討する。このような文の条件分岐Ｆ及び条件分岐Ｇは、複数の式、例えば、例えば「Ｆ１；Ｆ２」と表記される一連の演算を含み、ループ、再帰、又は、追加のｉｆ文等の追加の条件付きコードセグメントを含み得る。後者の状況は、ネストされたブーリアンガード付き選択を提示する。プログラムＰを、
【数１５９】
0006303073.tif 000160
として定義する。
【００７８】
ここで、４つの代替（Ｆ、Ｇ、Ｈ、及びＪ）が存在し、これらの４つのうちの１つのみが実行されるべきである。上述した技術が、Ｐ１及びＰ２に適用されるとき、ｂ１に依存するメイン分岐は、依然として、隠蔽技術により必ずしも完全にはカバーされない。
【００７９】
これに対処する１つの方法は、ネストされたｉｆ文を、一連のネストされていないｉｆ文で置換し、この一連のネストされていないｉｆ文を実行するプロセスにおいて各分岐（Ｆ、Ｇ、Ｈ、Ｊ）の式が全て評価されるようにこれを行うことである。
【００８０】
このようにプログラムを変換するために、ダミー演算を挿入することにより、式が、最初にバランスされ得る。
【００８１】
プログラムがもはやネストされたｉｆ節を含まないようにプログラムをフラット化するために、体系立てられた方法が適用され得る。
【００８２】
上記で確認したように、提案する方法は、プログラム、特にｉｆ節の分岐のペアが、エントロピー的に完全にバランスされる場合に、暗号論的に最良に機能する。分岐が、（無条件の）割り当てと１つ以上のネストされたｉｆ節との両方を含む場合、以下のように、ｉｆ節の各分岐においてこのような割り当てのコピーを分配することにより、これらをフラット化することができる：
・
【数１６０】
0006303073.tif 000161
・
【数１６１】
0006303073.tif 000162
【００８３】
変数ｘに関して好ましくはバランスされている以下のネストされたｉｆ節について検討する：
【数１６２】
0006303073.tif 000163
【００８４】
上記において、ｅｘｐ０、ｅｘｐ１、ｅｘｐ２、及びｅｘｐ３は、ｘに依存する式である。
ｐ：＝ｅｘｐｉ＋ｅｘｐｉ＋１及びｑ：＝ｅｘｐｉ−ｅｘｐｉ＋１を補助変数として導入すると、このプログラムは、以下のように変換され得る：
【数１６３】
0006303073.tif 000164
【００８５】
ここでは、２つの第２レベルのｉｆ節の後の続きの部分が、同一になったので、このプログラムは、以下に「フラット化」され得る：
プログラム１：
【数１６４】
0006303073.tif 000165
又は、乗法形式の変形例を使用すると：
【数１６５】
0006303073.tif 000166
【００８６】
結果として生じる２つのｉｆ文は、上記の暗号化された表現
【数１６６】
0006303073.tif 000167
についての技術を使用して実装され得る。例えば、上記のプログラム１の最初のｉｆ文に関して、表現ｒは、入力変数ｘを表現するために使用され得、表現ｒ１及び表現ｒ２は、ｐ及びｑを表現するために使用され得る。さらなる表現が、プログラム１の２番目のｉｆ文の出力ｘを表現するために使用され得る。
【００８７】
ｉｆ文が、より深いレベルまでネストされている場合、同様の技術を適用して、それらのｉｆ文を、一連の順次のｉｆ文に変換することができる。例えば、ｉｆ文が２回ネストされている以下の例示的なプログラムについて検討する：
【数１６７】
0006303073.tif 000168
【００８８】
この例示的なプログラムは、一連のネストされていないｉｆ文に変換され得る。そうするために、２ステップアプローチが採用され得る。最初に、１回ネストされているｉｆ文の場合と同様に、第３レベルのｉｆ節からの続きの部分が、補助変数ｐ：＝ｅｘｐｉ＋ｅｘｐｉ＋１及び補助変数ｑ：＝ｅｘｐｉ−ｅｘｐｉ＋１を導入することにより、統一化され得る。これが、以下のコードにおいて、より詳細に示される：
【数１６８】
0006303073.tif 000169
【００８９】
このプログラムをフラット化して、ネストされたｉｆ節を含まない以下のコードを得ることができる：
【数１６９】
0006303073.tif 000170
【００９０】
２回ネストされたｉｆ節を含むプログラムを順次のネストされていないｉｆ節を含むプログラムに変換する上記の変換手順が、任意の式ｅｘｐ０〜式ｅｘｐ７に関して、上記のフォーマットを有する任意のプログラムに適用され得る。
【００９１】
図８は、演算を条件付きで実行するためのコンピュータコードを作成する方法を示している。ステップ８０１は、条件と、変数ｗに対して実行される条件付き演算ｆであって、条件が成立する場合、ｗ’＝ｆ（ｗ）であるように変数ｗ’が計算されるように実行される条件付き演算ｆと、を特定することを含み、ここで、ｗ’は、集合Ｗの要素であり、ｆは、Ｗ上で定義された写像である。ステップ８０２は、第１のコンピュータコードを生成することを含み、ここで、第１のコンピュータコードは、実行されたときに、変数ｗであって、ｗは集合Ｗの要素である、変数ｗを、表現ｒにより表現するよう構成され、ここで、
【数１７０】
0006303073.tif 000171
であり、ｒは、表現の集合
【数１７１】
0006303073.tif 000172
の要素であり、σは、集合Σの要素であって、ｗの表現ｒに冗長性を提供する状態変数であり、
【数１７２】
0006303073.tif 000173
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。ステップ８０３は、第２のコンピュータコードを生成することを含み、ここで、第２のコンピュータコードは、実行されたときに、条件に関する入力に基づいて、値ｗ’の表現ｒ’を決定するよう構成され、ここで、ｒ’は、表現の集合
【数１７３】
0006303073.tif 000174
の要素であり、
【数１７４】
0006303073.tif 000175
であり、σ’は、集合Σの要素であって、ｗ’の表現ｒ’に冗長性を提供する状態変数であり、
【数１７５】
0006303073.tif 000176
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、入力に応じて条件が成立する場合、ｗ’＝ｆ（ｗ）であり、入力に応じて条件が成立しない場合、σ’＝ｆ（ｈ（ｗ，σ））であり、ｈは、Ｗ×ΣからＷへの写像である。
【００９２】
プログラム内のジャンプの除去を用いて、伴われる値又は制御フローの解析を禁じることができる。条件の観点から関連しない分岐があっても、ｉｆ文の全ての分岐においてなされる演算を計算して、これらの計算の結果を１つのデータ要素に組み合わせることは、この目標に到達するのを助けることができる。
【００９３】
ジャンプが抑制されるテーブル駆動マシンのシステムを作成して、プログラムの制御フローにおける変更を除去することができ、ここで、ブーリアンガード付き選択の場合における
【数１７６】
0006303073.tif 000177
の形態の符号化が、進まない分岐に沿って多くてもσだけ、且つ、進む分岐に沿って少なくともｗだけ、展開する。
【００９４】
図９は、プログラムの変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝に対する変更を隠蔽するシステムを示している。このシステムは、変数ｖ１，ｖ２，．．．，ｖｎのうちの変数ｖｉの値ｗｉであって、ｗは集合Ｗの要素である、値ｗｉを、表現ｒｉにより表現する値表現手段９０２を有し、ここで、
【数１７７】
0006303073.tif 000178
であり、ｒｉは、表現の集合
【数１７８】
0006303073.tif 000179
の要素であり、σｉは、集合Σの要素であって、ｗｉの表現ｒｉに冗長性を提供する状態変数であり、
【数１７９】
0006303073.tif 000180
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。この値表現手段９０２は、上記で開示された技術を使用して実装され得る。値表現手段９０２は、指定されるように、変数ｖ１，ｖ２，．．．，ｖｎの全てを、それぞれの表現ｗ１，ｗ２，．．．，ｗｎにより表現するよう構成され得る。σ１，σ２，．．．，σｎの値は、例えば、ランダムに選択され得る。値表現手段９０２は、基礎となる値ｗｉに基づいて、表現ｒｉを計算するよう構成され得る。値表現手段９０２はまた、別のデバイスから又はこのシステムの別のコンポーネントから、表現ｒｉを受信するよう構成され得る。ｎは正の整数である。すなわち、一般に、変数の集合Ｖは、少なくとも１つの変数を含む。
【００９５】
このシステムは、ｉ＝１，２，．．．，ｎについて、更新された表現
【数１８０】
0006303073.tif 000181
を得るために、Ｖの部分集合Ｖ’内の変数の値に対するアクションを、Ｖ’に対するアクションと、
【数１８１】
0006303073.tif 000182
に対するアクションと、により表現するアクション表現手段９０３をさらに有することができ、ここで、
【数１８２】
0006303073.tif 000183
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。
【数１８３】
0006303073.tif 000184
は、
【数１８４】
0006303073.tif 000185
に等しくてよい。代替的に、
【数１８５】
0006303073.tif 000186
は、
【数１８６】
0006303073.tif 000187
とは異なる暗号化写像であってもよい。したがって、表現を変更するときに、暗号化写像を変更することが可能である。
【００９６】
さらに、アクション表現手段は、Ｖ’に対するアクションと、
【数１８７】
0006303073.tif 000188
に対するアクションと、を実行するよう構成され得る。代替的に、アクション表現手段は、実行されたときにこれらのアクションを実行するプログラムコードを生成することにより、これらのアクションを単に表現するよう構成されてもよい。後者の場合、アクション表現手段９０３は、部分集合Ｖ’内の変数の値に対するアクションを定義しているプログラムコードを（例えばパーサにより）特定し、このプログラムコードを、Ｖ’に対するアクションと、
【数１８８】
0006303073.tif 000189
に対するアクションと、を定義するプログラムコードに変換するよう構成され得る。
【００９７】
Ｖ’に対するアクションは、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更するよう構成され、
【数１８９】
0006303073.tif 000190
に対するアクションは、
【数１９０】
0006303073.tif 000191
内の各変数ｖｋの表現ｒｋを、状態変数σｋの変更された値σ’ｋに応じて変更するよう構成される。詳細には、
【数１９１】
0006303073.tif 000192
内の各変数ｖｋの表現ｒｋが、同じ値のｗｋを表現する表現に変更される。変数の集合Ｖ’内の各変数ｖｊの表現ｒｊが、同じ値のσｊ（又は任意的に異なる値のσｊ）を保ちながら、変数ｖｊの変更された値ｗ’ｊに応じて変更され得る。
【００９８】
アクションは、条件が成立する場合の変数の集合Ｖ１に対するアクションと、条件が成立しない場合の変数の集合Ｖ２に対するアクションと、を定義しているｉｆ文を含み得、ここで、Ｖ１及びＶ２の両方が、Ｖの部分集合である。すなわち、変数の集合Ｖは、Ｖ１及びＶ２の和集合（合併）を含み、したがって、Ｖ１∪Ｖ２⊂Ｖである。アクション表現手段９０３は、条件が成立する場合には、変数の集合Ｖ’として変数の集合Ｖ１を使用するよう構成され得る。これは、アクション表現手段９０３が、変数の集合Ｖ１内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更することにより、Ｖ１に対するアクションを実行し、
【数１９２】
0006303073.tif 000193
内の各変数ｖｋの表現ｒｋを、状態変数σｋの変更された値σ’ｋに応じて変更することにより、
【数１９３】
0006303073.tif 000194
に対するアクションを実行することを意味する。
【００９９】
さらに、アクション表現手段９０３は、条件が成立しない場合には、変数の集合Ｖ’として変数の集合Ｖ２を使用するよう構成され得る。これは、アクション表現手段９０３が、変数の集合Ｖ２内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更することにより、Ｖ２に対するアクションを実行し、
【数１９４】
0006303073.tif 000195
内の各変数ｖｋの表現ｒｋを、状態変数σｋの変更された値σ’ｋに応じて変更することにより、
【数１９５】
0006303073.tif 000196
に対するアクションを実行することを意味する。
【０１００】
変数のうちの一部は、条件が成立するか否かにかかわらず、条件付きコードセグメントにより変更され得る。そのような場合、変数の集合Ｖ１及び変数の集合Ｖ２は、積集合（共通部分）Ｖ３を有し、Ｖ３＝Ｖ１∩Ｖ２である。アクションは、条件が成立する場合には、関数ｆｍに従って、条件が成立しない場合には、関数
【数１９６】
0006303073.tif 000197
に従って、集合Ｖ３の各変数ｖｍの値を変更する。アクション表現手段９０３は、条件が成立する場合には、ｗ’ｍ＝ｆｍ（ｗｍ）及び
【数１９７】
0006303073.tif 000198
であるように、また、条件が成立しない場合には、
【数１９８】
0006303073.tif 000199
及びσ’ｋ＝ｆｍ（ｈｍ（ｗｍ，σｍ））であるように、集合Ｖ３の各変更された変数ｖｍの表現
【数１９９】
0006303073.tif 000200
を決定するアクションにより、これらのアクションを表現するよう構成される。ここで、ｈｍは、Ｗ×ΣからＷへの写像である。
【０１０１】
アクション表現手段９０３は、ルックアップ演算により実装され得る。このために、１つ以上のルックアップテーブルが、準備され、このシステムのメモリに記憶され得る。条件が成立するかどうかは、このシステムにより明示的に判定される必要がない。そうではなく、条件を判定する値の入力が受信され得る。１つ以上のルックアップテーブルは、これらの入力値とともに表現を、対応する変更された表現にマッピングすることができる。したがって、アクション表現手段９０３は、表現ｒｉ及び条件に関する入力に対応する表現ｒ’ｉのルックアップを、表現ｒｉ及び条件に関する入力のタプルを、対応する表現ｒ’ｉにマッピングしている少なくとも１つのルックアップテーブルを使用して生じさせるよう構成され得る。
【０１０２】
アクション表現手段９０３はまた、図３を参照して上述した１つ以上のスワップ演算により実装され得る。アクション表現手段９０３は、条件ｂを判定する１つ以上の入力変数を特定するよう構成され得、変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝内の変数の各変数について、上述した第１のスワップユニット３０５、関数評価ユニット３０７、及び／又は第２のスワップユニット３０６を含み得る。
【０１０３】
上述した値表現手段９０２及びアクション表現手段９０３は、上述した変換ユニット６０１に動作可能に接続され得る。変換ユニット６０１は、第１の複数のネストされた条件を伴うネストされた条件付き演算を、第２の複数の条件を伴う機能的に等価な一連のネストされていない条件付き演算により表現する。例えば、一連のネストされていない条件付き演算は、変換ユニット６０１がネストされた条件付き演算を処理することにより、生成され得る。結果として生じたネストされていない条件付き演算の各々が、上記の方法で、アクション表現手段９０３により、個々に表現され得る。
【０１０４】
図１０は、プログラムの変数の集合Ｖ＝｛ｖ１，ｖ２，．．．，ｖｎ｝に対する変更を隠蔽する方法を示している。ステップ１００１において、変数ｖ１，ｖ２，．．．，ｖｎのうちの変数ｖｉの値ｗｉであって、ｗは集合Ｗの要素である、値ｗｉが、表現ｒｉにより表現され、ここで、ｗは、集合Ｗの要素であり、
【数２００】
0006303073.tif 000201
であり、ｒｉは、表現の集合
【数２０１】
0006303073.tif 000202
の要素であり、σｉは、集合Σの要素であって、ｗｉの表現ｒｉに冗長性を提供する状態変数であり、
【数２０２】
0006303073.tif 000203
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像である。ステップ１００２において、ｉ＝１，２，．．．，ｎについて、更新された表現
【数２０３】
0006303073.tif 000204
を得るために、Ｖの部分集合Ｖ’の値に対するアクションが、Ｖ’に対するアクションと、
【数２０４】
0006303073.tif 000205
に対するアクションと、により表現され、ここで、
【数２０５】
0006303073.tif 000206
は、Ｗ×Σから予め定められた集合への１対１の暗号化写像であり、Ｖ’に対するアクションは、変数の集合Ｖ’内の各変数ｖｊの表現ｒｊを、変数ｖｊの変更された値ｗ’ｊに応じて変更するよう構成され、
【数２０６】
0006303073.tif 000207
に対するアクションは、
【数２０７】
0006303073.tif 000208
内の各変数ｖｋの表現ｒｋを、σｋの変更された値σ’ｋに応じて変更するよう構成される。
【０１０５】
本発明は、本発明を実施するよう適合されているコンピュータプログラム、特にキャリア上又はキャリア内のコンピュータプログラムにも適用される。コンピュータプログラム製品に関する一実施形態は、本明細書に記載の方法のうちの少なくとも１つの方法の各処理ステップに対応するコンピュータ実行可能な命令を含む。これらの命令は、サブルーチンに細分割され得る、且つ／又は、静的又は動的にリンクされ得る１つ以上のファイルに記憶され得る。コンピュータプログラム製品に関する別の実施形態は、本明細書に記載のシステム及び／又は製品のうちの少なくとも１つの各ユニットに対応するコンピュータ実行可能な命令を含む。これらの命令は、サブルーチンに細分割され得る、且つ／又は、静的又は動的にリンクされ得る１つ以上のファイルに記憶され得る。
【０１０６】
コンピュータプログラムのキャリアは、プログラムを運ぶことができる任意のエンティティ又はデバイスとすることができる。例えば、キャリアは、例えば、ＣＤ  ＲＯＭ若しくは半導体ＲＯＭといったＲＯＭ等の記憶媒体、又は磁気記録媒体を含み得る。さらに、キャリアは、電気ケーブル、光ケーブル、無線、又は他の手段を介して伝達され得る電気信号又は光信号等の伝送可能なキャリアであってもよい。プログラムが、そのような信号内に具現化される場合、キャリアは、そのようなケーブル、又は、他のデバイス若しくは手段により構成され得る。代替的に、キャリアは、プログラムが組み込まれる集積回路であって、当該の方法を実行する又当該の方法の実行の際に使用されるよう適合されている集積回路であってもよい。
【０１０７】
上述した実施形態は、本発明を限定しているのではなく例示していること、及び、当業者であれば、請求項の範囲から逸脱することなく多くの代替実施形態を設計できること、に留意されたい。請求項において、括弧内に配置されるいかなる参照符号も、請求項を限定するものとして解釈されるべきではない。動詞「備える、有する、含む」及びその活用形の使用は、請求項に記載されている要素又はステップ以外の要素又はステップの存在を排除するものではない。要素に先行する品詞「a」又は「an」は、複数のそのような要素の存在を排除するものではない。本発明は、複数の異なる要素を有するハードウェアを用いて、適切にプログラムされたコンピュータを用いて、実施され得る。複数の手段を列挙する、デバイスの請求項において、これらの手段のうちの一部は、１つの同じアイテムのハードウェアにより具現化されることもある。所定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これらの手段の組合せが有利に使用され得ないことを示すものではない。
【図１】
0006303073.tif 000246
【図２】
0006303073.tif 000247
【図３】
0006303073.tif 000248
【図４】
0006303073.tif 000249
【図５】
0006303073.tif 000250
【図６】
0006303073.tif 000251
【図７】
0006303073.tif 000252
【図８】
0006303073.tif 000253
【図９】
0006303073.tif 000254
【図１０】
0006303073.tif 000255