(57)【要約】  データ関数用に構成されるテーブルネットワークを記憶する電子記憶装置と、記憶装置に結合され、テーブルネットワークを適用することによってデータ関数を計算するように構成される電子プロセッサとを有する、関数入力値に対してデータ関数を計算するように構成される計算装置が提供され、装置はエンコードされた入力値として関数入力値を取得し、エンコードされた入力値は単一値に一緒に暗号化される状態入力値と一緒に関数入力値を組み合わせ、テーブルネットワークはエンコードされた入力値を入力とし、エンコードされた出力値を出力として生成するように構成され、エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、関数出力値はデータ関数を関数入力値に適用する結果に等しく、状態出力値は状態関数を状態入力値に適用する結果に等しい。
2016505891.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータプログラムをコンパイルするように構成されるコンパイラであって、前記コンパイラは、データ関数と状態関数を含む、複数の演算子を識別するために前記コンピュータプログラムを構文解析するように、並びに前記データ関数と前記状態関数に対して構成されるテーブルネットワークを生成するように構成され、
前記テーブルネットワークは、エンコードされた入力値を入力とし、エンコードされた出力値を出力として生成するように構成され、前記エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、前記関数出力値は前記データ関数を関数入力値に適用する結果に等しく、前記状態出力値は前記状態関数を状態入力値に適用する結果に等しく、前記エンコードされた入力値は単一値に一緒に暗号化される前記状態入力値と一緒に前記関数入力値を組み合わせる、コンパイラ。
【請求項２】
請求項１に記載のコンパイラによってコンパイルされるコンピュータプログラムを実行するように構成される計算装置であって、前記装置は、データ関数と状態関数に対して構成される、前記コンパイラによって生成されるテーブルネットワークを記憶する電子記憶装置と、前記記憶装置に結合され、前記テーブルネットワークを適用することによって前記データ関数と前記状態関数を計算するように構成される電子プロセッサとを有し、
前記装置が、エンコードされた入力値として関数入力値を取得するように構成され、前記エンコードされた入力値は単一値に一緒に暗号化される状態入力値と一緒に前記関数入力値を組み合わせ、
前記テーブルネットワークが、前記エンコードされた入力値を入力とし、エンコードされた出力値を出力として生成するように構成され、前記エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、前記関数出力値は前記データ関数を前記関数入力値に適用する結果に等しく、前記状態出力値は前記状態関数を前記状態入力値に適用する結果に等しい、
計算装置。
【請求項３】
前記テーブルネットワーク入力の現在のエンコーディングに依存して前記テーブルネットワークの前記状態関数若しくは前記データ関数を使用するように構成される、請求項２に記載の計算装置。
【請求項４】
前記エンコードされた入力値が、第一のエンコーディング（Ｅ）に従って単一値に一緒に暗号化される前記関数入力値と前記状態入力値を組み合わせ、
前記テーブルネットワークが関数入力値と状態入力値を追加のエンコードされた入力値として取得するように構成され、前記追加のエンコードされた入力値は、第二のエンコーディング
2016505891.tif 000024
に従って単一値に一緒に暗号化される前記状態入力値と一緒に前記関数入力値を組み合わせ、
前記テーブルネットワークが前記追加のエンコードされた入力値を入力とし、追加のエンコードされた出力値を出力として生成するように構成され、前記追加のエンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、前記関数出力値は前記状態関数を前記関数入力値に適用する結果に等しく、前記状態出力値は前記データ関数を前記状態入力値に適用する結果に等しい、
請求項３に記載の計算装置。
【請求項５】
前記第一のエンコーディングが第一のエンコーディング関数Ｅ（ｘ，ｙ）によって定義され、ｘは関数入力をあらわし、ｙは状態入力をあらわし、前記第二のエンコーディングが
2016505891.tif 000025
によって定義される第二のエンコーディング関数によって定義される、
請求項４に記載の計算装置。
【請求項６】
前記第二のエンコーディング
2016505891.tif 000026
の写像の合成
2016505891.tif 000027
及び前記第一のエンコーディング（Ｅ）の逆元で前記テーブルネットワークの入力と出力を前処理及び後処理するように構成される、請求項４に記載の計算装置。
【請求項７】
前記テーブルネットワークが、前記エンコードされた入力値を入力とし、前記エンコードされた出力値を出力として生成する単一テーブルを有する、請求項２に記載の計算装置。
【請求項８】
前記テーブルネットワークが、
前記エンコードされた入力値に適用される状態エクストラクタテーブルが前記状態入力値を生じるように構成される、状態エクストラクタテーブルと、
前記状態入力値に適用される状態関数テーブルが前記状態出力値を生じるように構成される、状態関数テーブルと
を有する、請求項２に記載の計算装置。
【請求項９】
前記テーブルネットワークが、
前記エンコードされた入力値と前記状態出力値を入力として受信し、再コード化された入力値を出力として生成するように構成される再エンコーディングテーブルを有し、前記再コード化された入力値が、単一値に一緒に暗号化される前記状態出力値と一緒に前記関数入力値を組み合わせる、請求項８に記載の計算装置。
【請求項１０】
前記テーブルネットワークが、前記再コード化された入力値を入力として、前記エンコードされた出力値を出力として受信するように構成されるデータ関数テーブルを有する、請求項９に記載の計算装置。
【請求項１１】
前記テーブルネットワークが、
前記状態入力値を受信し、前記状態入力値に適用される縮小された状態関数の結果に等しい中間状態値を出力として生成するように構成される、縮小された状態関数テーブルを有し、前記縮小された状態関数の値域が単一値よりも大きく、前記状態関数の値域よりも小さく、前記エンコードされた入力値が前記中間状態値に依存して再コード化される、請求項８に記載の計算装置。
【請求項１２】
前記テーブルネットワークが、
前記エンコードされた入力値と前記中間状態値を入力として受信し、再コード化された入力値を出力として生成するように構成される第一の再エンコーディングテーブルであって、前記再コード化された入力値が単一値に一緒に暗号化される前記中間状態値と一緒に前記関数入力値を組み合わせる、第一の再エンコーディングテーブルと、
前記再コード化された入力値を入力として、再コード化された出力値を出力として受信するように構成されるデータ関数テーブルであって、前記再コード化された出力値が単一値に一緒に暗号化される前記中間状態値と一緒に前記関数出力値を組み合わせる、データ関数テーブルと、
前記再コード化された出力値と前記状態出力値を入力として受信し、前記エンコードされた出力値を出力として生成するように構成される第二の再エンコーディングテーブルとを有する、請求項１１に記載の計算装置。
【請求項１３】
前記テーブルネットワークが、
前記エンコードされた入力値と前記中間状態値を入力として受信し、再コード化された入力値を出力として生成するように構成される第一の再エンコーディングテーブルであって、前記再コード化された入力値が再エンコードされた関数入力であり、前記再エンコーディングが前記中間状態値に依存して選択される、第一の再エンコーディングテーブルと、
前記再コード化された入力値と縮小された状態値を入力として、エンコードされた形で前記関数出力値を出力として受信するように構成されるデータ関数テーブルと、
エンコードされた形の前記関数出力値と前記状態出力値を入力として受信し、前記エンコードされた出力値を出力として生成するように構成される第二の再エンコーディングテーブルとを有する、
請求項１１に記載の計算装置。
【請求項１４】
前記テーブルネットワークが、
前記エンコードされた入力値と前記状態出力値を入力として受信し、再コード化された入力値を出力として生成するように構成される第一の再エンコーディングテーブルを有し、前記再コード化された入力値が再エンコードされた関数入力であり、前記再エンコーディングが前記状態出力値に依存して選択される、請求項２から１３のいずれか一項に記載の計算装置。
【請求項１５】
前記テーブルネットワークが少なくとも４、好適には少なくとも８ビットを持つ関数入力値に対して構成される、請求項２から１４のいずれか一項に記載の計算装置。
【請求項１６】
前記テーブルネットワークが少なくとも４、好適には少なくとも８ビットを持つ状態入力値に対して構成される、請求項２から１５のいずれか一項に記載の計算装置。
【請求項１７】
関数入力値と状態入力値が同じビットサイズを持つ、請求項２から１６のいずれか一項に記載の計算装置。
【請求項１８】
請求項１に記載のコンパイラによってコンパイルされるコンピュータプログラムを実行するための方法であって、前記コンパイラによって生成されるテーブルネットワークをエンコードされた入力値に適用することによってデータ関数と状態関数を計算するステップと、エンコードされた出力値を出力として生成するステップとを有し、前記エンコードされた入力値は単一値に一緒に暗号化される状態入力値と一緒に関数入力値を組み合わせ、前記エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、前記関数出力値は前記データ関数を前記関数入力値に適用する結果に等しく、前記状態出力値は前記状態関数を前記状態入力値に適用する結果に等しい、方法。
【請求項１９】
コンピュータ上で実行されるときに請求項１又は１８に記載の全ステップを実行するように構成されるコンピュータプログラムコード手段を有するコンピュータプログラム。
【請求項２０】
コンピュータ可読媒体上に具体化される請求項１９に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関数入力値に対するデータ関数を計算するように構成される計算装置に関し、当該装置はデータ関数用に構成されるテーブルネットワークを記憶する電子記憶装置と、テーブルネットワークを適用することによってデータ関数を計算するように構成される、記憶装置に結合される電子プロセッサとを有し、装置は関数入力値をエンコードされた入力値として取得するように構成され、テーブルネットワークはエンコードされた入力値を入力値とし、エンコードされた出力値を出力として生成し、エンコードされた関数出力値、関数出力値は、データ関数を関数入力値に適用する結果に等しい。
【０００２】
本発明はさらに対応する方法及びコンパイラに関する。
【背景技術】
【０００３】
ＵＳ２０１２／０３００９２２は複数の入力データと出力データをテーブルに記憶することを有する、暗号処理法で使用するのに適した対応表を生成するための方法を開示し、各入力データはテーブル内の少なくとも一つの出力データと関連する。各入力データについて、出力データの少なくとも一つは、第一の補助データに、及び入力データに依存する暗号化中間データにコーディング関数を適用することによって取得される。
【０００４】
ＵＳ２０１２／０１５５６３８は、ブロック暗号などのコンピュータ対応暗号法の分野において、暗号鍵を保護することによって、メッセージを暗号化若しくは暗号解読するために一つの鍵を使用する前に所定の線形置換をそれに適用することによって、暗号が攻撃に対して強化されることを開示する。これは、攻撃者がアルゴリズムの実行中の内部状態を含む暗号アルゴリズムにフルアクセスできる"ホワイトボックス"環境において特に有利である。この方法及び関連する計算装置は、鍵が処理を通じて導き出され、そのため暗号を具現化するソフトウェアコードがコンパイルされるときにはわからない場合、有用である。これは典型的には暗号の多くユーザがいて各々がその独自の鍵を持つ場合、又は各ユーザセッションがその独自の鍵を持つ場合に当てはまる。
【０００５】
従来の暗号法では、典型的には攻撃者が安全なシステムの入出力値へのアクセスを得るだけであると仮定された。例えば、攻撃者はシステムに入る平文を観察し、システムから出てくる暗号文を観察することができる可能性がある。攻撃者は場合により計算機負荷の重い方法すら用いて、このような入力／出力ペアを解析することによって利益を得ようとし得るが、攻撃者が入力／出力挙動を実装したシステムに直接アクセスできるとは考えられていなかった。
【０００６】
近年、攻撃者が実装の何らかの知識を持つと仮定される脅威モデルを考慮することが必要になっている。例えば、サイドチャネル解析及びリバースエンジニアリングの脅威を考慮し得る。さらに、以前はセキュリティ問題と主に関連していた懸念は、プライバシーなどの他の分野に拡張している。暗号鍵などのセキュリティ情報を処理する暗号システムは今なお一番の関心事であるが、他のプログラム、例えばプライバシー関連情報を処理するものの保護も重要になっている。
【０００７】
コンピュータシステムはいわゆるサイドチャネルを通じて一部の情報をリークすることが長い間知られている。コンピュータシステムの入力‐出力挙動を観察することは、コンピュータシステムによって使用される秘密鍵など、機密情報についてのいかなる有用な情報も与えない。しかしながらコンピュータシステムは観察され得る他のチャネル、例えばその電力消費若しくは電磁放射を持ち、これらのチャネルはサイドチャネルとよばれる。例えば、異なる命令によって消費される電力のわずかな変動及び命令を実行する間に消費される電力の変動が測定され得る。測定される変動は暗号鍵などの機密情報に関連付けられ得る。観察可能な意図された入力‐出力挙動を超えた、機密情報についてのこの追加情報は、サイドチャネルとよばれる。サイドチャネルを通じて、コンピュータシステムはその使用中に秘密情報を'リーク'し得る。サイドチャネルを観察し解析することは、入力‐出力挙動の暗号解析のみから得られ得る以上の情報へのアクセスを攻撃者に与える可能性がある。サイドチャネル攻撃の一つの既知のタイプは差分電力解析（ＤＰＡ）とよばれるものである。
【０００８】
サイドチャネル問題への現在のアプローチは計算にランダム性を導入する。例えば、電力消費とプログラムが作用しているデータとの関係を曖昧にするために、プログラムを実行する実際のオペレーションの間にダミー命令が挿入され得る。
【０００９】
コンピュータへのさらに強力な攻撃はリバースエンジニアリングとよばれる。多くのセキュリティシナリオにおいて攻撃者はコンピュータにフルアクセスできる可能性がある。これはプログラムを分解し、コンピュータとプログラムについての何らかの情報を取得する機会を攻撃者に与える。十分な努力を仮定して、例えばプログラムにおいて隠されたいかなる鍵も、攻撃者によって見つけられる可能性がある。
【００１０】
この攻撃シナリオに対する保護は非常に困難であることがわかっている。対抗手段の一つのタイプはホワイトボックス暗号法とよばれる。ホワイトボックス暗号法では、鍵とアルゴリズムが組み合わされる。得られるアルゴリズムは一つの特定鍵にのみ有効である。次にアルゴリズムはいわゆるルックアップテーブルネットワークとして実装され得る。計算は鍵依存テーブル内の一連のルックアップに変換される。このアプローチの一例として例えばＳ．Ｃｈｏｗ，Ｐ．Ｅｉｓｅｎ，Ｈ．Ｊｏｈｎｓｏｎ，Ｐ．Ｃ．ｖａｎ  Ｏｏｒｓｃｈｏｔによる"Ｗｈｉｔｅ‐Ｂｏｘ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ａｎ  ＡＥＳ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ"を参照のこと。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
コンピュータシステムに対する既知の対抗手段は全く申し分のないものではない。例えば、ランダム性の導入は統計解析によって反撃され得る。ソフトウェアの難読化はプログラムのオペレーションのより高度な解析によって反撃され得る。従ってより多くのより良い対抗手段が必要である。
【００１２】
例えば、コンピュータプログラムを難読化する一つの方法は、入力値をエンコードし、可能な限りエンコードされた値に作用することである。計算を実行するためにいわゆるテーブルネットワークも使用してもよい。このようなテーブルネットワークは手動で、若しくは例えばホワイトボックス暗号法の場合、特殊プログラムによって、若しくは汎用コンパイラによって、作られ得る。一般的に言えば、テーブルは実行されるオペレーションのタイプを難読化すると信じられていた。しかしながら、本発明者らは後者が一般的に真実でないことを発見した。関数の（複数の）入力と（複数の）出力がエンコードされる場合でも、入力／出力関係の統計的特性は、どの関数がエンコードされているかを明らかにし得る。この現象の一例は以下の通りである。
【００１３】
Ｗ＝｛０，１，…，Ｎ−１｝、エンコーディングＥ、及びその対応するデコーディングＤ＝Ｅ−１を考える。ＦとＧはそれぞれエンコードされたモジュロＮ加算及びエンコードされたモジュロＮ乗算をあらわすとする。つまり、
2016505891.tif 000003
としてＦ：Ｗ×Ｗ→Ｗを定義し、
2016505891.tif 000004
はモジュロＮ加算をあらわし、Ｇ（ｘ，ｙ）＝Ｅ（Ｄ（ｘ）＊ＮＤ（ｙ））としてＧ：Ｗ×Ｗ→Ｗを定義し、＊ＮはモジュロＮ乗算をあらわす。
【００１４】
各固定ｘについて、｛Ｆ（ｘ，ｙ）｜ｙ∈Ｗ｝＝Ｗとする。また、各非ゼロのｘ∈Ｗ及びＮプライムについて、｛Ｇ（ｘ，ｙ）｜ｙ∈Ｗ｝＝Ｗ及び｛Ｇ（０，ｙ）｜ｙ∈Ｗ｝＝Ｅ（０）とする。Ｎ非プライムについて同様のパターンが生じる。
【００１５】
結果として、エンコーディングＥから独立して、ＦがエンコードされたモジュロＮ乗算になり得ず、ＧがエンコードされたモジュロＮ加算になり得ないことを決定することができる。攻撃者はそうするための少なくとも二つの方法を持つ。攻撃者はＷにおいて二つの異なる要素ｘ１及びｘ２を固定し、Ｈ∈｛Ｆ，Ｇ｝について、Ｈ（ｘ１，ｙ）とＨ（ｘ２，ｙ）を全てのｙについて比較し得る。これらの量が全てのｙについて等しい（ｅｑｕａｌ）場合、ＨはモジュロＮ乗算をあらわすことができず、これらの量が全てのｙについて一致する（ａｇｒｅｅ）場合、ＨはモジュロＮ加算をあらわすことができない。どのテーブルエントリを読むべきかを選ぶことができないが、実行中のソフトウェアプログラムのテーブルアクセスの結果を観察することができる攻撃者は、Ｗの各要素が出力として等しく頻繁に生じる一方、Ｇでは、要素Ｅ（０）がさらにもっと頻繁に出力として生じるという事実を使用し得る。そのためＷの要素がＨの出力としてＷの他の要素よりももっと頻繁に生じる場合、Ｈは難読化されたモジュロＮ加算よりも難読化されたモジュロＮ乗算である可能性が高い。
【００１６】
言い換えれば、利用可能な最良のソフトウェア難読化法の一つを使用する場合、すなわち計算のための入出力値とテーブルネットワークのフルエンコーディングを使用する場合、それでも一部の情報がプログラムの検査によって取得される可能性がある。この状況は極めて望ましくない。
【課題を解決するための手段】
【００１７】
上記で論じた問題の一部に対処する装置若しくは方法を持つことが有益であり得る。本発明は独立クレームによって定義される。従属クレームは有利な実施形態を定義する。
【００１８】
本発明の第一の態様は、コンピュータプログラムをコンパイルするように構成されるコンパイラに関し、コンパイラは、データ関数（ｆ）と状態関数（ｇ）を含む、複数の演算子を識別するためにコンピュータプログラムを構文解析するように、及びデータ関数と状態関数に対して構成されるテーブルネットワークを作成するように構成され、テーブルネットワークはエンコードされた入力値を入力とし、エンコードされた出力値を出力として生成し、エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、関数出力値はデータ関数を関数入力値に適用する結果に等しく、状態出力値は状態関数を状態入力値に適用する結果に等しく、エンコードされた入力値は単一値に一緒に暗号化される状態入力値と一緒に関数入力値を組み合わせる。
【００１９】
また、このようなコンパイラによってコンパイルされるコンピュータプログラムを実行するように構成される計算装置が提供される。計算装置はデータ関数用に構成されるテーブルネットワークを記憶する電子記憶装置と、記憶装置に結合され、テーブルネットワークを適用することによってデータ関数を計算するように構成される電子プロセッサとを有する。
【００２０】
装置はエンコードされた入力値として関数入力値を取得するように構成され、エンコードされた入力値は単一値に一緒に暗号化される状態入力値と一緒に関数入力値を組み合わせる。テーブルネットワークはさらにエンコードされた入力値を入力とし、エンコードされた出力値を出力として生成し、エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、関数出力値はデータ関数を関数入力値に適用する結果に等しく、状態出力値は状態関数を状態入力値に適用する結果に等しい。
【００２１】
関数入力値をエンコードされた入力値として取得することは、装置が、その中で別の値と一緒にエンコードされるエンコードされた入力値を受信するので、関数入力を受信することを意味する。
【００２２】
装置は二つの関数を計算する：関数入力値を入力とし、関数出力値を生成するデータ関数、及び状態入力値を入力とし、状態出力値を生成する状態関数。しかしながら、二つの、場合により異なる関数は独立した入力値に対して計算され、各々独立した出力値を生成するが、ただ一つのテーブルネットワークが必要とされる。一つのテーブルネットワークは、関数入力値と状態入力値の両方が暗号化される単一のエンコードされた入力値を受け取る。状態入力値は少なくとも二つの異なる値を得ることができる。
【００２３】
二つの関数を、関数入力値が複数の状態値のうちの一つと一緒にエンコードされる単一のテーブルネットワークにおいて実装することは、関数入力値が複数の異なるエンコードされた入力値に対応するという利点を持つ。これは、入力値と中間値の間の対応をリストすることに基づく攻撃が阻止されることを意味する。加えてデータ関数と状態関数が独立である、すなわち状態関数が（場合により複数の）関数入力のいずれにも依存せず、データ関数が（場合により複数の）状態入力のいずれにも依存しないことが利点である。これは同じテーブルネットワークが異なるときに異なる関数のために使用され；異なる関数に同時に使用され；又は一つに使用されるが他には使用されないことを意味する。さらにこれら三つのオプションは異なるテーブルネットワークのための同じプログラムにおいて使用され得る。これはリバースエンジニアリングの困難さを大幅に増す。実際、情報理論的視点からも、二つの異なる関数をエンコードするテーブルネットワークを持つことは、ネットワークが実際には二つに対して構成され、そのいずれも使用されるか若しくは使用されない可能性があるので、どの関数に対してこれが使用されるかをネットワーク自体から判断することを不可能にする。従って攻撃者は同時にプログラムのもっと大部分を解析することを強いられる。
【００２４】
暗号（"Ｅ"とあらわされることが多い）は可逆的であり、つまり関数入力値と状態入力値のエンコードされたペアから、関数入力値と状態入力値の両方が回復され得る。同様に、関数出力値と状態出力値のエンコードされたペアから、関数出力値と状態出力値の両方が回復され得る。
【００２５】
暗号化はプライベートであり、つまりシステムの異なる実装は入力若しくは出力値を一緒に暗号化する異なる方法を使用し得る。さらに、暗号化は少なくとも一部は拡散の原理を守る。エンコードされた値における値はエンコードされた値の大部分に依存する。例えば、入力／出力値がエンコードされた入力／出力値から回復されるとき、入力／出力値は好適にはエンコードされた入力／出力値の全てに依存し、少なくともこれは入力／出力値自体のビットサイズよりも多くのビットに依存する。これは入力／出力値についての情報が多くのビットにわたって分散されるという効果を持つ。好適には、エンコードされた値の一部のみにアクセスする場合、エンコーディング／デコーディング関数の完全な知識を持っていたとしても、それがエンコードする値を回復することは不可能である。従来、暗号化は高い頻度で鍵を利用することが留意される。有鍵エンコーディングを用いることは魅力的な可能性であるが、入力／出力値の比較的小さいサイズのために、エンコーディングをテーブルとしてあらわすことも可能である。このため、入力／出力値若しくは中間値など、変数値のコンテキストにおいてエンコーディングと暗号化は相互交換可能に使用される。
【００２６】
テーブルネットワークは二つの関数をあらわし、実際エンコードされた入力値は二つの入力（関数及び状態）を含むので、これがデータ関数若しくは状態関数のエンコードバージョンであるかどうかをテーブルネットワークから知ることは不可能である。実際、テーブルネットワークはいずれかの関数を計算するように完全に装備され、実際には独立変数若しくは変数の集合（複数の入力を持つデータ関数及び／又は状態関数の実施形態において）に対して両方の関数を計算する。
【００２７】
例えば、上記実施例に適用されて、加算と乗算を実行するために使用されることができるテーブルネットワークを取得し得る。実際にテーブルネットワークはいずれか一つを実行し得るので、テーブルネットワークの検査によってどれが使用されるかを知ることはできない。
【００２８】
データ関数は一つの若しくは複数の入力値をとり得る。状態関数は一つの若しくは複数の入力値をとり得る。一実施形態において、データ及び状態関数の入力値の数は同じである。例えば、装置は複数のエンコードされた入力値として複数の関数入力値を取得するように構成され得る。複数のエンコードされた入力値の各々は、単一値に一緒に暗号化される複数の状態入力値の状態入力値と一緒に、複数の入力値の関数入力値を組み合わせる。テーブルネットワークは複数のエンコードされた入力値を入力とし、エンコードされた出力値を出力として生成するように構成される。エンコードされた出力値は単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせる。関数出力値は、データ関数を複数の関数入力値に適用する結果に等しく、状態出力値は状態関数を複数の状態入力値に適用する結果に等しい。
【００２９】
このようなテーブルネットワークを生成する複数の異なる方法が以下に示される。関数出力値を含む、関数入力値に等しい若しくはそれに依存する任意の中間値は、エンコードされた形でのみ生じる、すなわち状態変数と一緒に暗号化される。理想的には、この特性は状態入力変数にも当てはまるが、利用可能なリソースに対する競争的需要を満たすためにこの時点では譲歩することが必要になり得る。例えば、この特性を持つ一つの方法は、エンコードされた入力値を入力としエンコードされた出力値を出力として生成する単一テーブルを有するテーブルネットワークを作ることである。
【００３０】
状態計算をある程度まで分離することが可能であり、例えばテーブルネットワークは状態エクストラクタテーブルと状態関数テーブルとを有し得る。状態エクストラクタテーブルは、エンコードされた入力値に適用される状態エクストラクタテーブルが状態入力値を生成するように構成される。状態関数テーブルは、状態入力値に適用される状態関数テーブルが状態出力値を生成するように構成される。状態値がテーブルネットワークにおいて取得されるとしても、関数入力値はエンコードされたままであることが留意される。また状態エクストラクタテーブルは、エンコードされた形で、ただし入力値に、例えば状態値のみを暗号化することによって取得可能なエンコードされた状態値に依存しない、エンコードされた形で、状態値を生成し得ることも留意される。
【００３１】
一旦状態出力値が、場合によりエンコードされた形で、利用可能になると、再エンコーディングテーブルを使用し得る。再エンコーディングテーブルはエンコードされた値を入力とし、エンコードされた値を生成するが、エンコーディングは変わっている。例えば、再エンコーディングテーブルはエンコードされた入力値と状態出力値を入力として受信し、再コード化された入力値を出力として生成するように構成され得る。再コード化された入力値は、単一値に一緒に暗号化される状態出力値と一緒に関数入力値を組み合わせる。エンコードされた出力値を取得するためにデータ関数テーブルが再コード化された入力値に適用され得る。例えば、データ関数テーブルは再コード化された入力値を入力として、エンコードされた出力値を出力として受信するように構成され得る。
【００３２】
これは必要なテーブルのサイズを縮小する。それにもかかわらずテーブルネットワークが二つの関数：データ関数と状態関数を計算するということは依然として事実のままである。攻撃者はどの関数にテーブルネットワークが使用されるかを知ることができない。さらに、入力値と一緒にエンコードされない形で状態値が生じるとしても、入力値はエンコードされた形でのみ生じる。
【００３３】
テーブルのサイズをさらにもっと縮小することが可能である。例えば、テーブルネットワークは縮小された状態関数テーブルと第一の再エンコーディングテーブルを有し得る。縮小された状態関数テーブルは状態入力値を受信するように、及び状態入力値に適用される縮小された状態関数の結果に等しい中間状態値を出力として生じるように構成され、縮小された状態関数の値域（ｒａｎｇｅ）は単一値よりも大きく、状態関数の値域よりも小さい。第一の再エンコーディングテーブルは、エンコードされた入力値と中間状態値を入力として受信し、再コード化された入力値を出力として生成するように構成され、再コード化された入力値は単一値に一緒に暗号化される中間状態値と一緒に関数入力値を組み合わせる。
【００３４】
テーブルネットワークはこのように三つの関数、状態関数、縮小された状態関数、及びデータ関数を計算する。縮小された状態関数は状態関数よりも小さい値域を持つので、データ関数用のテーブルが縮小される。各入力データ値が縮小された状態空間でも１より多くの代表元（ｒｅｐｒｅｓｅｎｔａｔｉｖｅ）を持つように、縮小された状態関数の値域は１より大きいサイズを持つことが留意される。一実施形態において、縮小された状態空間のサイズ、すなわち値の数は、少なくとも２、４若しくは８である。
【００３５】
例えば、テーブルネットワークはデータ関数テーブルと第二の再エンコーディングテーブルを有し得る。データ関数テーブルは再コード化された入力値を入力として、再コード化された出力値を出力として受信するように構成され、再コード化された出力値は単一値に一緒に暗号化される中間状態値と一緒に関数出力値を組み合わせる。第二の再エンコーディングテーブルは再コード化された出力値と状態出力値を入力として受信し、エンコードされた出力値を出力として生成するように構成される。
【００３６】
一実施形態において、テーブルネットワークは少なくとも４、好適には少なくとも８ビットを持つデータ入力値に対して構成される。一実施形態において、テーブルネットワークは少なくとも４、好適には少なくとも８ビットを持つ状態入力値に対して構成される。
【００３７】
一実施形態において、データ入力値と状態入力値は同じビットサイズを持つ。データ関数と状態関数が等しい入力サイズを持つ場合、これらはこの面では区別できない。一実施形態において、データ出力値と状態出力値は同じビットサイズを持つ。
【００３８】
一実施形態において、データ入力値と状態値は同じビットサイズを持ち、４ビット以上を持つ。一実施形態において、データ入力値と状態値は同じビットサイズを持ち、６ビット以上を持つ。一実施形態において、データ入力値と状態値は同じビットサイズを持ち、８ビット以上を持つ。
【００３９】
本発明の一態様は、本発明の第一の態様にかかるコンパイラによってコンパイルされるコンピュータプログラムを実行するための方法に関し、方法は、エンコードされた入力値にテーブルネットワークを適用することによってデータ関数を計算するステップと、エンコードされた出力値を出力値として生成するステップとを有し、エンコードされた入力値は、単一値に一緒に暗号化される状態入力値と一緒に関数入力値を組み合わせ、エンコードされた出力値は、単一値に一緒に暗号化される状態出力値と一緒に関数出力値を組み合わせ、関数出力値はデータ関数を関数入力値に適用する結果に等しく、状態出力値は状態関数を状態入力値に適用する結果に等しい。
【００４０】
計算装置は電子デバイス、例えばモバイル電子デバイス、携帯電話、セットトップボックス、コンピュータ若しくは同様のものである。
【００４１】
本発明にかかる方法はコンピュータ実装方法としてコンピュータ上で、若しくは専用ハードウェアにおいて、若しくは両者の組み合わせで実装され得る。本発明にかかる方法のための実行可能なコードはコンピュータプログラム製品上に記憶され得る。コンピュータプログラム製品の例はメモリデバイス、光学記憶デバイス、集積回路、サーバ、オンラインソフトウェアなどを含む。好適には、コンピュータプログラム製品は、当該プログラム製品がコンピュータ上で実行されるときに本発明にかかる方法を実行するためのコンピュータ可読媒体上に記憶される非一時的プログラムコード手段を有する。
【００４２】
好適な実施形態において、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行されるときに本発明にかかる方法の全ステップを実行するように構成されるコンピュータプログラムコード手段を有する。好適には、コンピュータプログラムはコンピュータ可読媒体上で具体化される。
【００４３】
本発明のこれらの及び他の態様は以降に記載の実施形態から明らかとなり、それらを参照して解明される。
【図面の簡単な説明】
【００４４】
【図１】データ関数と状態関数を実装するテーブルネットワークを例示するチャート図である。
【図２】データ関数と状態関数を実装するテーブルネットワークを例示するチャート図である。
【図３ａ】データ関数と状態関数を実装するテーブルネットワークを例示するチャート図である。
【図３ｂ】データ関数と状態関数を実装するテーブルネットワークを例示するチャート図である。
【図３ｃ】データ関数と状態関数を実装するテーブルネットワークを例示するチャート図である。
【図４】概してテーブルネットワークを例示するブロック図である。
【図５】計算装置を例示するブロック図である。
【図６】コンパイラを例示するフローチャートである。
【図７】データ関数を計算するための方法を例示するフローチャートである。
【発明を実施するための形態】
【００４５】
異なる図中で同じ参照番号を持つ項目は同じ構造的特徴と同じ機能を持つか、又は同じ信号であることが留意されるべきである。このような項目の機能及び／又は構造が説明されている場合、詳細な説明においてその繰り返される説明の必要はない。
【００４６】
本発明は多くの異なる形の実施形態を許容するが、本開示は本発明の原理の実施例とみなされ、図示及び記載の特定の実施形態に本発明を限定することを意図しないという理解とともに、一つ以上の特定の実施形態が図示され、本明細書で詳細に記載される。
【００４７】
図中、テーブルは長方形で示され、値は右上角を切り落とした長方形で示される。
【００４８】
図４はテーブルネットワークの一般概念を例示し、テーブルネットワーク４００が示される。大部分の関数はテーブルのネットワークとして表現され得る。特に算術及び論理演算の任意の構成がそのように表現され得る。例えば、テーブルのネットワークは、例えば暗号の実装であり得る。複数のテーブルのうち８テーブルが示される。テーブルは入力値のテーブルルックアップによって入力値を出力値に変換する。関数実装の外側から入力を受信するための入力テーブル４１０のうち三つが示される。出力テーブル４３０のうち一つが示される。出力テーブル４３０は例えば連結によって関数実装の出力を一緒に形成する。テーブルのうち別のものから少なくとも一つの入力を受信し、少なくとも一つの他のテーブルのための入力として使用するための出力を生成する、中間テーブルのうち４テーブル４２０，４２２，４２４，４２６が示される。テーブルは一緒にネットワークを形成する。暗号はブロック暗号であり得、ブロック暗号は暗号化若しくは暗号解読のために構成され得る。ブロック暗号はブロック暗号、例えばＡＥＳを暗号化する。実装は特定鍵用であってもよく、この場合テーブルは特定鍵に依存し得る。
【００４９】
ルックアップテーブル４２６は二つの入力と一つの出力を持つ演算子をあらわす。単項演算子のためのルックアップテーブルの構成は二項演算子に拡張され得る。例えば、第二の入力は'カリー化'され得る；関数変換法に関して、カリー化は、ｎ個の多引数（若しくはｎ組の引数）をとる関数を、各々が単数の引数を持つ関数の連鎖とよばれることができるように変換する方法である。このアプローチが使用されるとき、ルックアップテーブル４２６は複数の単項ルックアップテーブルとして実装される。他方でまた、各入力に対するビットストリングを生成し、結果を連結してもよい。このようにルックアップテーブルは直接生成され、単一のただしより大きなルックアップテーブルが得られる。ルックアップテーブルのレイアウトは構成に基づいて異なり得るが、それらは等しいサイズと同じ特性を持つ。複数の入力値が同じエンコーディングに従ってエンコードされることは必要ないことが留意される。
【００５０】
テーブルネットワークは二つの関数をエンコードする複数のテーブルを使用し得るか、若しくは二つの関数についてエンコードするテーブルネットワークをサブネットワークとして持ち得る。システムは現在のエンコーディングに依存してネットワークテーブルのその状態若しくはデータ関数を使用するように構成され得る。テーブルネットワーク難読化技術が、本明細書に記載のテーブルネットワークにおいても適用され得る。
【００５１】
例えば、第二のテーブルが第一のテーブルの出力を入力として受信すると仮定すると、第一のテーブルの出力は秘密の、例えばランダムに選ばれるエンコーディングでエンコードされ、第二のテーブルの入力はその逆エンコーディングでエンコードされ得る。
【００５２】
図１はより大きなテーブルネットワーク１００に組み込まれるテーブルネットワーク１８０を示す。テーブルネットワーク１８０は単一テーブル１３０のみを含む。
【００５３】
テーブルネットワーク１８０は複数のエンコードされた入力値を入力とするように構成され、エンコードされた入力値１２２及び１２４が示される。テーブルネットワーク１８０はエンコードされた出力値１６０を出力として生成するように構成される。下記では二つの入力値と単一の出力値を持つデータ関数と状態関数を仮定する。しかしながら、実施形態はいかなる数の入力値及び／又は出力値にも拡張され得る。特に一つの入力と一つの出力を持つ特定のデータ／状態関数が可能であり、二つの入力と一つの出力を持つデータ／状態関数が可能である。
【００５４】
テーブルネットワーク１８０はデータ関数用に構成され、テーブルネットワークを適用することによってデータ関数を計算するように構成される電子プロセッサに結合される電子記憶装置に記憶される。
【００５５】
エンコードされた値１２２は関数入力値１０２と状態入力値１１２から得られる。例えば、これはエンコーダ１１０によってなされ得る。エンコーダ１１０はテーブルネットワーク１８０を記憶する同じ装置に含まれ得るが、これは必要ではない。入力値は既にエンコードされた形で受信され、及び／又はエンコードされた形で送信され得る。或いはそれらはエンコードされていない形で受信／送信され得る。後者の場合それらはエンコードされ、エンコードされた形で内部で使用され得る。例えば装置の外側で異なるエンコーディングが使用される場合、再エンコーディングもある可能性がある。例えば、関数出力値１６２と状態出力値１６４はデコーダ１７０から取得され得る。
【００５６】
データ関数のエンコードされた入力は別のテーブル若しくはテーブルネットワークの出力になり得る。後者は二つの関数用に構成されるテーブルネットワークであってもなくてもよい。異なるデータ関数用に構成されるテーブルネットワークを組み合わせることによってプログラム全体が構築され得る。
【００５７】
エンコーダ／デコーダ１１０及び１７０は相互の逆元として得られる。エンコーダ１１０は以下のように得られる。関数入力値と状態入力値の可能な組み合わせの各々がリストされる。例えば、両方が４ビット幅である場合、１６＊１６＝２５６の可能な組み合わせがある。２５６の組み合わせはランダムな全単射のオーダーでそれ自体に写像され得る。同じことが他のサイズにも当てはまる。暗号化関数も使用され、例えば何らかの秘密エンコーディング鍵を用いて８ビットブロック暗号が適用され得る。
【００５８】
エンコードされた入力値は関数入力値１０２と状態入力値１１２を相互依存的に含み、例えば関数入力はエンコードされた入力の全ビットに依存する。従って、エンコードされた入力値１２２の一部のみがわかっても、一般に関数入力値１０２若しくは状態入力値１１２のいずれかを見つけることはできない。
【００５９】
以下、数学的言語を使用して複数の実施形態を与える。関数入力値を状態値と組み合わせる一つの利点は、関数入力が複数の表現を持つことである。関数ｆはデータ関数を、ｇは状態関数をあらわす。関数ｆはＦの定義域（ｄｏｍａｉｎ）内の値が複数の代表元を持つようにＦにエンコードされる。どの関数ｆがエンコードされているかを隠すために、ｆの（複数の）入力と（複数の）出力はｆのエンコードバージョンＦの定義域と値域内で複数の表現を持つ。関数Ｆは、Ｘがｘの代表元であるときはいつでもＦ（Ｘ）がｆ（ｘ）の代表元であるように、設計される。その後になって、ｆからの入力／出力をあらわすよりもＦからの入力／出力をあらわすために一般により多くのビットを必要とするように、ｆの各入力／出力がＦの複数の入力／出力に対応することを強調するために"長い"変数（Ｆの入力／出力）と"短い"変数（ｆの入力／出力）について述べることがある。被演算子に対する複数の表現を得る一つの方法が以下に記載される。先と同様に、単純にするため、等しい入力及び出力記号を持つ関数を考慮し、これは一般化され得ることが留意される。
【００６０】
Ｗはエンコードしたい被演算子の集合をあらわすとする。"状態"の有限集合Σと、ＷとΣの濃度の積に等しい濃度を持つ有限集合Ｖを導入する。Ｗ×Σの要素は秘密エンコーディング関数ＥによってＶに１対１写像される。Ｗにおける要素ｗの代表元は集合Ω（ｗ）＝｛Ｅ（ｗ，σ）｜σ∈Σ｝の元（ｍｅｍｂｅｒ）である。
【００６１】
従ってＷにおける各要素の代表元の数はΣの濃度に等しい。結果として、Ｖから記号を運ぶデータパスはＷから記号を運ぶデータパスよりも広い。例えば、Ｗが１６ビット整数の集合である場合、状態空間Σは１６＝２４の要素を持ち、Ｖのためのデータパスは１６＋４＝２０ビットを使用し、一方Ｗのためのデータパスは１６ビットを使用する。
【００６２】
下記実施形態は二変数の関数をエンコードする。エンコードしたい関数ｆ：Ｗ×Ｗ→Ｗを考慮する。全てのｗ１，ｗ２∈Ｗ及びσ１，σ２∈Σについて
Ｆ（Ｅ（ｗ１，σ１），Ｅ（ｗ２，σ２））∈Ω（ｆ（ｗ１，ｗ２））
となるように関数Ｆ：Ｖ×Ｖ→Ｖを構成する。
【００６３】
すなわち、言葉でいえば：Ｆはｗ１とｗ２の代表元の任意のペアをｆ（ｗ１，ｗ２）の代表元に写像する。
【００６４】
ｆ（ｗ１，ｗ２）の代表元の状態は被演算子ｗ１及びｗ２の両方に依存し、状態σ１及びσ２の両方にも、決定論的に若しくはランダムに、依存し得る。より具体的には、状態は状態σ１とσ２のみに依存する可能性があり、これは関数ｇ：Σ×Σ→Σをとることによって、及び
Ｆ（Ｅ（ｗ１，σ１），Ｅ（ｗ２，σ２））＝Ｅ（ｆ（ｗ１，ｗ２），ｇ（σ１，σ２））
を定義することによって実装され得る。
【００６５】
上記実施形態の興味深い特殊な場合は、Σ＝Ｗをとる場合に生じる。その場合関数Ｅを用いてｆをエンコードする関数Ｆは、異なるエンコーディング関数
2016505891.tif 000005
とともにではあるが、関数ｇもエンコードする。つまり、二つの関数ｆ若しくはｇのどちらがＦによって実装されているかを推論することができない。
2016505891.tif 000006
と定義する。計算により次式がわかる。
2016505891.tif 000007
【００６６】
従ってＦに対するテーブルはエンコーディングＥが使用されている場合は関数ｆを実装し、
2016505891.tif 000008
がエンコーディング関数として使用されている場合は関数ｇを実装する。このように、テーブル１３０のみからは、これが少なくとも二つの関数についてエンコードし得るので、どの関数が使用されているかわからないことが証明される。
【００６７】
Ｆに対するテーブルはｆとｇの両方を計算するのに役立ち得る。実際、Ｅが使用される場合、前述の通り、Ｆに対するテーブルはｆを実装する。同じテーブルは関数
2016505891.tif 000009
で入力と出力を前処理及び後処理することによってｇを実装するためにも使用され得る。正確には、ｗ１，ｗ２∈Ｗ、σ１，σ２∈Σとし、νｉ＝Ｅ（ｗｉ，σｉ）、ｉ＝１，２と書く。すると
2016505891.tif 000010
を得る。
【００６８】
結果として、
2016505891.tif 000011
を得る。
【００６９】
エンコードされた入力値は、場合によりデータ関数を含むか若しくはデータ関数によってあらわされる、コンピュータプログラムへの入力値であり得る。コンピュータプログラムはコンピュータ上で実行していてもよい。コンピュータプログラムの命令はデータ関数によってあらわされ得る。エンコーディングとデコーディングは秘密鍵の制御下にあり得る。エンコーディング及びデコーディングテーブル自体がそのような鍵とみなされ得る。エンコーディングＥｋでエンコードされるデータに作用する命令ｆが適用される場合、これはまずデータをデコードし、それからｆがデコードされたデータに適用され、その後結果が再度エンコードされる。つまり、データｘは出力Ｆ（ｘ）＝Ｅｋ（ｆ（Ｄｋ（ｘ）））をもたらす。例えばルックアップテーブルとして、関数Ｆの直接記憶により、関数ｆとそのセマンティクスが隠される。特定の実施形態において、デコーディングはエンコーディングの左逆元であり、つまり全てのｘについてＤｋ（Ｅｋ（ｘ））＝ｘである。これは二つの関数ｆとｇが同じ関数ＥｋとＤｋでエンコード及びデコードされる場合、関数ｆ（ｇ（ｘ））のエンコードバージョンがＧ（ｘ）＝Ｅｋ（ｇ（Ｄｋ（ｘ））及びＦ（ｘ）＝Ｅｋ（ｆ（Ｄｋ（ｘ））に対するテーブルを連続的に用いることによってなされ得るという利点を持つ。実際、ｆ（ｇ（ｘ））のエンコードバージョンがＧとＦに対するテーブルのその後のアクセスから取得され得るように、各ｘに対してＥｋ（ｆ（ｇ（Ｄｋ（ｘ））＝Ｆ（Ｇ（ｘ））となることがわかる。このように、演算のシーケンスが連続演算間のエンコーディングとデコーディングなしに適用され得るので、セキュリティを大きく増強する。エンコーディングとデコーディングが安全な側でしか起こらない実施形態において、一方全てのエンコードされた演算はオープンな安全でない側で起こる。一つ以上のエンコードされた関数の（複数の）出力は別のエンコードされた関数への（複数の）入力となり得る。見てきた通りこれはエンコーディングとデコーディングが相互の逆元である場合に好都合に構成され得る。本発明で演算のシーケンスを実行するための好適な実施形態は以下の通りである。まず、安全な定義域で、"短い"変数が"長い"変数に変換される。"長い"変数がおおよそ等しい頻度で生じることを確実にするためにランダム化が関与する。これは例えばランダム状態σ∈Σを生成する装置を持ち、Ｅｋ（ｘ，σ）に変数ｘを写像することによって達成されることができ、Ｅｋは"長い"変数のエンコーディングである。オープンな側での全計算、"長い"変数を使用する全演算の後、デコーディングＤｋが安全な側において適用され、次に、デコードされた長い変数に対応する"短い"変数が決定される。代替的に、短い変数のデコーディングと決定は一つの複合ステップでなされる。文字ｋは秘密、例えば秘密鍵をあらわす。
【００７０】
変数に対して複数の代表元を持つことはデータパスが長くなることを示唆する。また、これはｆのエンコードバージョンＦを実装するためのテーブルが大きくなることも示唆する。例えば、二つの１６ビット変数ｘ及びｙを入力として、１６ビット変数を出力として持つ関数ｆ（ｘ，ｙ）を考える。ｆのエンコードバージョンを実装するためのテーブルは、複数の代表元を持つことなく、各テーブルエントリが１６ビット幅である２１６×２１６のエントリを持つテーブルを使用し、これは２３６ビットのテーブルサイズになる。ここで各１６ビット変数が１６の代表元を持つと仮定すると、代表元の集合は２０ビットであらわされ得る。ここで各テーブルエントリが２０ビット幅である２２０×２２０のエントリを持つテーブルを使用し、これは５×２４２ビットのテーブルサイズになる。つまり、テーブルは複数の代表元を持たない場合の５×２６＝３２０倍大きい。
【００７１】
図２はデータ及び状態表現を組み合わせることのテーブルサイズに対する影響を軽減する方法を示す。テーブルネットワーク２００は図１と同じデータ関数と同じ状態関数を計算する。
【００７２】
テーブルネットワーク２００はデータ関数用に構成され、テーブルネットワークを適用することによってデータ関数を計算するように構成される電子プロセッサに結合される電子記憶装置に記憶される。
【００７３】
テーブルネットワーク２００はエンコードされた入力値１２２及び１２４から対応する状態値１１２及び１１４を抽出するように構成される状態エクストラクタテーブル２１２及び２１４を有する。これは入力値がいつ何時でも平文形式で取得されることを示唆するわけではないことが留意される。状態値は状態関数テーブル２３０への入力として使用される。状態関数テーブル２３０は状態関数をあらわす。状態エクストラクタテーブル２１２、状態エクストラクタテーブル２１４及び状態関数テーブル２３０は、状態値に対するエンコーディングを、場合により値１１２と１１４に対して異なるエンコーディングさえ使用し得ることが留意される。しかしながら、このエンコーディングは状態値のみに依存し入力値には依存しない。エンコーディングは秘密であり、例えば特定の実装にプライベートであり得る。状態関数テーブル２３０から状態出力値２３２がわかる。
【００７４】
テーブルネットワーク２００は再エンコーディングテーブル２４２，２４４をさらに有する。これらのテーブルはエンコードされた入力値１２２及び１２４を受け入れるが、この特定の実施形態では状態出力２３２である共通状態値を持つようにそれらを再エンコードする。これはデータ関数テーブル２６０が、もはや二つの異なる状態値を受信する可能性のために構成される必要がないので、著しく単純化され得ることを意味する。図１と同じエンコードされた出力値１６０が得られることが留意される。
【００７５】
以下、数学的言語を使用して複数の実施形態を与える。ｍ被演算子の関数ｆを考慮する。第一のステップとして、少なくとも二つの被演算子が同じ状態を持つようにｆの被演算子の表現を決定し得る。利点を示すために、被演算子がｗの値を得ることができ、被演算子の各値がｓの表現を持つ場合を考える。図１のアプローチは（ｓｗ）ｍエントリを持つテーブルをもたらす。ｆの全被演算子が同じ状態に強制される場合、ｓｗｍエントリのみを持つテーブルを使用し得る。図２の一実施形態において、ｆの複数の被演算子のうち少なくとも二つの被演算子は状態空間において共通状態に強制される。
【００７６】
被演算子に対する複数の表現を得る一つの方法は以下の通りである。Ｗがエンコードしたい被演算子の集合をあらわすとする。"状態"の有限集合Σと、Ｗ及びΣの濃度の積に等しい濃度を持つ有限集合Ｖを導入する。Ｗ×Σの要素は秘密エンコーディング関数ＥによってＶに１対１写像される。Ｗにおける要素ｗの代表元は集合Ω（ｗ）＝｛Ｅ（ｗ，σ）｜σ∈Σ｝の元である。
【００７７】
従ってＷにおける各要素の代表元の数はΣの濃度に等しい。結果として、Ｖから記号を運ぶデータパスはＷから記号を運ぶデータパスよりも広い。例えば、Ｗが１６ビット整数の集合であり状態空間Σが１６＝２４要素を持つ場合、Ｖのためのデータパスは１６＋４＝２０ビットを使用し、一方Ｗのためのデータパスは１６ビットを使用する。
【００７８】
ここでエンコードしたい関数ｆ：Ｗ×Ｗ→Ｗを考える。全てのｗ１，ｗ２∈Ｗ及びσ１，σ２∈Σについて
Ｆ（Ｅ（ｗ１，σ１），Ｅ（ｗ２，σ２））∈Ω（ｆ（ｗ１，ｗ２））
となるように関数Ｆ：Ｖ×Ｖ→Ｖを構成する。
【００７９】
すなわち、言葉でいえば：Ｆはｗ１とｗ２の代表元の任意のペアをｆ（ｗ１，ｗ２）の代表元に写像する。ここで代表元の状態が状態σ１及びσ２にのみ依存する状況を考え、これは関数ｇ：Σ×Σ→Σをとることによって、及び
Ｆ（Ｅ（ｗ１，σ１）Ｅ（ｗ２，σ２））＝Ｅ（ｆ（ｗ１，ｗ２），ｇ（σ１，σ２））
を定義することによって実装され得る。
【００８０】
この関数ＦはＶから二つの入力変数を持つことに留意する。従ってＦに対するテーブルは｜Ｖ｜２エントリを持ち、各エントリはＶからの要素である。以下、テーブルサイズを著しく縮小する方法を示す。
Ｓｅ（Ｅ（ｗ，σ））＝σ
と定義される、状態エクストラクタのためのテーブルＳｅ：Ｖ→Σを用いる。
【００８１】
図２において、状態エクストラクタテーブル２１２及び２１４はこれらの状態エクストラクタ関数Ｓｅをあらわす。エンコードされた入力値１２４と異なる状態エンコーディングがエンコードされた入力値１２２において使用された可能性があることが留意される。
【００８２】
図２において２３０で実装される関数ｇを計算するためのテーブルも使用する。また、（秘密）エンコーディング
2016505891.tif 000012
並びにε１：Ｖ×Σ→Ｗ及びε２：Ｖ×Σ→Ｗを実装するためのテーブル（図２のテーブル２４２及び２４４に対応）も使用し、これらはｉ＝１，２及び全てのｗ∈Ｗ、σ，τ∈Σに対して
2016505891.tif 000013
となるようになっている。
【００８３】
最後に、全てのｗ１∈Ｗ、ｗ２∈Ｗ及びτ∈Σに対して
2016505891.tif 000014
となるように関数φ：Ｗ×Ｗ×Ｔ→Ｖを実装するためのテーブルを使用する。
【００８４】
ここで入力ν１＝Ｅ（ｗ１，σ１）及びν２＝Ｅ（ｗ２，σ２）を考える。攻撃者はν１とν２を観察することができるが、ｗ１とｗ２を観察することはできないことが留意される。以下のプログラムを実行する。
2016505891.tif 000015
【００８５】
上記最後から二番目のラインは図２のテーブル２４２、２４４、２５２及び２５４に対応する。上記最後のラインは図２のテーブル２６０に対応する。
【００８６】
ここで所要テーブルの総サイズを決定する。Ｓｅに対するテーブルは｜Ｖ｜エントリを持ち、その各々はΣ：｜Ｖ｜ｌｏｇ２｜Σ｜ビットの要素である。ｇに対するテーブルは｜Σ｜２エントリを持ち、その各々はΣ：｜Σ｜２ｌｏｇ２｜Σ｜ビットの要素である。ε１及びε２に対するテーブルは両方とも｜Ｖ｜｜Σ｜エントリを持ち、その各々はＷ：｜Ｖ｜｜Σ｜ｌｏｇ２｜Ｗ｜ビット／テーブルの要素である。φに対するテーブルは｜Ｗ｜２｜Σ｜エントリを持ち、その各々はＶ：｜Ｗ｜２｜Σ｜ｌｏｇ２｜Ｖ｜ビットの要素である。従って所要ビットの総数は
（｜Ｖ｜＋｜Σ｜２）ｌｏｇ２｜Σ｜＋２｜Ｖ｜｜Σ｜ｌｏｇ２｜Ｗ｜＋｜Ｗ｜２｜Σ｜ｌｏｇ２｜Ｖ｜
に等しい。
【００８７】
従って、｜Ｗ｜＝｜Σ｜であれば、｜Ｖ｜＝｜Ｗ｜｜Σ｜を用いて、所要ビットの数が（４｜Ｗ｜３＋２｜Ｗ｜２）ｌｏｇ２｜Ｗ｜に等しいことがわかる。図１は｜Ｖ｜２ｌｏｇ２｜Ｖ｜＝２｜Ｗ｜４ｌｏｇ２｜Ｗ｜ビットを使用する。従ってこの実施例では、ほとんど｜Ｗ｜／２の係数でテーブルサイズが縮小される。
【００８８】
図３ａはどのようにテーブルサイズとセキュリティがトレードオフで交換され得るかを示す。図２の状態関数テーブル３２３０に加えて、テーブルネットワーク３００は縮小された状態関数テーブル３１０を有する。縮小された状態関数テーブル３１０は状態関数テーブル２３０と異なる関数を状態入力値１１２及び１１４に対して計算する。実際、縮小された状態関数テーブル３１０は、縮小された状態関数テーブル３１０が状態関数テーブル２３０よりも小さい値域を持つことを除き、１１２及び１１４に対して任意の関数、例えばランダム関数を計算し得る。つまり、縮小された状態関数テーブル３１０の可能な出力値の数は状態関数テーブル２３０の可能な出力値の数よりも小さい。縮小された状態関数テーブル３１０は縮小された状態値３２０を生成する。例えば、状態出力値２３２は４ビットであり縮小された状態出力値は２ビットであり得る。単純化するために、状態出力値２３２のビットから値３２０のビットを選択してもよいが、好適には、テーブル３１０及び２３０は別個であり相関せず、特に非線形的である。
【００８９】
入力値を状態出力値に再エンコードする代わりに、テーブルネットワーク３００は縮小された状態値３２０に再エンコードする。テーブルネットワーク３００は、それぞれエンコードされた入力値１２２と１２４を入力として受け入れ、状態出力値１６４の代わりに縮小された状態値３２０についてエンコードされた新たなエンコード値を生成するように構成される再エンコーディングテーブル３３２及び３３４を有する。結果はそれぞれ再コード化された入力値３４２，３４４である。従って再コード化された入力値３４２は、エンコードされた入力１２２におけるその関数入力値を、単一値に一緒に暗号化される縮小された状態値３２０（状態入力値１１２の代わりに）と組み合わせる；同じことは再コード化された入力値３４４に当てはまる。
【００９０】
最終的に、データ関数テーブル３５０は、状態値の縮小された値域を受け入れることを除いて類似データ関数テーブル２６０である。入力値について計算される関数はデータ関数に対応し、状態関数についての関数はいかなるものでも、例えばランダム若しくは恒等関数であり得る。最後に、エンコードされた出力値が関数出力値１６２だけでなく状態出力値１６４にも対応するように、結果が再エンコーディングテーブル３６０で再エンコードされる。再エンコーディングテーブル３３２及び再エンコーディングテーブル３３４は第一の再エンコーディングテーブルともよばれる。再エンコーディングテーブル３６０は第二の再エンコーディングテーブル３６０ともよばれる。再コード化された入力３４２及び再コード化された入力３４４はともに縮小された状態を含むことが留意され、これはテーブル３５０の入力の一部が重複することを意味し、結果としてテーブルはスパースになり、従って例えばデータ圧縮が適用される場合うまく圧縮し得る。
【００９１】
例えば関数値と状態値が各々４ビット幅であり、縮小された状態値が２ビット幅である場合、再エンコーディングテーブル３３２／３３４は４＋４＋２＝１０ビットを入力として、６ビットを出力として持ち、データ関数テーブル３５０は６＋６＝１２ビットを入力として持つ。テーブル３５０がエンコードされた入力／出力値として同じサイズの出力値を生成する場合、これは４＋４＝８ビットの出力を持ち、状態値が縮小される場合、これは６ビットの出力を持ち、出力が（場合によりエンコードされる）関数出力値のみを持つ場合、これは４ビットの出力を持つ。ビット幅４及び２など、実証する値は様々であり得る。
【００９２】
テーブルネットワーク３００はデータ関数用に構成され、テーブルネットワークを適用することによってデータ関数を計算するように構成される電子プロセッサに結合される電子記憶装置に記憶される。
【００９３】
図３ｂはどのように異なる方法でテーブルサイズとセキュリティがトレードオフで交換され得るかを示す。図３ａと同様に、テーブルネットワーク３００は縮小された状態関数テーブル３１０を有する。しかしながら図３ｂは再エンコーディングテーブル３３２と３３４を含まない。代わりに、状態依存再エンコーディングテーブル３７２と３７４が使用される。
【００９４】
状態依存再エンコーディングテーブル３７２はエンコードされた入力値１２２を入力とし、これは関数入力値と状態入力値を、ただしエンコード（暗号化）された形で組み合わせる。状態依存再エンコーディングテーブル３７２は異なる方法で関数入力を抽出してエンコードし、再エンコーディングは縮小された状態値３２０に依存する。異なる言い方では、エンコードされた入力値１２２における関数入力は鍵として縮小された状態値３２０で暗号化される。状態依存再エンコーディングテーブル３７４は同じことを、ただしエンコードされた入力値１２４にする。テーブル３７２及び３７４の結果は再コード化された入力値３８２及び３８４である。
【００９５】
例えば関数値と状態値が各々４ビット幅であり、縮小された状態値が２ビット幅である場合、再エンコーディングテーブル３７２／３７４は４＋４＋２＝１０ビットを入力として、４ビットを出力として持ち、データ関数テーブル３８５は４＋４＋２＝１０ビットを入力として持つ。テーブル３８５が同じサイズの出力値をエンコードされた入力／出力値として生成する場合、これは４＋４＝８ビットの出力を持ち、状態値が縮小される場合、これは６ビットの出力を持ち、出力が（場合によりエンコードされる）関数出力値のみを持つ場合、これは４ビットの出力を持つ。ビット幅４及び２など、実証する値は様々であり得る。
【００９６】
以下、数学的言語を使用して複数の実施形態を与える。実施形態は、関数ｆをあまりうまく隠さないという潜在的犠牲のもとに所要テーブルのサイズのさらなる縮小を可能にする。
【００９７】
Ｓｅ（Ｅ（ｗ，σ））＝σと定義される状態エクストラクタ関数に対するテーブルＳｅ：Ｖ→Σを使用し、テーブルは｜Ｖ｜エントリを持ち、その各々はΣの要素であり、従ってこれは｜Ｖ｜ｌｏｇ２｜Σ｜ビットを使用する。これは図３のテーブル２１２及び２１４である。同様に、ｇを実装するためのテーブルは｜Σ｜２ｌｏｇ２｜Σ｜ビットを持ち、これは図３のテーブル２３０である。次に、"内部状態空間"Ｔと、写像ｔ：Σ×Σ→Ｔに対するテーブルを使用する。ｔに対するテーブルは｜Σ｜２ｌｏｇ２｜Ｔ｜ビットを使用し、これは図３のテーブル３１０である。
【００９８】
また、（秘密）エンコーディング
2016505891.tif 000016
も使用する。さらに、ｉ＝１，２及び全てのｗ∈Ｗ、σ∈Σ及びτ∈Ｔについて、
2016505891.tif 000017
となるような、関数ε１：Ｖ×Ｔ→Ｗ及びε２：Ｖ×Ｔ→Ｗを実装するためのテーブルを使用する。テーブルは各εｉについて｜Ｖ｜｜Ｔ｜エントリを持ち、その各々はＷからの要素であり、従ってこれは｜Ｖ｜｜Ｔ｜ｌｏｇ２｜Ｗ｜ビットを使用する。これらは図３のテーブル３７２及び３７４である。全てのｗ１∈Ｗ、ｗ２∈Ｗ及びτ∈Ｔについて
2016505891.tif 000018
となるような関数φ：Ｗ×Ｗ×Ｔ→Ｖを使用し、
2016505891.tif 000019
はＷ×Ｔの秘密置換である。φに対するテーブルは｜Ｗ｜２｜Ｔ｜エントリを持ち、その各々はＶの要素であり、従って所要ビットの数は｜Ｗ｜２｜Ｔ｜ｌｏｇ２｜Ｖ｜に等しい。これは図３のテーブル３８５である。最後に、全てのｗ∈Ｗ、τ∈Ｔ、σ∈Σに対して
2016505891.tif 000020
となるような関数Ψ：Ｗ×Ｔ×Σ：→Ｖを実装するためのテーブルを使用する。これは図３のテーブル３６０である。このテーブルに対するビットの数は｜Ｗ｜｜Ｔ｜｜Σ｜ｌｏｇ２｜Ｖ｜に等しい。
【００９９】
従って所要ビットの総数は（｜Ｖ｜＋｜Σ｜２）ｌｏｇ２｜Σ｜＋｜Σ｜２ｌｏｇ２｜Ｔ｜＋２｜Ｖ｜｜Ｔ｜ｌｏｇ２｜Ｗ｜＋｜Ｗ｜｜Ｔ｜（｜Ｗ｜＋｜Σ｜）ｌｏｇ２｜Ｖ｜に等しい。特殊な場合｜Ｗ｜＝｜Σ｜において、これは｜Ｗ｜２ｌｏｇ２｜Ｔ｜＋２｜Ｗ｜２（３｜Ｔ｜＋１）ｌｏｇ２｜Ｗ｜に縮小する。
【０１００】
上記から、より小さい内部状態空間Ｔが所要テーブルサイズを縮小し得るように見える。次に、上述のテーブルをどのように使用するか明示する。入力ν１＝Ｅ（ｗ１，σ１）及びν２＝Ｅ（ｗ２，σ２）を考える。攻撃者はν１とν２を観察することができるが、ｗ１とｗ２を観察することはできないことが留意される。以下のプログラムを実行する。
2016505891.tif 000021
【０１０１】
小さい状態空間の欠点は以下の通りである。上記プログラムにおいて、
2016505891.tif 000022
となるようなｙ１，ｙ２を計算する。従って攻撃者が二つの異なる値ν１及びν'１について対応する値ｙ１及びｙ'１が実際に等しいことを観察する場合、ν１及びν'１がｗの同じ値をあらわすことがわかる。Ｔが小さい場合、ｗ１に対する異なる代表元はｙ１に対して同じ値を生じる可能性が極めて高い。極端な場合：Ｔが一つの要素しか持たない場合、Ｗにおける要素の異なる代表元は常にｙ１の同じ値を与える。従ってＴが過度に小さく選ばれないことが有利である。例えば、Ｔは４若しくは８若しくは１６の要素を持ち得る。
【０１０２】
以下にエンコーダ１１０、デコーダ１７０、状態エクストラクタテーブル２１２及び２１４の構成の実施例が与えられる。各４ビットの単一関数入力と単一状態入力を仮定する（いずれかのより多くがあってもよい）。
【表１】
2016505891.tif 000023
【０１０３】
最初の二列は関数入力値と状態入力値の可能な組み合わせ全部をリストする。最後の列は２進法で数０から２５５のランダム置換をリストする。暗号化は、２５６−２＝２５４の入力‐出力ペアの完全な知識があっても、残り二つのペアはそれでも１ビットの不確実性をその中に持つという意味で、完全であることが留意される。８ビット幅のブロック暗号を用いることによって、完全ではないがそれでも非常に有効なエンコーディングが得られる。
【０１０４】
エンコーディングテーブルは最初の二列についてソートすることによって得られ、得られるテーブルは最初の二列から最後の列（エンコーディング）を得る方法を示す。最後の列についてソートすることによって、エンコードの代わりにデコードするテーブルが得られる。最初の列を除去して最後の列についてソートすることによって、状態エクストラクタ関数が得られる。一般に、入力及び出力列の両方を記憶する必要はないことが留意される。例えば、入力列が記憶され、全ての可能な組み合わせを含む場合、これは省略され得る。
【０１０５】
図３ｃは縮小された状態関数を使用しない状態依存再エンコーディングを示す。図３ｃの状態依存再エンコーディングテーブル３７２及び３７４は、縮小された状態値の代わりに状態出力値２３２を入力として持つ点を除き、図３ｂのものと同じである。これは行われる再エンコーディングがより安全であることを意味する。他方で３７２、３７４及び３８５におけるテーブルは広範囲の入力を持つ。興味深いことに、図３ｃのデータ関数テーブル３８５は図３ｂのものよりも大きな入力を持つが、テーブル３８５は出力に組み込む正確な状態出力値を持つので、再エンコーディングテーブル３６０は必要ない（これは可能であるが、テーブルサイズを縮小し得る）。
【０１０６】
一実施例として関数及び状態値に対して再度４ビットをとると、図３ｃのテーブル３７２は４＋４＋４＝１２ビットを入力として、４ビットを出力として持つ。図３ｃのテーブル３８５は４＋４＋４＝１２ビットを入力として、４＋４＝８ビットを出力として持つ。
【０１０７】
図５は記憶装置５１０を持つ計算装置５００を示す。記憶装置５１０は典型的には一つ以上の不揮発性メモリであるが、ハードディスク、光学ディスクなどであってもよい。記憶装置５１０はダウンロードされる、若しくは他の方法で受信されるデータを有する揮発性メモリであってもよい。計算装置５００はプロセッサ５５０を有する。プロセッサは典型的にはメモリに記憶されるコード５５５を実行する。便宜上、コードは記憶装置５１０に記憶され得る。コードはプロセッサに計算を実行させる。装置５００は入力値を受信する及び／又は結果を送信するためにオプションのＩ／Ｏ装置５６０を有し得る。Ｉ／Ｏ装置５６０はネットワーク接続、リムーバブル記憶装置などであり得る。
【０１０８】
記憶装置５１０は図１から３の一つにかかる一つ以上のテーブルネットワークを含む。
【０１０９】
一実施形態において、計算装置は動作中に以下の通り機能し得る：計算装置５００は入力値を受信する。入力値は例えばエンコーディングテーブル５４１、例えばテーブル１１０を用いることによってエンコードされる。従って入力値はエンコードされた入力値として取得される。入力値は例えば装置５６０を通じて直接、エンコードされた入力値として取得され得ることが留意される。入力値をエンコードされた入力値にエンコードすることは、状態入力が選ばれなければならないことを示唆する。そうする方法はいくつかあり、例えば状態入力はランダムに、例えば乱数発生器によって選ばれ得る。状態入力はアルゴリズムに従って選ばれ得る。アルゴリズムは複雑で、難読化を増大し得る。状態入力値は一定であるか、若しくは数列から連続的にとられてもよく、例えば１の一定増分を持ち、何らかの開始点で開始する整数列から連続的にとられてもよく、開始点はゼロ、乱数などであり得る。状態入力を乱数として選び、次の状態入力選択ごとに１増加することは特に有利な選択である。状態入力が装置外で（ｏｆｆ‐ｄｅｖｉｃｅ）選ばれる場合、攻撃者はどこで状態入力値が選ばれそれらが何であるかを追跡することができない。
【０１１０】
プロセッサ５５０はメモリ５１０内のプログラム５５５を実行する。プログラムはプロセッサに、エンコードされた入力値又は得られる出力値にルックアップテーブルを適用させる。ルックアップテーブルはいかなる論理若しくは算術関数について作成されてもよく、従ってルックアップテーブルのシーケンスを用いることによって任意の計算が実行され得る。これはプログラムを難読化するのに役立つ。この場合ルックアップテーブルは難読化のためにエンコードされ、中間値もエンコードされる。この場合、単一関数入力値が複数のエンコードされた入力値によってあらわされ得るので、難読化は特に有利である。さらに、一部の若しくは全部のテーブル及び／又はテーブルネットワークは複数の関数特性を持つ。
【０１１１】
ある時点で結果値が発見される。必要な場合結果は例えばデコーディングテーブル５４２、例えばテーブル１７０を用いてデコードされ得る。しかし結果はエンコードされた形でエクスポートされてもよい。入力値は入力装置から取得されてもよく、出力値は画面上に表示するために使用され得る。
【０１１２】
計算はエンコードされたデータワードに対して実行される。計算はテーブルルックアップアクセスのシーケンスを適用することによってなされる。使用される入力値は計算装置外から受信される入力値であり得るが、前のルックアップテーブルアクセスによって取得されてもよい。このように中間結果が得られ、そしてこれは新たなルックアップテーブルアクセスのために使用され得る。ある時点で中間結果の一つは関数のエンコードされた結果である。
【０１１３】
計算装置５００は状態入力値をデータ関数入力に割り当てるための乱数発生器を有し得る。
【０１１４】
図６はコンパイル法６００をフローチャートとして例示する。ステップ６１０において第一のコンピュータプログラムが受信器によって受信される。ステップ６２０において例えばトークンを識別するために字句解析器によって字句解析が実行される。場合によりマクロ展開などの処理もなされる。ステップ６３０においてプログラムはパーサによって構文解析される。例えば、パーサは第一のプログラムのプログラミング言語の形式文法に従って構文解析木を生成する。パーサはプログラム内の異なる言語構築を識別し、適切なコード生成ルーチンをコールする。特に、演算子若しくは複数の演算子が識別される。その場合、ステップ６４０においてコード生成がコード生成器によってなされる。コード生成中、一部のコードが生成され、必要であれば付随テーブルが生成される。付随テーブルは二つの関数に対して構成されるテーブルを含む：必要な演算子に対して一つ、及び状態関数。生成されるコードは、一つ以上のルックアップテーブルによって置換されるので、演算子を含む必要がなく、一般に含まない。状態関数はランダムに選ばれ得る。状態関数はプログラムの結果として選ばれてもよく、例えば状態関数は別の必要な演算子であってもよく、これはテーブルが再利用されることを可能にする。例えば、パーサは演算を識別して加算し、これを加算命令のためのルックアップテーブルに、及び正確な値にルックアップテーブルを適用するための生成コードに変換する。状態関数としてコンパイラはランダム関数を選択し得る。コンパイラは関数の集合、例えば加算、減算、乗算及び同様のものから関数をランダムに選択してもよい。
【０１１５】
一部のテーブルが何度も生成されることがよく起こる可能性があり、その場合それらを何度も記憶する必要がないので、ステップ６５５において、生成されたテーブルはテーブルベースにマージされる。例えば、加算テーブルは一度だけ必要であり生成され得る。全コードがマージされ全テーブルがマージされるとコンパイルは終了する。随意に、最適化ステップがあってもよい。
【０１１６】
典型的には、コンパイラはエンコードされた定義域を、すなわち全ての値若しくは少なくとも何らかの基準に対応する全ての値がエンコードされる、すなわちコードワードビットサイズ（ｎ）を持つ、プログラムのセクションを使用する。エンコードされた定義域において、演算はルックアップテーブル実行によって実行され得る。エンコードされた定義域に入ると全ての値がエンコードされ、エンコードされた定義域から離れると値がデコードされる。基準は、値がセキュリティ機密情報、例えば暗号鍵に相関する、又は依存するというものであり得る。
【０１１７】
コンパイラを作成する興味深い方法は以下の通りである。ステップ６３０において中間コンパイルがなされる。これは中間言語、例えばレジスタ転送言語などへのコンパイルであり得るが、機械語コードコンパイルであってもよい。これは図６のステップ６１０‐６３０に対して、テーブルネットワークを生じない従来のコンパイラが使用され得ることを意味する。しかしながらステップ６４０においてコード生成は中間コンパイルに基づいてなされる。例えば、機械語コードが使用された場合、各命令はその命令の対応する演算子フリー実装によって、すなわちその命令のテーブルベース実装によって置換される。これはコンパイラを作成する特定の直接的な方法をあらわす。図６は機械語でなく第二のプログラミング言語を生成するコンパイラを生成するためにも使用され得る。
【０１１８】
一実施形態において、コンパイラは第一のコンピュータプログラミング言語で書かれた第一のコンピュータプログラムを第二のコンピュータプログラムにコンパイルするためのコンパイラであり、コンパイラはテーブルと機械語コードを生成することによって第二のコンピュータプログラムを生成するコード生成器を有し、生成されるテーブルと生成される機械語コードは一緒に第二のコンピュータプログラムを形成し、生成される機械語コードはテーブルを参照し、コンパイラは第一のコンピュータプログラムにおける演算式若しくは論理式を識別するように構成され、式は少なくとも一つの変数に依存し、コード生成器は、多値の変数に対する識別された式の事前計算された結果をあらわし、少なくとも一つの他の式をあらわす、一つ以上のテーブルを生成するように、並びに事前計算された結果をあらわす生成される一つ以上のテーブルにアクセスすることによって第二のコンピュータプログラムにおいて識別された式を実装する機械語コードを生成するように、構成される。理想的には、識別された式を実装するように生成される機械語コードは算術若しくは論理機械命令自体を含まず、少なくとも機密情報に関連する算術若しくは論理機械命令を含まない。テーブルをリバースエンジニアリングした攻撃者は、それが識別された式をあらわすかもしれないが、他の式もあらわすかもしれないことを知り得る。
【０１１９】
これは、より少ない算術若しくは論理演算を含むので、リバースエンジニアリングに対する抵抗を増大し、第二のコンピュータプログラムのサイドチャネル漏洩を低下させる。理想的には、全ての演算式と論理式及び部分式はテーブルアクセスによって置換される。演算式若しくは論理式又は部分式を構成するこれらの命令がないので、これらはいかなる情報も漏洩し得ない。テーブルは事前計算され、テーブルに含まれる算術的若しくは論理的挙動を実行するために消費される電力はプログラムの実行中は見えない。
【０１２０】
図７は関数入力値に対してデータ関数を計算するための方法７００をフローチャートで例示する。ステップ７１０において関数入力値は状態入力値と一緒にエンコードされた入力値に組み合わされる。この組み合わせは暗号化する方法でなされる。入力値のエンコーディングは異なる場所で及び／又は異なる当事者によってなされ得ることが留意される。ステップ７２０においてテーブルネットワークがエンコードされた入力値に適用され、エンコードされた出力値を出力として生成する。ステップ７３０において、関数出力値がエンコードされた出力値から得られる。状態出力値もエンコードされた出力値から得られるが、これは必要ないかもしれないことが留意される。関数出力値はデータ関数を関数入力値に適用する結果に等しく、状態出力値は状態関数を状態入力値に適用する結果に等しい。ステップ７３０は異なる場所で及び／又は異なる当事者によってなされ得る。
【０１２１】
当業者に明らかになる通り、本明細書に開示される方法を実行する多くの異なる方法が可能である。例えば、ステップの順序は変更されることができ、又は一部のステップは並行して実行され得る。さらに、ステップの間に他の方法ステップが挿入されてもよい。挿入されるステップは本明細書に記載したような方法の改良をあらわし得るか、又は方法に無関係であり得る。
【０１２２】
本発明にかかる方法は、プロセッサシステムに方法７００を実行させるための命令を有するソフトウェアを用いて実行され得る。ソフトウェアはシステムの特定のサブエントリによってとられるステップのみを含んでもよい。ソフトウェアはハードディスク、フロッピー、メモリなどといった適切な記憶媒体に記憶され得る。ソフトウェアは配線に沿って、若しくは無線で、若しくはデータネットワーク、例えばインターネットを用いて、信号として送信され得る。ソフトウェアはダウンロード及び／又はサーバ上での遠隔使用のために利用可能にされてもよい。
【０１２３】
当然のことながら本発明はコンピュータプログラムに、特に本発明を実現するように構成されるキャリア上若しくは中のコンピュータプログラムにも及ぶ。プログラムはソースコード、オブジェクトコード、コード中間ソース及び部分的にコンパイルされた形式などのオブジェクトコードの形式で、又は本発明にかかる方法の実装において使用するのに適した任意の他の形式であり得る。コンピュータプログラム製品に関する実施形態は、上記方法の少なくとも一つの処理ステップの各々に対応するコンピュータ実行可能命令を有する。これらの命令はサブルーチンに分割されるか、及び／又は静的に若しくは動的にリンクされ得る一つ以上のファイルに記憶され得る。コンピュータプログラム製品に関する別の実施形態は、上記システム及び／又は製品の少なくとも一つの手段の各々に対応するコンピュータ実行可能命令を有する。
【０１２４】
上述の実施形態は本発明を限定するのではなく例示し、当業者は多くの代替的な実施形態を設計することができることが留意されるべきである。クレームにおいて、括弧の間に置かれる任意の参照符号はクレームを限定するものと解釈されてはならない。"有する"という動詞とその活用形の使用は、クレームに列挙される以外の要素若しくはステップの存在を除外しない。ある要素に先行する冠詞"ａ"若しくは"ａｎ"はかかる要素の複数の存在を除外しない。本発明は複数の個別要素を有するハードウェアを用いて、適切にプログラムされるコンピュータを用いて実装され得る。複数の手段を列挙する装置クレームにおいて、これら手段の一部はハードウェアの一つの同じ項目によって具体化されてもよい。特定の手段が相互に異なる従属クレームに列挙されるという単なる事実は、これら手段の組み合わせが有利に使用されることができないことを示さない。
【符号の説明】
【０１２５】
１００              テーブルネットワーク
１０２，１０４      関数入力値
１１０              エンコーダ
１１２，１１４      状態入力値
１２２，１２４      エンコードされた入力値
１３０              データ関数
１６０              エンコードされた出力値
１６２              関数出力値
１６４              状態出力値
１７０              デコーダ
１８０              テーブルネットワーク
２００              テーブルネットワーク
２１２，２１４      状態エクストラクタテーブル
２３０              状態関数テーブル
２４２，２４４      再エンコーディングテーブル
２５２，２５４      再コード化された入力値
２６０              データ関数テーブル
３１０              縮小された状態関数テーブル
３２０              縮小された状態値
３３２，３３４      再エンコーディングテーブル
３４２，３４４      再コード化された入力値
３５０              データ関数テーブル
３６０              再エンコーディングテーブル
３７２，３７４      状態依存再エンコーディングテーブル
３８２，３８４      再コード化された入力値
４１０              入力テーブル
４２０              中間テーブル
４３０              出力テーブル
５００              計算装置
５１０              記憶装置
５２１，５２２      単一入力ルックアップテーブル
５３１，５３２      複数入力ルックアップテーブル
５３１１‐５３２３  単一入力ルックアップテーブル
５４１              エンコーディングルックアップテーブル
５４２              デコーディングルックアップテーブル
５５５              機械語コード
５５０              コンピュータプロセッサ
５６０              Ｉ／Ｏ装置
【図１】
2016505891.tif 000028
【図２】
2016505891.tif 000029
【図３ａ】
2016505891.tif 000030
【図３ｂ】
2016505891.tif 000031
【図３ｃ】
2016505891.tif 000032
【図４】
2016505891.tif 000033
【図５】
2016505891.tif 000034
【図６】
2016505891.tif 000035
【図７】
2016505891.tif 000036
【国際調査報告】
2016505891.tif 000037
2016505891.tif 000038
2016505891.tif 000039