(57)【特許請求の範囲】
【請求項１】
１以上の入力の関数を計算する計算装置であって、
−  前記装置は前記関数の計算において使用される１以上のルックアップテーブルを記憶する記憶装置を有し、前記ルックアップテーブルは入力値を出力値にマッピングし、前記ルックアップテーブルは、第１エラー訂正コード、第２エラー訂正コード、第１エラー閾値及び第２エラー閾値に関して、各々が前記第１エラー訂正コードの同じコードワードから最大で第１エラー閾値数のビットだけ相違する何れの２つの入力値も、各々が前記第２エラー訂正コードの同じコードワードから最大で第２エラー閾値数のビットだけ相違する対応する出力値にマッピングされるように構築され、
−  前記第１エラー閾値は、少なくとも１、最大で前記第１エラー訂正コードのエラー訂正能力t1であり、前記第２エラー閾値は最大で前記第２エラー訂正コードのエラー訂正能力t2である、
計算装置。
【請求項２】
前記第１エラー訂正コードが前記第２エラー訂正コードと同一である、請求項１に記載の計算装置。
【請求項３】
前記第１エラー閾値が前記第１エラー訂正コードのエラー訂正能力t1に等しい、請求項１又は請求項２に記載の計算装置。
【請求項４】
前記第２エラー閾値が零である、請求項１ないし３の何れか一項に記載の計算装置。
【請求項５】
当該計算装置は前記１以上の入力を１以上のエンコードされた入力として取得し、エンコードされた入力は前記１以上の入力の１つにエンコード関数を適用することにより得られ、該エンコード関数は入力をエラー訂正コードの対応するコードワードに、オプションとして第１エラー閾値数までのビットエラーを加えて、マッピングする、請求項１ないし４の何れか一項に記載の計算装置。
【請求項６】
当該計算装置は前記関数を一連の中間結果に一連のテーブルルックアップアクセスを適用することにより計算し、前記中間結果は前記一連のテーブルルックアップアクセスの出力値及びエンコードされた入力値を含み、前記中間結果の１つが前記関数のエンコードされた結果である、請求項１ないし５の何れか一項に記載の計算装置。
【請求項７】
前記第１エラー訂正コード及び第２エラー訂正コードの何れか一方は、［ｎ，ｋ，ｄ］（ただし、ｎは前記第１エラー訂正コード及び前記第２エラー訂正コードのコードワードのビット数、ｋは前記第１エラー訂正コード及び前記第２エラー訂正コードのデータワードのビット数、ｄは第１エラー閾値及び第２エラー閾値である。）とした場合、[7,4,3]、[11,4,5]、[12,8,3]、[16,8,5]、[21,16,3]、[9,5,3]、[13,5,5]、[10,6,3]、[14,6,5]、[8,4,4]及び[10,4,4]のうちの何れかである、請求項１ないし６の何れか一項に記載の計算装置。
【請求項８】
演算子が入力ビットサイズk1のビット列を出力ビットサイズk2のビット列にマッピングするルックアップテーブルを構築する方法であって、当該方法は、
−  ビット列を発生するステップであって、発生されたビット列が第１エラー訂正コードのコードワードビットサイズn1と同じサイズを有し、該第１エラー訂正コードが少なくとも前記入力ビットサイズk1の大きさを有するステップと、
−  デコード可能な発生された各ビット列に関して、
−    前記発生されたビット列をデコードして、デコードされた発生されたビット列を取得し、該デコードは前記第１エラー訂正コードに対応し、
−    前記演算子を前記デコードされた発生されたビット列に適用し、
−    前記演算子の結果をエンコードして、第２エラー訂正コードのコードワードを取得し、オプションとして該コードワードに最大で第２エラー閾値数のビットエラーを加え、該第２エラー閾値数は最大で前記第２エラー訂正コードのエラー訂正能力t2であり、該第２エラー訂正コードは少なくとも前記出力ビットサイズk2の大きさを有し、
−    前記ルックアップテーブルにおいて、前記デコード可能な発生されたビット列をオプションとしてのビットエラーを含む前記演算子のエンコードされた結果にマッピングする、
ステップと、
を有する、方法。
【請求項９】
演算子が入力ビットサイズk1のビット列を出力ビットサイズk2のビット列にマッピングするルックアップテーブルを構築する方法であって、
−  前記入力ビットサイズk1と同じサイズを持つビット列を発生するステップと、
−  発生された各ビット列に関して、
−    前記演算子を前記発生されたビット列に適用し、
−    前記演算子の結果をエンコードして、第２エラー訂正コードからのコードワードを取得し、オプションとして該コードワードに訂正可能なエラーパターンを加え、前記第２エラー訂正コードは少なくとも前記出力ビットサイズk2の大きさを有し、
−    前記発生されたビット列をエンコードして、第１エラー訂正コードからのコードワードを取得し、該第１エラー訂正コードは少なくとも前記入力ビットサイズk1の大きさを有する、
ステップと、
−  訂正可能な各エラーパターンに関して、
−    前記訂正可能なエラーパターンを前記エンコードされた発生されたビット列に適用して、エンコードされた入力値を取得し、
−    前記ルックアップテーブルにおいて、前記エンコードされた入力値をオプションとしてのビットエラーを含む前記演算子の前記エンコードされた結果にマッピングする、
ステップと、
を有する、方法。
【請求項１０】
前記関数の計算に使用される前記１以上のルックアップテーブルの一つのルックアップテーブルが、入力ビットサイズｋのビット列を入力ビットサイズｋのビット列にマッピングする演算子から構築されている、請求項１ないし７の何れか一項に記載の計算装置。
【請求項１１】
前記演算子が双射である、請求項１０に記載の計算装置。
【請求項１２】
前記演算子が恒等である、請求項１０に記載の計算装置。
【請求項１３】
第１コンピュータプログラミング言語で書かれた第１コンピュータプログラムを第２コンピュータプログラムにコンパイルするコンパイラであって、
−  前記コンパイラは前記第２コンピュータプログラムをテーブル及びマシン語コードを発生することにより発生するコード発生部を有し、前記発生されたテーブル及び前記発生されたマシン語コードは、一緒に、前記第２コンピュータプログラムを形成し、前記発生されたマシン語コードは前記テーブルを参照し、
−  前記コンパイラは前記第１コンピュータプログラムにおける算術又は論理表現を識別し、該表現は少なくとも１つの変数に依存し、前記コード発生部は、前記変数の複数の値に対する前記識別された表現の事前計算された結果を表す１以上のテーブルを発生すると共に、前記第２コンピュータプログラムにおいて前記識別された表現を実施するためのマシン語コードを前記事前計算された結果を表す前記発生された１以上のテーブルにアクセスすることにより発生し、前記１以上のテーブルが発生される、
コンパイラ。
【請求項１４】
入力ビットサイズｋを有する１以上の入力の関数を計算する方法であって、当該方法は、
−  １以上のルックアップテーブルを記憶するステップであって、前記ルックアップテーブルは入力値を出力値にマッピングし、ルックアップテーブルの入力値は第１エラー訂正コードの第１コードワードのビットサイズn1に等しいビットサイズを有し、前記ルックアップテーブルは、前記第１エラー訂正コード、第２エラー訂正コード、第１エラー閾値及び第２エラー閾値に関して、各々が前記第１エラー訂正コードの同じコードワードから最大で第１エラー閾値数のビットだけ相違する何れの２つの入力値も、各々が前記第２エラー訂正コードの同じコードワードに対して最大で第２エラー閾値数のビットだけ相違する対応する出力値にマッピングされるように構築され、前記第１エラー閾値は、少なくとも１、最大で前記第１エラー訂正コードのエラー訂正能力t1であり、前記第２エラー閾値は最大で前記第２エラー訂正コードのエラー訂正能力t2であるステップと、
−  エンコードされた値に前記１以上のルックアップテーブルを適用するステップを有する前記関数の計算に前記１以上のルックアップテーブルを使用するステップと、
を有する、方法。
【請求項１５】
請求項８、９及び１４の何れか一項に記載の方法における全てのステップを実行するコンピュータプログラムコード手段を有する、コンピュータプログラム。
【請求項１６】
コンピュータ読取可能な媒体上に具現化された請求項１５に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力ビットサイズを有する１以上の入力の関数を計算するように構成された計算装置に関するもので、該装置は上記関数の計算において使用される１以上のルックアップテーブルを記憶する記憶装置を有し、該ルックアップテーブルは入力値を出力値にマッピングする。
【背景技術】
【０００２】
コンピュータ構成装置のセキュリティは、複数の要因に依存する。一方では、基となる抽象プロトコル（abstract protocol）及び暗号法のセキュリティが存在する。採用された暗号法が解読されると、典型的に当該システムも解読される。他方において、構成（implementation）自体に関するセキュリティも存在する。
【０００３】
例えば、コンピュータシステムが所謂サイドチャンネルを介して幾らかの情報を漏らすことが長く知られている。コンピュータシステムの入力／出力挙動を観察することは、該コンピュータシステムにより使用されている秘密キー等の機密情報（sensitive information）に関する如何なる有用な情報も提供しないかも知れない。しかしながら、コンピュータシステムは、例えば該システムの電力消費又は電磁放射等の、観察され得る他のチャンネル（これらチャンネルは、サイドチャンネルと称される）を有している。例えば、異なる命令により消費される電力の小さな変化及び命令を実行する間に消費される電力の変化を測定することができる。測定された変化は、暗号キー等の機密情報と関連付ける（相関をとる）ことができる。観察可能な意図する入力／出力挙動を越える、該機密情報に関する付加的情報は、サイドチャンネルと称される。サイドチャンネルを観察及び分析することは、攻撃者に対して、入力／出力挙動の暗号分析のみから得られ得るものよりも良好な接近手段を提供し得る。１つの既知のタイプのサイドチャンネル攻撃は、所謂、差分電力分析（ＤＰＡ）である。
【０００４】
システムを攻撃する他の方法も存在する。古典的なサイドチャンネル攻撃に関するものは、障害（故障）注入攻撃である。ここでは、基となるハードウェアが意図的に誤動作させられる。該誤動作により、当該装置は誤った解答を生成する。特定のタイプのエラーが秘密情報に関係していれば、エラーを解析することは秘密情報を明らかにすることになり得る。特に、閃光攻撃としても知られている光攻撃は障害を注入する特に強力な方法である。光攻撃においては、中間値を混乱させるために、レーザ光が計算中の回路に照射される。
【０００５】
例えば、ＲＳＡ署名アルゴリズムに対する既知の攻撃は、当該システムの電圧供給を調整することにより目標マシンに過渡障害を注入する。攻撃者は犠牲となるチップの内部部品に対してアクセスする必要はなく、当該システムを過渡障害に曝しながら該システムからの壊れた署名出力を単に収集する。十分な数の壊れたメッセージが収集されたら、オフライン分析により秘密キーを抽出することができる。
【０００６】
障害攻撃に対抗する１つの方法は、計算を検証することである。例えば、重要な計算を２回実行することによるものである。ＲＳＡ署名の特別なケースでは、署名をＲＳＡ検証アルゴリズムにより検証することができる。このようにして、障害攻撃は検出され、誤った値が当該計算装置から出ることが防止される。
【０００７】
コンピュータに対する更に強力な攻撃は、所謂、リバースエンジニアリングである。多くのセキュリティ状況において、攻撃者は当該コンピュータに対して完全なアクセスを有し得る。このことは、攻撃者に対して当該プログラムを分解し、当該コンピュータ及びプログラムに関する如何なる情報をも得る機会を提供してしまう。十分に努力すれば、例えばプログラム内に隠された如何なるキーも攻撃者により見付けられてしまい得る。
【０００８】
このような攻撃計画に対して保護することは、非常に困難であることが分かった。１つのタイプの対抗手段は、所謂、ホワイトボックス暗号法である。ホワイトボックス暗号法では、キー及びアルゴリズムは組み合わされる。結果としてのアルゴリズムは、１つの特定のキーに対してのみ動作する。次に、該アルゴリズムは、所謂、ルックアップテーブル・ネットワークとして構成することができる。計算は、キー依存テーブルにおける一連のルックアップに変換される。この方法の一例に関しては、例えば、S. Chow, P. Eisen, H. Johnson及びP.C. van Oorschotによる“White-Box Cryptography and an AES Implementation”を参照されたい。
【０００９】
コンピュータハードウェア及びコンピュータソフトウェアによる機能の実施化は、共に、上述したサイドチャンネル攻撃に対して脆弱である。しかしながら、この問題はソフトウェアにおいて最も厳しい。ハードウェア構成と比較して、ソフトウェアは相対的に遅く、相対的に大量の電力を消費する。両要因は、サイドチャンネル攻撃に有利に働く。
【００１０】
コンパイルを変更することによりサイドチャンネル攻撃に対するコンピュータプログラムの抵抗力を増加させる試みがなされている。
【００１１】
米国特許第7996671号は、サイドチャンネル攻撃に対するコンピュータプログラムの抵抗力を改善されたコンパイルにより増加させることを提案している。電力分析攻撃は測定される電力消費に依存しているので、抵抗力は、電力消費を減少させるようにコンパイルすることにより増加される。コンパイラは、最もエネルギ効率的なコンパイルを予測し、該コンパイルを選択する。エネルギ消費の低減は、電力ノイズ／変化を増加させ、サイドチャンネル抵抗力を改善することが分かる。
【００１２】
エネルギ低減方法のみでは十分な電力ノイズ／変化を生じさせるのに不十分である場合、エネルギ最適化のために使用される上記コンパイラ方法を、暗号アルゴリズム等のコードの重要な部分における電力コストをランダム化するために使用することができる。このことは、異なる電力要件でコードを入念に発生することによりコンパイル時に達成される。
【００１３】
計算にランダムさを導入するサイドチャンネル問題に対する現在の方法は、満足の行くものではないことが分かっている。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上記及び他のセキュリティ問題に対処することが有益である。攻撃者は、サイドチャンネル攻撃に対する上述したコンパイルに基づく対抗策はＤＰＡ等の受動的サイドチャンネルに対抗するには或る程度有効であり得るが、障害攻撃及びリバースエンジニアリング等の能動的攻撃に対してはそうでないと見ている。
【課題を解決するための手段】
【００１５】
１以上の入力の関数を計算するように構成された計算装置が提供される。該装置は、上記１以上の入力を１以上のエンコード（符号化）された入力として得るよう構成される。該装置は前記関数の計算において使用される１以上のルックアップテーブルを記憶する記憶装置を有し、これらルックアップテーブルは入力値を出力値にマッピングする。ルックアップテーブルの入力値は、第１エラー訂正コードの第１コードワードのビットサイズ（n1）に等しいビットサイズを持つ。該ルックアップテーブルは、上記第１エラー訂正コード、第２エラー訂正コード、第１エラー閾値及び第２エラー閾値に対して、各々が前記第１エラー訂正コードの同じコードワードから最大で第１エラー閾値数のビットだけ相違する何れの２つの入力値も、各々が前記第２エラー訂正コードの同じコードワードに対して最大で第２エラー閾値数のビットだけ相違する対応する出力値にマッピングされるように構築される。前記第１エラー閾値は、少なくとも１、最大で前記第１エラー訂正コードのエラー訂正能力（t1）であり、前記第２エラー閾値は最大で前記第２エラー訂正コードのエラー訂正能力（t2）である。
【００１６】
エンコードされた入力はエンコード関数を前記入力の１以上に適用することにより得ることができ、該エンコード関数は入力をエラー訂正コードの対応するコードワードにマッピングする。オプションとして、上記のエンコードされた入力は或る程度崩すことができる。即ち、入力値に適用される第１ルックアップテーブルに対応する第１閾値までのビットエラーを、エンコードされた入力値に加えることができる。一般的に、ビットエラーを加えることは、ビット（この場合は、第１エラー閾値数までのビット）を変化（即ち、反転）することにより実行することができる。幾つかのアプリケーションにおいて、当該プログラムは実際にエンコードされた入力を直接受け取る。当該コンパイラは、エンコードされていない値をエンコードされた値に変換するための補助的プログラムを作成するように構成することができる。該補助的プログラムは、エンコードされた入力値を供給する必要がある他のアプリケーションにより使用することができる。
【００１７】
入力値自体の代わりに、エンコードされた入力値を使用することは、当該プログラムの難読化に貢献する、即ち該プログラムをリバースエンジニアリングする困難さを増加させる。前記記憶されたルックアップテーブルは、エラー訂正特性を有する。これらの特性は２つの方法で利用することができる。同じコードワードに対して最大でエラー訂正能力（“ｔ”とも称される）までのビットだけ相違する全てのエンコードされた入力値は、当該ルックアップテーブルにより同じ方法で処理される。このように、最大で“ｔ”個のビットエラーを生じさせる障害攻撃は、例えばキーに相関されたエラー等のセキュリティに関連するエラーを生じさせることはない。障害攻撃は、注入されねばならない各追加のエラーに伴って、益々困難となる。エラー訂正テーブルを用いて計算を実行することにより、障害攻撃は実行することが一層難しくなる。一方、当該ルックアップテーブルは、同一の入力値に属する、即ち同一のコードワードに近い２つの入力に対して同一の結果を与える必要はない。該ルックアップテーブルはエラーに対して抵抗性があるので、これらのエラーを意図的に導入することもできる。値とエンコードとの間の固定の関係が乱された場合、リバースエンジニアリングは益々困難となる。エラー訂正テーブルが使用される場合、単一の入力値は多数のエンコードされた値により表すことができる。特に、入力値、出力値及び内部変数の間の相関を見付けることに依存する自動化リバースエンジニアリングは、この統計的障害を克服するために著しく多い実行のデータを必要とする。当該エラー訂正テーブルが障害及びリバースエンジニアリング攻撃に対抗する２つの方法は互いを排除することを要し、両者は同時に使用することができる。
【００１８】
興味深いことに、当該エラー訂正コードは各ルックアップテーブルに対して同一である必要はない。エラー訂正コードは、各ルックアップテーブルに対して同一のパラメータを有することさえ必要としない。異なるエラー訂正コードを使用することは、難読化のために有益であるのみならず、当該システムの柔軟性を大きく増加させる。典型的に、ルックアップテーブルにより実施化される関数は、所謂テーブルのネットワークを使用する。複数の異なるエラー訂正テーブルを許容することにより、これらのテーブルは同一のサイズのものである必要はない。即ち、このことは必要とされるサイズ要件を大きく節約する。何故なら、小さくすることが可能なテーブルを実際に小さくすることができるからである。当該装置の一実施態様において、関数は、複数の異なる第１エラー訂正コード及び複数の異なる第２エラー訂正コードに関して構築されたテーブルのネットワークとして実施される。当該ルックアップテーブル・ネットワークにおいて、使用されるエラー訂正コードは適合しなければならない。即ち、第１テーブルの出力が第２テーブルに供給される場合、第１テーブルの第２エラー訂正コードは第２テーブルに対する第１エラー訂正コードでなければならない。
【００１９】
一実施態様においては、確かに、前記関数の計算に使用される前記１以上のルックアップテーブルは、該関数の計算に使用される第１及び第２ルックアップテーブルを有し、第１ルックアップテーブルは第１の第１エラー訂正コード及び第１の第２エラー訂正コードに関して構築され、第２ルックアップテーブルは第２の第１エラー訂正コード及び第２の第２エラー訂正コードに関して構築され、上記第１の第２エラー訂正コードは上記第２の第１エラー訂正コードに等しい。
【００２０】
しかしながら、このことは必要ではない。即ち、一実施態様において、ルックアップテーブルの第１エラー訂正コードは、該ルックアップテーブルの第２エラー訂正コードと同一である。一実施態様において、当該ルックアップテーブルの全ての第１エラー訂正コードは同一であると共に、当該ルックアップテーブルの全ての第２エラー訂正コードと同一である。
【００２１】
前記第１及び第２エラー閾値は、障害抵抗性と難読性の増加との間で取引がなされることを可能にする。
【００２２】
例えば、一実施態様において、第２エラー閾値は零である。この実施態様において、各々が同じコードワードに対して最大で第１エラー閾値数のビットだけ相違する如何なる２つの入力値も、同じ第２コードワードにマッピングされる。この実施態様は、障害注入に対して最適に保護を行う。中間値に注入される障害は、これらに対して何らかの計算が実行されるやいなや、自動的に訂正される。このタイプのルックアップテーブルは、意図的な障害が、テーブル内に固定される代わりに、当該プログラムに動的に挿入される場合にも最良のものである。同様に、第１エラー閾値を第１エラー訂正コードのエラー訂正能力（t1）に等しく選択することにより、エラー訂正能力は増加される。好ましい実施態様において、これら２つの選択は組み合わされる。
【００２３】
一実施態様において、当該計算装置は前記関数を、所謂、ルックアップテーブル・ネットワークにおいて計算するように構成される。前記記憶装置に記憶されたルックアップテーブルに一連のテーブルルックアップアクセスを適用することにより、一連の中間結果が得られる。これら中間結果は、上記一連のテーブルルックアップアクセスのエンコードされた入力値及び出力値を含み、該中間結果の１つが当該関数のエンコードされた結果である。エラー訂正テーブルの有益な効果は、プログラムの一層大きな部分に適用された場合に、一層強くなるということである。関数をテーブルのネットワークとして実施することにより、難読性に対する効果が著しく増加する。
【００２４】
テーブルのネットワークを構築することは、第１及び第２エラー訂正関数が当該ネットワークにおけるルックアップテーブルの各々に対して同一である場合に、一層容易となる。その場合、あるテーブルの出力値を、他のテーブルの入力値として直接使用することができる。しかしながら、幾らか注意すれば、テーブルは異なるエラー訂正コードを有することができる。例えば、或るテーブルの第２エラー訂正コードが他のテーブルの第１エラー訂正コードと等しくなることを確認することができる。更に、恒等演算子を変形することにより、或るエンコーディングを他のものに変換する変換テーブルを得る。
【００２５】
簡略化のために、例示の多くは１つのエラー訂正コードを、入力を受信するため、出力を供給するための両方に及び全ての中間値のために使用する。しかしながら、これは必要ではないことに注意すべきであり、異なる第１及び第２エラー訂正コードという複雑さの増加を可能にすること、即ち更なる難読性を得ること及び／又は記憶されるルックアップテーブルのフットプリントの低減を得ることは、確かに有益であり得る。第１エラー訂正コード及び第２エラー訂正コードが同一の最小距離を有することさえ必要ではなく、これが異なるテーブルの間で必要とされることもない。しかしながら、使用される全てのエラー訂正コードが同一の最小距離を有していれば好都合である。何故なら、このことは、エラーに対する最小限の保護を保証する一方、テーブルを該最小限の保護を満足させるために必要とされるものより大きくさせることを回避させるからである。
【００２６】
当該計算装置の一実施態様は、１以上の入力の関数を計算するように構成される。該
装置は前記関数の計算において使用される１以上のルックアップテーブルを記憶する記憶装置を有し、前記ルックアップテーブルは入力値を出力値にマッピングし、入力値及び出力値は前記コードワードのビットサイズに等しいビットサイズを有する。前記ルックアップテーブルは、当該エラー訂正コードに関して、各々が同じコードワードに対して最大で“ｔ”ビットだけ相違する何れの２つの入力値も、各々が他の同一のコードワードに対して最大で“ｔ”ビットだけ相違する対応する出力値にマッピングされるように構築される。上記値“ｔ”は、当該コードの“エラー訂正能力”とも称される。
【００２７】
例えば、当該計算装置は前記１以上の入力を１以上のエンコードされた入力として取得するように構成され、エンコードされた入力は前記入力の１つにエンコード関数を適用することにより得られる。該エンコード関数は、入力をｔ−エラー訂正コードの対応するコードワードにマッピングし、これらコードワードは前記入力のビットサイズより大きなコードワードビットサイズを有する。エンコードする前の入力は入力ビットサイズを有し、エンコードの後ではコードワードビットサイズを有する。
【００２８】
前記１以上の入力の関数は、セキュリティアプリケーションの実施、例えば署名又は暗号解読関数とすることができる。特に、キー、認可及びアクセス権等のセキュリティ機密値を扱う機能は、当該エラー訂正テーブルの恩恵を受ける。
【００２９】
前記エンコードされた入力を得ることは、当該計算装置自体により、例えば、エンコードモジュールによりエンコード関数を前記入力の１つに適用することによって実行することができる。このことは、当該計算装置の外部でも実行することができ、この場合、該計算装置はエンコードされた入力を直接受け取る。エラー訂正エンコーディングによるエンコードは、例えばホワイトボックス暗号法から既知のように、難読化エンコーディングとうまく組み合わせることができる。
【００３０】
例えば、Ｙはエンコードされていないドメイン、即ち、そのままの（入力）値を示す。そして、Ｘはコードワード空間を示す。ＭをドメインＹの一層大きなドメインＸへの埋め込みであるとする一方、Ｍ-1をドメインＸからＹへのマッピングであるとし、ここで、Ｘの値Ｍ(ν)における小さなエラーｅはνにマッピングで戻る。入力値ｙをエンコードすることは、Ｍ(ｙ)を計算することにより実行することができる。後者は、例えば線形行列乗算等のエンコード関数を適用することにより実行することができるが、ルックアップテーブルにより実行することもできる。ｇを難読化するＹからＹの関数であるとする。ｇを適用することは、変数の意味を隠蔽する。これは、上述したエンコーディングと以下のように組み合わせることができる。即ち、ｙはＭ(ｇ(ｙ))にマッピングされる。例えば、ｇはランダムに選択することができ、少なくともｇは恒等式ではない。
【００３１】
例えば、特別なコンパイラにより得られる、又は手で作成される関数のテーブル化された構成を用いる結果、より大きなフットプリントとなる。更に、当該エンコーディングは値のサイズを増大させるので、テーブルは、エラー訂正エンコーディング無しの場合より大きくなる。多くのアプリケーションの場合、当該利点は、この空間の増加に勝る。第１及び／又は第２エラー訂正コードに対して使用する幾つかの興味あるコードは、以下の[7,4,3]、[11,4,5]、[12,8,3]、[16,8,5]、[21,16,3]である。これらのコードは、相対的に小さな値の“ｔ”、即ち１又は２を、２値アーキテクチャに良く適合するエンコードされていないブロックサイズと組み合わせる。しかしながら、エンコードされていない入力ビットサイズ（ｋ）を２の冪乗に限定する理由はない（もっとも、これは便利ではあるが）。後者の場合、[9,5,3]、[13,5,5]、[10,6,3]、[14,6,5]等のコードを使用することもできる。
【００３２】
奇数の最小距離が好ましいが、偶数の最小距離を持つコードの使用も可能である。このことは、[8,4,4]、[10,4,4]等のコードも使用することができることを意味する。
【００３３】
偶数の最小距離(ｄ)を使用することは、障害検出にとり重要であり得る。ｄ＝2tによれば、(t-1)までのエラーを訂正することができ、ｔ個までのビットエラーを検出することができる。例えば、ｔ個のエラーが存在するかを検証するエラーロジックを含めることができる。また、非完全コードを使用する場合、該エラーロジックは訂正不能なビットパターンを検出することができる。このような問題が検出された場合、例えば当該処理を放棄する、エラーを掲示する等の適切な動作を行うことができる。
【００３４】
コンパイラの設計を大幅に簡素化させるので、線形コードが好ましいが、線形構成はルックアップテーブルの改善につながらない。このことは、[14,7,5]、[15,7,6]、[15,8,5]及び[16,8,6]等の非線形コードも使用することができることを意味する。
【００３５】
しかしながら、テーブルを小さく保つために、ｎを小さく、例えば１２以下、又は１１以下にさえ保つこと、及び当該寸法を小さく、例えば８以下、恐らくは４に保つことが好ましい。
【００３６】
本発明の一態様は、入力ビットサイズのビット列から入力ビットサイズのビット列へマッピングする演算子からのルックアップテーブルの構築に関するものである。これらの方法は、好ましくは、コンピュータにより実施される方法である。結果としてのルックアップテーブルは、好ましくは、コンピュータ読取可能な媒体に記憶される。
【００３７】
当該方法の一実施態様においては、コードワードビットサイズ（n1）の全ての訂正可能なビット列の部分集合が発生される。演算子が、上記発生された訂正可能なビット列の復号に適用される。即ち、該復号（デコーディング）は第１エラー訂正コードに従って実行される。その結果は、第２エラー訂正コードのコードワードに、恐らくは１以上のエラーを加えて、エンコードされる。前記発生された訂正可能なビット列が、オプションとしての１以上のエラーを含む上記エンコードされたコードワードにマッピングされるルックアップテーブルが構築される。当該演算子のエンコードされていない入力値におけるビットの数は、最大で、第１エラー訂正コードの大きさである。該演算子のエンコードされていない出力値におけるビットの数は、最大で、第２エラー訂正コードの大きさである。
【００３８】
エラー訂正ルックアップテーブルを構築するために、少なくとも２つの基準方法が存在する。両方法において、第１エラー訂正可能コードのコードワードサイズと同じサイズの訂正可能なビット列が構築され、該訂正可能なビット列に対応する演算子結果が計算され、第２エラー訂正コードからのコードワードが上記演算子結果をエンコードすることにより見付けられる。後者のステップは、恐らくは、ビットエラーを加える（即ち、訂正可能なビットエラーを加える）ステップを含む。次いで、訂正可能なビット列を演算子結果にマッピングするルックアップテーブルが構築される。
【００３９】
第１エラー訂正コードのコードワードサイズと同じサイズの訂正可能なビット列は、少なくとも２つの方法で見付けることができる。
【００４０】
第１の方法では、該訂正可能なビット列は直接発生される。完全コードの場合、これは、所与の長さの全ての可能性のあるビット列を単に発生することであり得る。もっと進んだ構成では、これは、所与の長さの全ての可能性のあるビット列を発生するが、デコード可能なビット列をフィルタすることであり得る。幾つかの特別なコードは、上記デコード可能なビット列を発生するための特別なアルゴリズムを有する。
【００４１】
第２の方法では、第１エラー訂正コードの寸法に等しいビットサイズのエンコードされていないビット列が発生される。これは、所与の長さの全てのビット列を直接発生することにより実行することができる。次いで、該発生されたビット列はエンコードされて、第１エラー訂正コードのコードワードを得る。該得られたコードワードから、訂正可能なビット列を、訂正可能なビットパターンを加えることにより得ることができる。訂正可能なビットパターンを加えることは、コードワードに最大で第１エラー閾値数のビットエラーを加えること、即ち該コードワードの最大で第１エラー閾値数のビットを変化させることであり得る。
【００４２】
例えば、一実施態様において、コードワードの訂正可能なビット列は、第１エラー訂正コードの第１コードワードビットサイズ（n1）と同一のサイズを有するビット列を発生することにより得られる。一実施態様では、該サイズの全てのビット列が発生される。例えば、コードワードの訂正可能なビット列は、第１入力ビットサイズ（k1）と同一のサイズを持つビット列を発生し、該発生されたビット列を第１エラー訂正コードのコードワードにエンコードし、全ての訂正可能なエラーパターンを発生し、該訂正可能なエラーパターンを上記のエンコードされた発生されたビット列に適用することにより得られる。一実施態様においては、全てのビット列及び／又は訂正可能なエラーパターンが発生される。
【００４３】
前記演算子は、算術演算子又は論理演算子等の基本的演算子とすることができる。しかしながら、演算子は、複数の基本演算子を含む表現（式）等の複雑な演算子とすることもでき、入力値を取り込んで出力値を生成するアルゴリズムとすることさえできる。特に、当該演算子は前記関数であり得るが、典型的には、該関数は複数の演算子の適用を必要とする。
【００４４】
ルックアップテーブルの構築のための前記方法により得られるルックアップテーブルは、前記計算装置において使用することができる。
【００４５】
本発明の一態様は、第１コンピュータプログラミング言語で書かれた第１コンピュータプログラムを第２コンピュータプログラムにコンパイルするコンパイラに関するものである。該コンパイラは前記第２コンピュータプログラムをテーブル及びマシン語コードを発生することにより発生するコード発生部を有し、前記発生されたテーブル及び前記発生されたマシン語コードは、一緒に、前記第２コンピュータプログラムを形成し、前記発生されたマシン語コードは前記テーブルを参照する。該コンパイラは前記第１コンピュータプログラムにおける算術又は論理表現を識別するよう構成され、該表現は少なくとも１つの変数に依存する。前記コード発生部は、前記変数の複数の値に対する前記識別された表現の事前計算された結果を表す１以上のテーブルを発生すると共に、前記第２コンピュータプログラムにおいて前記識別された表現を実施するためのマシン語コードを前記事前計算された結果を表す前記発生された１以上のテーブルにアクセスすることにより発生するよう構成される。前記１以上のテーブルは、ここで述べる構築方法の何れかにより発生することができる。
【００４６】
上記コンパイラは、プログラマを、エラー訂正テーブルを使用することに関連する複雑さから保護するので有利である。特に、複数のエラー訂正コードが使用される場合、複雑さは手により処理することが不可能となる。
【００４７】
本発明の一態様は、１以上の入力の関数を計算する方法に関するものである。該方法は、１以上のルックアップテーブルを記憶するステップであって、前記ルックアップテーブルは入力値を出力値にマッピングし、ルックアップテーブルの入力値は第１エラー訂正コードの第１コードワードのビットサイズ（n1）に等しいビットサイズを有し、前記ルックアップテーブルは、前記第１エラー訂正コード、第２エラー訂正コード、第１エラー閾値及び第２エラー閾値に関して、各々が前記第１エラー訂正コードの同じコードワードに対して最大で第１エラー閾値数のビットだけ相違する何れの２つの入力値も、各々が前記第２エラー訂正コードの同じコードワードに対して最大で第２エラー閾値数のビットだけ相違する対応する出力値にマッピングされるように構築され、前記第１エラー閾値は、少なくとも１、最大で前記第１エラー訂正コードのエラー訂正能力（t1）であり、前記第２エラー閾値が最大で前記第２エラー訂正コードのエラー訂正能力（t2）であるステップと；エンコードされた値に前記１以上のルックアップテーブルを適用するステップを有する前記関数の計算に前記１以上のルックアップテーブルを使用するステップとを有する。
【００４８】
当該計算装置は電子装置である。即ち、該計算装置は、携帯電話等の携帯電子装置、セットトップボックス、コンピュータ等とすることができる。
【００４９】
本発明による方法は、コンピュータ上でコンピュータにより実施される方法として、専用のハードウェアで、又は両方の組み合わせで実施することができる。本発明による方法のための実行可能なコードは、コンピュータプログラム製品上に記憶することができる。コンピュータプログラム製品の例は、メモリ装置、光記憶装置、集積回路、サーバ、オンラインソフトウェア等を含む。好ましくは、該コンピュータプログラム製品は、該プログラム製品がコンピュータ上で実行された場合に本発明による方法を実行するためにコンピュータ読取可能な媒体上に記憶された非一時的プログラムコード手段を有する。
【００５０】
好ましい実施態様において、当該コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行された場合に、本発明による方法の全てのステップを実行するように構成されたコンピュータプログラムコード手段を有する。好ましくは、該コンピュータプログラムはコンピュータ読取可能な媒体上に具現化される。
【００５１】
本発明の上記及び他の態様は、後述する実施態様から明らかとなり、斯かる実施態様を参照して説明される。
【図面の簡単な説明】
【００５２】
【図１】図１は、エラー訂正ルックアップテーブルを図示する概略図である。
【図２】図２は、計算装置を図示するブロック図である。
【図３】図３は、ルックアップテーブルのネットワークを図示するブロック図である。
【図４】図４は、演算子のためにルックアップテーブルを発生する方法を示すフローチャートである。
【図５ａ】図５ａは、演算子のためにルックアップテーブルを発生する方法を示すフローチャートである。
【図５ｂ】図５ｂは、図５ａに対応する例示値を示す。
【図６】図６は、コンパイルを示すフローチャートである。
【図７】図７は、ルックアップテーブルを構築する装置を示すブロック図である。
【発明を実施するための形態】
【００５３】
以下では、異なる図において同一の符号を有する項目は同一の構成的フィーチャ及び同一の機能を有するか又は同一の信号であることに注意されたい。また、詳細な説明において、斯様な項目の機能及び／又は構成が説明された場合は、斯かる機能及び／又は構成の説明は繰り返されない。
【００５４】
本発明は多数の異なる形態の実施態様が可能であるが、本開示は本発明の原理の例示であり、本発明を図示及び説明された特定の実施態様に限定することを意図するものではないと見なされるべきであるとの理解により、図面及び詳細な説明では１以上の特定の実施態様が詳細に図示及び説明される。
【００５５】
図１は、エラー訂正ルックアップテーブルを示す。ルックアップテーブルは、メモリ装置の入力値により制御されるメモリ位置から出力値を取り出すことにより入力値を出力値にマッピングする。
【００５６】
ルックアップテーブル１００は、出力値１２０を有する。各出力値は入力値に対応する。入力値は１１０に概略的に示されている。これら入力値は必ずしも記憶される必要はないことに注意されたい。しばしば、入力値は前後関係から暗黙的となる。例えば、入力値は、典型的に、出力値が記憶されたメモリアドレスに対して固定の関係を有する。通常の状況において、ルックアップテーブルは特定の範囲内の、仕分け順に掲載された全ての値を掲載する。これは、入力値をメモリに記憶する必要がない状況である。入力値を記憶しないことは、記憶空間を典型的には半分に節約する。一方、入力値を明示的に記憶することも、利点を有する。例えば、入力値が記憶される場合、出力値は如何なる（たとえランダムな）順番でもよい。入力値をルックアップすることにより出力値を見付けることができ、当該コードを僅かに簡単にする。しかしながら、重要なことに、入力値を明示的に記憶することにより、当該ルックアップテーブルは値を容易に省略することができる。例えば、当該ルックアップテーブルが何らかの関数又は演算子を表す場合、如何なる不使用な入力値も省略することができる。更に、後述するように、全ての可能性のあるビットパターンは使用しない符号化（エンコード）の使用を可能にする。この場合、入力値を記憶することさえも、記憶要件を減らすことができる。
【００５７】
ルックアップテーブル１００は、エラー訂正コードに関係する特別な特性を有している。コードＣはｎビットの２ｋのコードワードを有している。Ｃにおける如何なる２つのコードワードも少なくともｄビットだけ相違する。該コードのパラメータは、［n,k,d］コードと称される。数ｔ＝floor((d-1)/2)は、訂正することが可能なビットエラーの数を示す。即ち、最大でｔ個のビットが反転した場合、結果としてのビット列に最も近い固有なコード（unique code）が存在する。数ｋはコードの次元（dimension）と称され、数ｄは最小距離と称される。次元（大きさ、寸法）なる語の使用は、線形コードが必要とされることを（好ましいが）示すものではない。ここでは、次元なる語を、当該コードが少なくとも２の次元乗のコードワードを有することを示すために使用する。
【００５８】
数ｔは、当該コードのエラー訂正能力と称される。第１のエラー訂正コードが第２のエラー訂正コードとは相違し得ることを強調する必要がある場合、添え字が付加され、かくして、n1,k1,t1及びn2,k2,t2と称する。しかしながら、ここでは、殆どの場合、同一のコードが使用される例を示し、その場合、該数は省略され得る。２つの等しいコードに関する例が示されるなら、例を２つの異なるコードに一般化することは簡単である。
【００５９】
ルックアップテーブル１００は、同じコードワードから最大でｔビット相違する如何なる２つの入力値も、（恐らくは異なる）コードワードから最大でｔビット相違する対応する出力値を有するという特性を有している。特別なケースでは、出力値は全てコードワードである。後者の場合、同じコードワードから最大でｔビット相違する上記如何なる２つの入力値も、コードワードである同一の出力値を有する。
【００６０】
図１において、入力１１２は同じコードワードから最大でｔビット相違する。例えば、ｔ＝１及びｎ＞＝５の場合、５つの入力１１２は１つのコードワードから５つの異なるビットを反転して得られたものであり得；例えばｔ＞１及びｎ＞３の場合、５つの入力１１２は１つのコードワードから3ビットを反転して得られたものであり得る、等々である。５つの入力の数は一例であり、より多くても又は少なくてもよい。例えば、４又は６又は８等である。複数の入力１１２の各入力は、１３１〜１３８のうちの正確に１つの出力に対応する。
【００６１】
発明者は、エラー訂正テーブルの概念は非常に汎用的で、多くの用途を有することに気付いた。先ず、計算環境が、光攻撃等の攻撃において起き得る様にビットの反転を受け易い場合、エラー訂正テーブルは入力におけるビット反転を自動的に訂正するであろう。同様のことが、余り信頼性のおけないハードウェア、又は例えば高いレベルの放射等の不利な環境において使用されるハードウェアに対しても当てはまる。
【００６２】
他の用途はコードの難読化におけるものである。エラー訂正テーブルを用いる計算は幾つかのエラーに対して抵抗性があるので、コードをリバースエンジニアリングすることを一層困難にする目的でエラーを導入することができる。例えばＸＯＲを制御するランダム数発生器等のエラー追加手段を使用することにより、故意にエラーを導入することができる。しかしながら、斯かるエラーはテーブル自体に導入することもできる。この用途において、出力値はコードワードではなく、複数のビットが反転されたコードワードである。反転されるビットの数は、前記ｔ、即ちエラー訂正限界以下でなければならない。
【００６３】
複数の入力を取り込むエラー訂正テーブルを構築するために、カリー化（currying）を使用することができる。入力を連結することもできる。コードＣが与えられた場合、連鎖
0005851074.tif 000002
もコードである。
【００６４】
図２は、記憶装置２１０を有する計算装置２００を示す。記憶装置２１０は典型的には１以上の不揮発性メモリであるが、ハードディスク、光ディスプレイ等でもあり得る。記憶装置２１０は、ダウンロードされた又はそれ以外で受信されたデータを有する揮発性メモリとすることもできる。計算装置２００はプロセッサ２５０を有する。該プロセッサは、典型的に、メモリに記憶されたコード２５５を実行する。便宜上、該コードはメモリ２１０に記憶することができる。該コードは上記プロセッサに計算を実行させる。装置２００は、入力値を受信し及び／又は結果を送信するためにオプションとしてのＩ／Ｏ装置２６０を有している。Ｉ／Ｏ装置２６０は、ネットワーク接続、取外し可能な記憶装置等とすることができる。
【００６５】
記憶装置２１０は符号化（エンコーディング）ルックアップテーブル２４１を有することができ、該ルックアップテーブルは入力値としてデータワードを取り込むと共に、出力値としての（恐らくは、エラーを含む）コードワードを有する。例えば、入力値は“ｋ”ビットを有する一方、出力値は“ｎ”ビットを有するので、[n,k,d]コードに対応する。
【００６６】
記憶装置２１０はコードワードをデータビットにデコードするための復号（デコーディング）テーブル２４２を有することができる。該テーブルは装置２６０を介しての出力のために使用することができる。
【００６７】
記憶装置２１０は、前述した様に、単一入力ルックアップテーブルを有する。示されたものは、テーブル２２１及び２２２である。例えば、これらテーブルは否定等の単項関数を表すように構成されたものであり得る。
【００６８】
興味深いことに、２以上の入力を持つエラー訂正テーブルを有することも可能であり、これらルックアップテーブルは複数の入力値を出力値にマッピングし、入力値及び出力値はコードワードのビットサイズ（ｎ）と等しいビットサイズを有し、該ルックアップテーブルはエラー訂正コードに関して構築される。対応する入力値が同じコードワードから最大で“ｔ”ビット相違するように相違する２組の複数の入力値が、各々が他の同一のコードワードから最大で“ｔ”ビット相違するような対応する出力値にマッピングされる。図２は、複数入力ルックアップテーブル２３１、２３２を示している。
【００６９】
複数の入力値を有するルックアップテーブルは、種々の方法で表すことができる。１つの有利な方法は、カリー化を使用することである。即ち、１つの入力値を固定することにより、“ｒ”の入力値のためのルックアップテーブルはr-1の入力値しか有さない演算子に縮小される。斯様な一層小さなルックアップテーブルは、固定されたオペランドの全ての値に対して記憶される。他の例として、入力値は連結することができる。後者は、全てのビット列が入力値として許可されるのではない場合に便利である。図２はカリー化方法を使用している。即ち、２３１１〜２３２３は単一入力ルックアップテーブルである。
【００７０】
一実施態様において、当該計算装置は処理の間に以下のように動作することができる。即ち、計算装置２００は入力値を受ける。これら入力値は、例えば符号化テーブル２４１を用いることによりエンコードされる。このように、上記入力値はエンコードされた入力値として得られる。入力値は、エンコードされた入力値として直接得ることもできることに注意されたい。プロセッサ２５０はメモリ２１０内のプログラム２５５を実行する。該プログラムは、上記プロセッサに、符号化された入力値に対して又は結果としての出力値に対してルックアップテーブルを適用させる。ルックアップテーブルは如何なる論理又は算術関数に対しても作成することができ、かくして、如何なる計算も一連のルックアップテーブルを用いて実行することができる。ホワイトボックス暗号法においては、これが、プログラムを難読化するために使用される。この場合、中間値が難読化のために符号化され、従ってルックアップテーブルとなる。これは、エラー訂正特性と有利に組み合わせることができることに注意されたい。
【００７１】
或る時点で、結果の値が見付かる。必要なら、該結果は、例えば復号テーブル２４２を用いてデコードすることができる。しかしながら、該結果はエンコードされた形でエクスポートすることもできる。入力値は入力装置から得ることもでき、出力値はスクリーン上で見せるために使用することもできる。
【００７２】
計算は、エンコードされたデータワード、即ち可能性としてｔ個のエラーを含むコードワードに対して実行される。該計算は、一連のテーブルのルックアップアクセスを適用することにより実行される。使用される入力値は、当該計算装置の外部から入力される入力値であり得るが、前のルックアップテーブルアクセスにより得ることもできる。このようにして、中間結果が得られ、該中間結果は次いで新たなルックアップテーブルアクセスのために使用することができる。或る時点において、上記中間結果の１つは当該関数のエンコードされた結果となる。
【００７３】
図３はテーブルのネットワークを示す。殆どの関数は、テーブルのネットワークとして表すことができる。特に、算術及び論理演算の如何なる構成も、そのように表すことができる。例えば、該テーブルのネットワークは、例えば暗号器（cipher）の構成であり得る。多重テーブルのうちの８個のテーブルが図示されている。１つのテーブルは、入力値を、該入力値のテーブルルックアップにより出力値に変換する。当該関数構成部の外部から入力を受けるための、入力テーブル３１０のうちの３つが図示されている。出力テーブル３３０のうちの１つが図示されている。これら出力テーブル３３０は、一緒に、例えば連結により、当該関数構成部の出力を形成する。中間テーブル３２０のうちの４つが図示されており、該テーブルは、これらテーブルのうちの他のものから少なくとも１つの入力を受けると共に、少なくとも１つの他のテーブルに対する入力として使用する出力を生成する。テーブル３１０、３２０及び３３０は、一緒に、ネットワークを形成する。当該暗号器はブロック暗号器であり得る。即ち、該ブロック暗号器は暗号化のため又は暗号解読のために構成することができる。該ブロック暗号器は、ブロック暗号文、例えばＡＥＳを暗号化する。該構成は特定のキーのためとすることができ、その場合、上記テーブルは該特定のキーに依存し得る。
【００７４】
一例として、テーブル３２２がk1ビットをk2ビットにマッピングする演算子を表すと仮定すると、該ルックアップテーブル３２２は第１エラー訂正コード[n1,k1,d1]及び第２エラー訂正コード[n2,k2,d2]に関して構成されている。該テーブルはn1ビットをn2ビットにマッピングする。実施者は、当該ビット列がデコード可能であるか否かに拘わらずn1ビットの全ての可能性のある列をマッピングするか、又はデコード可能なビット列のみをマッピングするかを選択することができる。最初のオプションを用いる場合、該テーブルはn2＊２n1ビットのサイズを有する。テーブル３２２から入力値を受けるルックアップテーブル３２４は、k2ビットをk3ビットにマッピングする演算子を表す。ルックアップテーブル３２２は、第１エラー訂正コード[n2,k2,d2]に関して構成される。
【００７５】
ルックアップテーブル３２６は、２つの入力及び１つの出力を持つ演算子を表す。単項演算子のためのルックアップテーブルの構成は、２項演算子に拡張することができる。例えば、第２入力は“カリー化（curried out）”することができる。即ち、関数変換技術を参照すると、カリー化は、ｎ個の複数の引数（又はｎ組の引数）をとる関数を、各々が単一の引数を伴う関数の連鎖と見なすことができるように変換する技術である。この方法が用いられた場合、ルックアップテーブル３２６は、複数の単項ルックアップテーブルとして構成することができる。一方、各入力に対して訂正可能なビット列を発生し、結果を連結することもできる。このようにして、該ルックアップテーブルは直接的に発生することができ、単一であるが大きなルックアップテーブルが得られる。ルックアップテーブルの配置は構成に基づいて相違し得るが、これらは等しいサイズ及び同一の特性を有する。複数の入力値が同一のエラー訂正コードに従ってエンコードされる必要はないことに注意されたい。
【００７６】
図４は、エラー訂正関数を作成する方法を示す。図４及び図５の例において、以下では[7,4,3]ハミングコードを使用する。該コードワードは、７ビット長であり、４データビットをエンコードする。該コードは単一のエラーを訂正することができる。即ち、ｔ＝１である。コードワードが形式d1 d2 d3 d4 p1 p2 p3を有する構成を使用し、ここで、d1〜d4はデータビットであり、p1=d1+d2+d4, p2=d2+d3+d4, p3=d1+d3+d4はパリティビットであり、＋はモジュロ２加算を示す。
【００７７】
エラー訂正ルックアップテーブルが望ましい演算子が与えられたと仮定する。当該関数は２入力と仮定するが、１又は３以上も可能である。該演算子は、plus、mod及びmul等の通常の演算子であり得る。しかしながら、該演算子はアプリケーションに固有のもの、例えばＡＥＳのＳボックスでもあり得る。
【００７８】
以下の説明では、当該演算子は２つの入力値をとる二値演算子であると仮定する。一例として、算術加算が使用される。該例を扱いやすく保つために、入力値は４ビット幅であり、エンコードされた入力値は７ビット幅であるとする。実際には、大幅に大きな入力値及び／又は符号化を使用することができるが、これは、それに応じて大幅に大きなテーブルとなる。
【００７９】
ステップ４１０において、コードワードのビットサイズ（ｎ）のビット列が発生される。該発生されたビット列は、最終ルックアップテーブルに対する可能性のある入力値である。当該例においては、ビット列1011001及び0110111が発生される。前者はコードワードであるが、後者はそうでないことに注意されたい。該発生されたビット列は、例えばエラー訂正アルゴリズムを用いてデコードされ、デコードされた発生ビット列を得るようにする。該デコードされたビット列は、入力値ビットサイズ（ｋ）（ここでは４ビット）のものである。第２の発生ビット列におけるエラーは訂正されていることに注意されたい。この場合、即ち[7,4,3]ハミングコードによれば、所謂完全コードが使用される。完全コードは、如何なる発生ビット列も固有の復号ビット列にデコードされ得るという利点を有している。非完全コードを使用することができる。この場合は、復号ビット列から最も近い復号ビット列を選択するために、タイブレーカが使用される。該タイブレーカは決定性であり、例えば順序付け（例えば、辞書式順序付け）を強要する。他の例として、幾つかのビット列はデコードすることができないが、代わりに、“復号エラー”が通知され、適切な処理がなされる。これはテーブルにおける注釈とすることもでき、例えば、デコード不可能な入力ビット列に対する出力としてデコード不可能なビット列を付与することができる。好ましくは、上記デコード不可能なビット列は、不注意にキーの相関等を導入してしまうことを避けるためにランダムとする。
【００８０】
当該演算子は、上記発生ビット列のデコードの結果に適用される。この場合、２つのビット列が発生されているので、該演算子は、これらビット列の両方に適用される。この場合、4ビットに対する加算が実行される。その結果は、コードワードを得るためにエンコードされる。オプションとして、最大でｔビットまでのエラーが当該コードワードに加えられる。この場合、当該コードワードの１ビットを反転することができる。最後に、ルックアップテーブルは、上記発生ビット列が、オプションとしてのビットエラーを含む上記演算子のデコードされた結果にマッピングされるように構成される。
【００８１】
上記処理は、全ての所望のビット列が発生されるまで繰り返される。典型的には、コードビットサイズ（ｎ）の全てのビット列が順番に発生される。当該演算子が複数の入力を有する場合、複数のビット列が発生される。
【００８２】
この例において、当該方法は7ビットの２つのビット列の全ての組み合わせを発生することができる。従って、２１４のビット列が発生される。その結果が、ルックアップテーブル４５２に掲載されている。左側において４５４に示されるものは入力値であり、右側において４５６に示されるものは対応する出力値である。入力値は必ずしも明示的に掲載される必要はないことに注意されたい。特に、全てのビット列が発生される場合、入力側は省略することができる。
【００８３】
図５ａは、エラー訂正テーブルを構築する他の方法を示す。図５ｂは、如何にして図４におけるのと同一のテーブルエントリが最終的ルックアップテーブルに現れ得るかを示すことにより、どの様にして同一のテーブルを構築することができるかを示している。
【００８４】
ステップ５１０において、入力ビットサイズ（ｋ）のビット列が発生される。発生されたビット列は、ステップ５３０において該発生ビット列に演算子を適用すると共に、該結果をステップ５４０においてエンコードすることにより使用される。図４におけるのと同様に、オプションとして、当該コードワードには意図的なエラー（ｔまで）を加えることができる。前記発生ビット列は、ステップ５２０においても符号化（即ち、コードワードとしての符号化）を発生するために使用される。ステップ５６０において、訂正可能なエラーパターンが発生される。全ての可能性のある入力値が当該ルックアップテーブルにより表される必要はない。代わりに、入力値を、コードワードと限られた組の訂正可能な入力値とを加えたものに限定することができる。当該コードが完全であり、上記訂正可能な入力値の組が、ｔまでの１のビットを持ち、残りが零である全てのパターンに等しい場合、結果は同じである。しかしながら、ｔ未満のエラーを加えることも可能である。当該コードが不完全であり、前記訂正可能な入力値の組が、ｔまでの１のビットを持ち、残りが零である全てのパターンに等しい場合、該入力値の組は厳密には全ての可能性のあるビット列よりも小さい。ステップ５６０において加えられる訂正可能なビットパターンとステップ５４０において加えられるエラーとの間には対応性が存在しなければならない。
【００８５】
図４及び図５の両方において、コードワードビットサイズ（ｎ）の全ての訂正可能なビット列の部分組が発生され、該発生された訂正可能なビット列をデコードした結果に当該演算子が適用され、その結果が、恐らくは１以上のエラーを加えて、エンコードされる。発生された訂正可能なビット列が、オプションとして１以上のエラーを含むエンコードされたコードワードにマッピングされたルックアップテーブルが構築される。
【００８６】
図６は、コンパイル方法６００をフローチャートとして示す。ステップ６１０において、入力部により第１コンピュータプログラムが入力される。ステップ６２０において、字句解析部により、例えばトークンを識別するために、字句解析が実行される。可能性として、マクロ展開等の処理も実行される。ステップ６３０において、当該プログラムは構文解析部により構文解析される。例えば、該構文解析部は、当該第１プログラムのプログラミング言語の形式文法に従って構文解析ツリーを発生する。該構文解析部は当該プログラムにおける異なる言語構成体を識別し、適切なコード発生ルーチンを呼び出す。特に、演算子又は複数の演算子が識別される。その場合、ステップ６４０においてコード発生部によりコード発生が実行される。コード発生の間において、何らかのコード及び、必要なら、付随するテーブルが発生される。該付随するテーブルはエラー訂正テーブルである。発生されるコードは、１以上のルックアップテーブルにより置換されるので、当該演算子を含む必要はなく、通常は含まないであろう。例えば、構文解析部は、加算演算子を識別し、これを、該加算命令のためのルックアップテーブルに及び該ルックアップテーブルを正しい値に適用するための発生コードに変換する。
【００８７】
ステップ６５５において、発生されたテーブルはテーブルベースに統合される。何故なら、幾つかのテーブルは複数回発生されることが生じ得、その場合、これらを複数回記憶する必要はないからである。例えば、加算テーブルが必要とされ、１回のみ発生され得る。全てのコードが統合され、全てのテーブルが統合された場合に、当該コンパイルは完了される。オプションとして、最適化ステップが存在し得る。
【００８８】
典型的に、当該コンパイラはエンコードされるドメイン、即ち当該プログラムにおける全ての値又は少なくとも何らかの基準に対応する全ての値がエンコードされる（即ち、コードワードビットサイズ（ｎ）を有する）部分、を使用する。符号化されるドメインにおいて、演算はルックアップテーブル実行により実行することができる。エンコードされるドメインに入った場合、全ての値はエンコードされ、エンコードされるドメインを去った場合、値はデコードされる。基準は、当該値が機密情報（例えば、暗号キー）に相関される、又は依存するということであり得る。
【００８９】
当該コンパイラを作成する興味ある方法は以下の通りである。ステップ６３０において、中間コンパイルが実行される。これは、例えばレジスタ転送語等の中間言語とすることができるが、マシン語コードコンパイルとすることもできる。このことは、図６のステップ６１０〜６３０に対しては通常のコンパイラを使用することができ、エラー訂正テーブルを作成しないことを意味する。しかしながら、ステップ６４０では、コードの発生が上記中間コンパイルに基づいて実行される。例えば、マシン語コードが使用された場合、各命令は、当該命令の対応する演算子無し実施化、即ち当該命令のテーブルに基づく実施化により置換される。これは、当該コンパイラを作成する特に素直な方法を表している。図６は、マシン語ではなく第２プログラミング言語を生成するコンパイラを発生するために使用することもできる。
【００９０】
一実施態様において、当該コンパイラは第１コンピュータプログラミング言語で書かれた第１コンピュータプログラムを第２コンピュータプログラムにコンパイルするコンパイラであり、該コンパイラは上記第２コンピュータプログラムをテーブル及びマシン語コードを発生することにより発生するコード発生部を有し、該発生されたテーブル及び該発生されたマシン語コードは一緒に上記第２コンピュータプログラムを形成し、上記の発生されたマシン語コードは上記テーブルを参照する。該コンパイラは、前記第１コンピュータプログラムにおける算術又は論理表現（式）を識別するように構成され、該表現は少なくとも１つの変数に依存し、前記コード発生部は上記変数の複数の値に関して上記の識別された表現の事前に計算された結果を表す１以上のエラー訂正テーブルを発生すると共に、上記の識別された表現を第２コンピュータプログラムで実施するためのマシン語コードを、上記の発生された事前に計算された結果を表す１以上のテーブルにアクセスすることにより発生するように構成される。理想的には、上記の識別された表現を実施するために発生されるマシン語コードは、算術又は論理マシン命令自体、少なくとも機密情報に関係する算術又は論理マシン命令は含まないものとする。
【００９１】
このことは、第２コンピュータプログラムのサイドチャンネル漏れを低下させる。何故なら、該第２コンピュータプログラムは、より少ない算術又は論理演算子か含まないからである。理想的には、全ての算術及び論理表現及び部分表現（部分式）がテーブルアクセスにより置換されるようにする。上記算術及び論理表現及び部分表現を置換する命令が存在しないので、これらは如何なる情報も漏らし得ない。上記テーブルは事前に計算される。即ち、該テーブルに含まれる算術又は論理動作を実行するために消費される電力は、当該プログラムを実行する間には見えない。該テーブルはエラー訂正的であるので、当該プログラムも障害注入攻撃に対して一層抵抗性のものとなる。当該プログラムに意図的なエラーが加えられた場合、実行の間において動的にも、又はルックアップテーブルにおいても、内部変数と外部結果との間の関係は更に不明瞭にされ、かくして、リバースエンジニアリングを一層困難にさせる。
【００９２】
図７は、ルックアップテーブルを構築する装置７００を示す。該装置は、訂正可能ビット列発生器７１２と、復号ビット列発生器７１４とを有している。発生器７１２及び７１４は、一緒に動作して、ルックアップテーブルが入力として受けなければならない全てのビット列、即ち上記訂正可能なビット列及び対応するエンコードされていないビット列を生成する。発生器７１２は、コードワードビットサイズ（n1）のビット列を生成する。発生器７１４は演算器入力ビットサイズ（k1）のビット列を生成する。両発生器は第１エラー訂正コードに対応する。該対は、ここで説明するルックアップテーブルを構築する方法の何れを使用することもできる。
【００９３】
発生器７１４の出力は演算器７３０により使用される。演算器７３０は、エンコードされていない、即ちデコードされたビット列に対して演算子を実行するように構成される。演算器７３０の出力は、k2ビットを有する。サイズk1はk2に等しくすることができる。該演算器の結果は、エンコーダ７４０により第２エラー訂正コードのためにエンコードされる。最後に、収集器７５０は、発生器７１２から入力される訂正可能なビット列と、エンコーダ７４０の対応するエンコードされた結果とを収集して、ルックアップテーブルを生成する。結果としてのルックアップテーブルに対する入力と、出力の位置との間の関係が、該収集器が第１エラー訂正コードのコードワードサイズに等しいサイズの全ビット列を実際に含んでいるという理由で、容易に得ることができる場合、上記訂正可能なビット列は当該ルックアップテーブルに含まれることを要さない。
【００９４】
上記収集器は、ビットエラーの幾つか又は全てを加えることができる。ビットエラーが加えられた位置は、訂正可能なビット列に依存する。例えば、入力ビット列が位置ｉにビットエラーを有する場合、ビットエラーは第２エンコード訂正コードにおける位置i+1に加えられる。
【００９５】
以下には、一実施態様の更なる洗練例が示される。プログラム内の最も普通の命令は、演算であり、演算の結果を記憶する。これらの演算は、加算（＋）、減算（−）及び乗算（＊）等の良く知られた演算を含む。当該コンパイラは、これらの演算を目標とする。即ち、該コンパイラは、何らかの高いレベルの言語で書かれた表現を、これらの既知の演算に分解する。テーブルは、全ての関連する演算に対して、即ち、当該プログラムにおける演算及び、ＶＭが使用されるなら、当該プログラムが実行されるＶＭの演算の両方に対して使用することができる。セキュリティは、これらのテーブルに特別なフィーチャ又は特性を付与することにより更に改善することができる。
【００９６】
各演算に対してテーブルを使用することができる。テーブルは演算に従って定義される。エンコーディング無しで、例えば、単項演算子Opmに対してはtableOpm[x]==Opm(x)であり、２項演算子Opdに対してはtableOpd[x][y]==Opd(x,y)である。非単項演算に対しては、当該コンパイラはテーブルに対するアクセスを複数アクセスとして実施することができることに注意されたい（カリーとして知られている処理）。即ち、X=tableOpd[x]にX[y]が後続する。メモリ的に、８ビットのデータ経路の場合、１４の２項演算は１メガバイトに等しいメモリ使用を要するが、これは許容可能と考えられることに注意されたい。幾つか又は全てのテーブルはＲＯＭに記憶することができ、幾つか及び／又は全てのテーブルは、揮発性又は非揮発性によらず、他のメモリに記憶することができることに注意されたい。エラー訂正エンコーディングを加えることは、上記式におけるエンコーディングを置換することにより実行することができる。
【００９７】
コンパイラ／リンカ及びＶＭの一体化は、演算の使用を該演算のテーブルアクセスにより置換することにより維持される。基となるプラットフォームは、ジャンプ命令並びにレジスタ及びメモリに対する／からの書込／読出のためにしか使用する必要がない。
【００９８】
もっと進んだ実施態様では、コンパイラは全部の表現をテーブルとして実施することができる。例えば、式Ｘ２＋Ｙ２は、２つの乗算と１つの加算により実施することができ、結果として少なくとも３つ（カリー化される場合は、それ以上）の演算となる。しかしながら、これはＸ２＋Ｙ２のテーブルとして実施し、このテーブルのアクセスにコンパイルすることもできる。この結果は、１つの（カリー化される場合は、２つ）テーブルアクセスとなる。
【００９９】
コンパイルされたプログラムの実行のためにＶＭが使用される場合、コンパイラ／リンカ及びＶＭの間の一体性は、当該テーブルをＶＭに受け渡すことにより維持することができる。ラベル付けされたテーブルが、当該コンパイラの出力及び当該ＶＭに対する入力となる。当該コンパイラにより供給されるコードにおいて、これらのラベルが参照される。このことはメモリ的に改善となり得る。何故なら、使用されない演算のテーブルは省略することができるからである。一実施態様において、当該コンパイラは、ある値を１、２又は複数の数値入力に割り当てる表現（式）を第１プログラムで識別するための表現ユニットを有し、前記コード発生器は上記数値入力の全ての値に対する上記表現の結果を表すテーブルを発生するように構成される。興味深いことに、該表現は既存のマシンコード命令に等しくなる必要はない。
【０１００】
興味深いことに、特定のＶＭプログラミング言語のプログラムを実行するよう構成された仮想マシンは、エラー訂正テーブルを使用するようにコンパイルすることができる。このこと自体が、ＶＭ上で実行される如何なるプログラムにも、エラー訂正特性の幾つかを付与するであろう。しかしながら、当該プログラムは、何らかの他の言語のプログラムをＶＭプログラミング言語にコンパイルすることによっても得ることができる。後者のコンパイルは、エラー訂正テーブルを使用するようにコンパイルすることもできる。
【０１０１】
例えば、ＶＭ自体を実施化するために、エラー訂正により拡張された仮想マシンのテーブル化された命令を使用することができる。これを、エラー訂正メカニズムで加算命令を拡張することに関して説明する。他の命令も同様に扱うことができる。
【０１０２】
最初のステップは、エラー訂正の特性を、当該命令（本例では、加算命令（add_instruction））に追加することであり得る。Ｍを、ドメインＹを一層大きなドメインＸに埋め込むこととし、Ｍ−１を、ドメインＸからＹへのマッピングとする。ここで、Ｘの値Ｍ(ν)における小さなエラーｅもνにマッピングして戻る。短くは、
0005851074.tif 000003
である。ここで、
0005851074.tif 000004
はＸにおける加算を示す。典型的に、Ｘは等しい長さの二値ビット列からなり、
0005851074.tif 000005
はビット列のビット単位のモジュロ２加算を示し、エラーｅは、僅かの非零成分しか有さない場合（又は、コーティング専門用語では、小さなハミング重を有する場合）“小さい”。訂正したいエラーの集合をＥにより示し、集合
0005851074.tif 000006
をＳにより示す。当該エラー訂正コーティングは、Ｓにおける各要素ｓを、Ｙにおけるν及びＥにおけるｅの場合に
0005851074.tif 000007
と固有な方法で書くことができるように設計される。この場合、
0005851074.tif 000008
となる。ＸにおけるＳにはない要素ｓに対しては、Ｍ−１(ｘ)は定義されない。
【０１０３】
小例として、Y={0,1,2,3}, X={0,1}5及びE={00000, 10000, 01000, 00100, 00010, 00001}（従って、１ビットのエラーを訂正したい）とする。ＭをM(0)=00000, M(1)=01110, M(2)=10101及びM(3)=11011により定義する。
明らかに、
0005851074.tif 000009
となる。
【０１０４】
検査により、
0005851074.tif 000010
の各要素は、Ｙにおけるｕ及びＥにおけるｅにより
0005851074.tif 000011
と固有な形態で書くことができることが分かった。このように、集合Ｓはデコード可能なビット列の集合である。
【０１０５】
ＳにはないＸの８個の要素が存在する（即ち、11000, 10110, 01101, 00011, 10010, 11100, 00111, 01001）。Ｍ−１は、これらの８個の要素に対しては定義されない。
【０１０６】
前記難読化方法と同様に、Ｓにおける全てのｘ及びｙに対して：
add(x,y)==M(M-1(x)+M-1(y))
を導入する。
【０１０７】
上記関数add(x,y)は、ｘ及びｙの少なくとも一方がＳにない場合、定義されない。add(x,y)が斯様な無効な入力により要求された場合、この命令は実行されず、エラー標示が発生する。
【０１０８】
このようにして、オリジナルのaddをエラー訂正特性により拡張し、当該表現がＯ又はＭは別として等しいことに留意する。
【０１０９】
上記小例においては、２ビットにより表され得る数が５ビットのビット列にマッピングされ、単一のビットの訂正を可能にした。一般的に、ｋビットにより表すことができる数を長さｋ＋ｒのビット列にエンコードすることができ、１つのエラービットが訂正され得るようにし、ここで、ｒはｋ＋ｒ≦２ｒ−１である。従って、例えば、ｋ＝８ビットの数の場合、ｒ＝４冗長ビットであり、ｋ＝３２ビットの数の場合、ｒ＝６の冗長ビットであり得る。後者の場合、エンコードされたビット列は長さ３８を有するので、集合Ｅは３９の要素を有し、メモリサイズは係数３９により増加される。
【０１１０】
特には請求項に及び／又は図４、図５及び図６を参照して記載されたもの等の、ここに記載された方法を実行する多数の異なる方法が可能であることに注意されたい。このことは当業者にとり明らかであろう。例えば、ステップの順番は変えることができ、幾つかのステップは並行して実行することができる。更に、ステップの間に他の方法ステップを挿入することもできる。挿入されるステップは、ここで説明したもののような当該方法の改良を表し得るか、又は当該方法とは関係しないものであり得る。例えば、ステップ５２０及び５３０又は６２０及び６３０等は、少なくとも部分的に並行して実行することができる。更に、或るステップは、次のステップが開始される前に、完全に完了していなくてもよい。
【０１１１】
本発明による方法は、ソフトウェアを使用して実行することができ、斯かるソフトウェアはプロセッサシステムに方法４００、５００又は６００を実行させる命令を有する。ソフトウェアは、当該システムの特定の下位部分により行われるステップのみを含むことができる。該ソフトウェアは、ハードディスク、フロッピー（登録商標）ディスク、メモリ等の適切な記憶媒体に記憶することができる。該ソフトウェアは、有線若しくは無線を介しての信号として、又は例えばインターネット等のデータネットワークを使用して送信することができる。該ソフトウェアは、ダウンロードのために及び／又はサーバ上での遠隔使用のために利用可能とすることができる。
【０１１２】
本発明は、本発明を実施させるように構成されたコンピュータプログラム、特には担体上又は内のコンピュータプログラムにも及ぶと理解される。当該プログラムは、ソースコード、オブジェクトコード若しくは部分的にコンパイルされた形態等のソースとオブジェクトとの中間のコードの形態とするか、又は本発明による方法の実施に使用するのに適した何らかの他の形態とすることができる。コンピュータプログラム製品に関する一実施態様は、記載された方法の少なくとも１つの処理ステップの各々に対応するコンピュータ実行可能な命令を有する。これらの命令は、サブルーチンに分割することができ、及び／又は静的若しくは動的にリンクされ得る１以上のファイルに記憶することができる。コンピュータプログラム製品に関する他の実施態様は、記載されたシステム及び／又は製品の少なくとも１つの手段の各々に対応するコンピュータ実行可能な命令を有する。
【０１１３】
上述した実施態様は本発明を限定するというよりは解説するものであり、当業者であれば多数の代替実施態様を設計することができることに注意すべきである。
【０１１４】
尚、請求項において括弧内の如何なる符号も当該請求項を限定するものと見なしてはならない。また、“有する”なる動詞及びその活用形は、請求項に記載されたもの以外の構成要素又はステップの存在を排除するものではない。また、単数形の構成要素は、複数の斯様な構成要素の存在を排除するものではない。また、本発明は、幾つかの別個のエレメントを有するハードウェアにより、及び適切にプログラムされたコンピュータにより実施することができる。また、幾つかの手段を列挙する装置の請求項において、これら手段の幾つかは全く同一のハードウェアにより具現化することができる。また、特定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これら手段の組み合わせを有利に使用することができないということを示すものではない。
【符号の説明】
【０１１５】
１００    ルックアップテーブル
１１０    テーブルに対する入力（実際にメモリに記憶されるものではない）
１１２    コードワードから最大で“ｔ＝floor((d-1)/2)”ビット相違する複数の入力
１２０    テーブル内容
１３１〜１３８    入力１１２に対するテーブルの結果
２００    計算装置
２１０    記憶装置
２２１，２２２    単一入力ルックアップテーブル
２３１，２３２    複数入力ルックアップテーブル
２３１１〜２３２３    単一入力ルックアップテーブル
２４１    符号化ルックアップテーブル
２４２    復号ルックアップテーブル
２５０    コンピュータプロセッサ
２５５    マシン語コード
２６０    Ｉ／Ｏ装置
３１０    入力テーブル
３２０    中間テーブル
３３０    出力テーブル
４５２    ルックアップテーブル
４５４    入力部
４５６    出力部
５５２    ルックアップテーブル
７００    ルックアップテーブルを構築する装置
７１２    訂正可能ビット列発生器
７１４    復号ビット列発生器
７３０    演算器
７４０    第２エラー訂正コードのためのエンコーダ
７５０    収集器
【図１】
0005851074.tif 000012
【図２】
0005851074.tif 000013
【図３】
0005851074.tif 000014
【図４】
0005851074.tif 000015
【図５ａ】
0005851074.tif 000016
【図５ｂ】
0005851074.tif 000017
【図６】
0005851074.tif 000018
【図７】
0005851074.tif 000019