(57)【特許請求の範囲】
【請求項１】
電子ストレージと、前記ストレージに結合される電子プロセッサとを有する計算装置であって、前記ストレージはテーブルネットワークの系列を記憶し、前記プロセッサは、前記テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力とグローバル状態入力とに対して繰り返される関数を計算するよう構成され、
前記系列のテーブルネットワークは、対応するデータ関数と状態関数とについて構成され、前記対応するデータ関数に従ってデータ入力をデータ出力にマッピングし、状態関数に従って状態入力を状態出力に同時にマッピングするよう構成され、
前記電子プロセッサは、前記テーブルネットワークの系列の適用を繰り返すよう構成され、前記繰り返し適用されるテーブルネットワークのテーブルネットワークを前記グローバルデータ入力とグローバル状態入力とに適用し、前記繰り返しの後続のテーブルネットワークを前記系列の前のテーブルネットワークのデータ出力と状態出力とに適用し、前記系列の繰り返される適用は、前記グローバルデータ入力に対してグローバルデータ関数を決定し、前記グローバル状態入力に対してグローバル状態関数を決定し、これにより、中間データ出力と中間状態出力とを取得し、
前記電子ストレージは更に、前記系列のテーブルネットワークになされた変更に対処するため前記テーブルネットワークの系列と連携するよう構成される保護テーブルネットワークを記憶し、前記保護テーブルネットワークは、前記中間状態出力とグローバル状態入力とを入力として受信するよう構成され、前記保護テーブルネットワークは、前記グローバル状態入力に適用されるグローバル状態関数が前記中間状態出力を生成することを検証するよう構成される計算装置。
【請求項２】
前記系列のテーブルネットワークの単一の繰り返しは、前記グローバル状態入力に対する単一繰り返し状態関数を決定し、前記単一繰り返し状態関数は冪等又は冪零である、請求項１記載の計算装置。
【請求項３】
前記単一繰り返し状態関数は恒等式であり、前記保護テーブルネットワークは、前記グローバル状態入力が前記中間状態出力に等しいことを検証するよう構成される、請求項２記載の計算装置。
【請求項４】
前記保護テーブルネットワークは、系列の繰り返し数に応じて更なる入力を受信するよう構成される、請求項１記載の計算装置。
【請求項５】
前記保護テーブルネットワークは更に、前記中間データ出力を入力として受信し、保護されたデータ出力と保護された状態出力とを出力として生成するよう構成され、
前記検証が成功した場合、前記保護されたデータ出力は、前記中間データ出力に等しく、前記検証が前記グローバルデータ入力と前記グローバル状態入力との少なくとも一部の値について不成功である場合、前記保護されたデータ出力は前記中間データ出力に等しくない、請求項１記載の計算装置。
【請求項６】
前記保護テーブルネットワークは、状態テーブルネットワークを有し、
前記状態テーブルネットワークは、前記グローバル状態関数について構成され、前記状態入力を検証状態出力にマッピングするよう構成され、
前記保護テーブルネットワークは、検証状態出力が前記中間状態出力に等しいことを検証するよう構成される、請求項１記載の計算装置。
【請求項７】
前記状態テーブルネットワークは、前記系列におけるテーブルネットワークより少ないテーブルを一緒に有する、請求項６記載の計算装置。
【請求項８】
前記系列におけるテーブルネットワークに対応する全ての状態関数は等しい、請求項１記載の計算装置。
【請求項９】
前記グローバルデータ入力とグローバル状態入力とは、一緒に単一のグローバル入力に符号化され、
前記系列のテーブルネットワークのデータ入力と状態入力とは、一緒に単一の入力に符号化され、
前記系列のテーブルネットワークのデータ出力と状態出力とは、一緒に単一の出力に符号化され、
前記中間データ出力と前記中間状態出力とは、一緒に単一の中間出力に符号化され、
前記保護されたデータ出力と前記保護された状態出力とは、一緒に単一の保護された出力に符号化される、請求項１記載の計算装置。
【請求項１０】
電子ストレージと、前記ストレージに結合される電子プロセッサとを有する計算装置であって、前記ストレージは、テーブルネットワークの系列を記憶し、前記プロセッサは、前記テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力とグローバル状態入力とに対して関数を計算するよう構成され、
前記系列のテーブルネットワークは、対応するデータ関数と状態関数とについて構成され、前記対応するデータ関数に従ってデータ入力をデータ出力にマッピングし、状態関数に従って状態入力を状態出力に同時にマッピングするよう構成され、
前記電子プロセッサは、前記テーブルネットワークの系列を適用するよう構成され、前記適用されるテーブルネットワークのテーブルネットワークを前記グローバルデータ入力とグローバル状態入力とに適用し、後続のテーブルネットワークを前記系列の前のテーブルネットワークのデータ出力と状態出力とに適用し、前記系列の適用は、前記グローバルデータ入力に対してグローバルデータ関数を決定し、前記グローバル状態入力に対してグローバル状態関数を決定し、これにより、中間データ出力と中間状態出力とを取得し、
前記電子ストレージは更に、前記系列のテーブルネットワークになされた変更に対処するため前記テーブルネットワークの系列と連携するよう構成される保護テーブルネットワークを記憶し、前記保護テーブルネットワークは、前記中間状態出力とグローバル状態入力とを入力として受信するよう構成され、前記保護テーブルネットワークは、前記グローバル状態入力に適用されるグローバル状態関数が前記中間状態出力を生成することを検証するよう構成され、
前記グローバル状態関数は恒等式であり、又は
前記系列は、前記グローバル状態関数を計算するための２つより多くのテーブルネットワークを有し、前記保護テーブルネットワークは単一の状態テーブルネットワークを有し、前記状態テーブルネットワークは、前記グローバル状態関数について構成され、前記状態入力を検証状態出力にマッピングするよう構成され、前記保護テーブルネットワークは、検証状態出力が前記中間状態出力に等しいことを検証するよう構成され、前記状態テーブルネットワークは前記系列におけるテーブルネットワークより少ないテーブルを一緒に有する計算装置。
【請求項１１】
テーブルネットワークの系列を利用する計算方法であって、当該方法は、前記テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力とグローバル状態入力とに対して繰り返される関数を計算するよう構成され、
前記系列のテーブルネットワークは、対応するデータ関数と状態関数とについて構成され、前記対応するデータ関数に従ってデータ入力をデータ出力にマッピングし、状態関数に従って状態入力を状態出力に同時にマッピングするよう構成され、
当該方法は、
前記テーブルネットワークの系列を繰り返し適用するステップであって、前記繰り返し適用されるテーブルネットワークのテーブルネットワークを前記グローバルデータ入力とグローバル状態入力とに適用し、前記繰り返しの後続のテーブルネットワークを前記系列の前のテーブルネットワークのデータ出力と状態出力とに適用し、前記系列の繰り返される適用は、前記グローバルデータ入力に対してグローバルデータ関数を決定し、前記グローバル状態入力に対してグローバル状態関数を決定し、これにより、中間データ出力と中間状態出力とを取得する、適用するステップと、
前記系列のテーブルネットワークになされた変更に対処するため前記テーブルネットワークの系列と連携するよう構成される保護テーブルネットワークを適用することによって、前記グローバル状態入力に適用されるグローバル状態関数が前記中間状態出力を生成することを検証するステップであって、前記保護テーブルネットワークは、前記中間状態出力とグローバル状態入力とを入力として受信するよう構成され、前記保護テーブルネットワークは、前記グローバル状態入力に適用されるグローバル状態関数が前記中間状態出力を生成することを検証するよう構成される、検証するステップと、
を有する方法。
【請求項１２】
データ関数の系列を取得し、テーブルネットワークの第１の系列、保護テーブルネットワーク及びコンピュータコードを生成するよう構成されるコンパイラであって、前記第１の系列と保護テーブルネットワークとは電子ストレージに記憶されるよう構成され、前記コンピュータコードは、前記電子ストレージに結合される電子プロセッサ上で実行されるよう構成され、前記コンピュータコードは、前記テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力とグローバル状態入力とに対して繰り返される関数を計算するよう構成され、
前記系列のテーブルネットワークは、前記データ関数の系列の対応するデータ関数と状態関数とについて構成され、前記対応するデータ関数に従ってデータ入力をデータ出力にマッピングし、状態関数に従って状態入力を状態出力に同時にマッピングするよう構成され、
前記コンピュータコードは、前記テーブルネットワークの系列の適用を繰り返すよう構成され、前記繰り返し適用されるテーブルネットワークのテーブルネットワークを前記グローバルデータ入力とグローバル状態入力とに適用し、前記繰り返しの後続のテーブルネットワークを前記系列の前のテーブルネットワークのデータ出力と状態出力とに適用し、前記系列の繰り返される適用は、前記グローバルデータ入力に対してグローバルデータ関数を決定し、前記グローバル状態入力に対してグローバル状態関数を決定し、これにより、中間データ出力と中間状態出力とを取得し、
前記保護テーブルネットワークは、前記系列のテーブルネットワークになされた変更に対処するため前記テーブルネットワークの系列と連携するよう構成され、前記保護テーブルネットワークは、前記中間状態出力とグローバル状態入力とを入力として受信するよう構成され、前記保護テーブルネットワークは、前記グローバル状態入力に適用されるグローバル状態関数が前記中間状態出力を生成することを検証するよう構成されるコンパイラ。
【請求項１３】
コンピュータプログラムがコンピュータ上で実行されると、請求項１１の全てのステップを実行するよう構成されるコンピュータプログラムコード手段を有するコンピュータプログラム。
【請求項１４】
コンピュータ可読媒体上に実現される請求項１２又は１３記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子ストレージと、テーブルネットワークを記憶する当該ストレージに結合される電子プロセッサであって、テーブルネットワークを適用することによってファンクションを計算するよう構成されるプロセッサとを有する計算装置に関する。
【０００２】
本発明は更に、計算方法、コンパイラ及び対応するコンピュータプログラムに関する。
【背景技術】
【０００３】
従来の暗号化では、攻撃者がセキュアシステムの入出力値へのアクセスのみを取得することが典型的に想定された。例えば、攻撃者は、システムに入る平文を観察し、システムから出る暗号文を観察することができる。攻撃者は、おそらく計算量の大きな方法を利用しさえしてこのような入力／出力ペアを解析することによって利益を取得しようとすることが可能であるが、彼は入力／出力動作を実現したシステムへの直接的なアクセスを有しているとは考えられなかった。
【０００４】
最近、攻撃者が実装について知っていることが想定される脅威モデルを考慮することが必要になってきている。例えば、サイドチャネル解析及びリバースエンジニアリングの脅威を考慮するかもしれない。さらに、セキュリティ問題に以前には最も関連した懸念は、プライバシなどの他の分野に拡がってきた。暗号鍵などのセキュリティ情報を処理する暗号化システムは最大の懸念を残しているが、プライバシ関連情報を処理するものなどの他のプログラムの保護がまた重要になってきている。
【０００５】
コンピュータシステムは、いわゆるサイドチャネルを介し情報を漏洩することが長く知られてきた。コンピュータシステムの入出力動作の観察は、コンピュータシステムにより利用される秘密鍵などの機密情報に関する何れの有用な情報を提供しないかもしれない。しかしながら、コンピュータシステムは、それの電力消費又は電磁放射など、観察可能な他のチャネルを有し、これらのチャネルはサイドチャネルとして参照される。例えば、異なる命令により消費される電力の小さな変動及び命令の実行中に消費される電力の変動が測定されてもよい。測定された変動は、暗号鍵などの機密情報と相関される。観察可能であって意図された入出力動作を超えた秘密情報に関するこのような付加情報は、サイドチャネルと呼ばれる。サイドチャネルを介し、コンピュータシステムはその使用中に秘密情報を“漏洩”しうる。サイドチャネルの観察及び解析は、入出力動作のみの暗号解読から取得されるものより良好な情報へのアクセスを攻撃者に与えうる。１つの既知のタイプのサイドチャネル攻撃は、いわゆる、差分電力解析（ＤＰＡ）である。
【０００６】
サイドチャネル問題に対する現在のアプローチは、計算におけるランダム性を導入する。例えば、プログラムダミー命令を実行する中間の本物の処理が、電力消費とプログラムが実行されるデータとの間の関係を曖昧にするため挿入されてもよい。
【０００７】
コンピュータに対する更に強力な攻撃は、いわゆる、リバースエンジニアリングである。多数のセキュリティシナリオの攻撃者は、コンピュータへの完全なアクセスを有するかもしれない。これは、プログラムを分解し、コンピュータ及びプログラムに関する情報を取得する機会を与える。十分な努力が与えられると、プログラムに隠された鍵が攻撃者により検出されうる。
【０００８】
この攻撃シナリオに対する保護は、大変困難であると判明している。１つのタイプの対策手段は、いわゆるホワイトボックス暗号化である。ホワイトボックス暗号化では、鍵及びアルゴリズムは組み合わされる。結果として得られるアルゴリズムは１つの特定の鍵についてのみ作用する。次に、アルゴリズムは、いわゆるルックアップテーブルネットワークとして実現されうる。計算は、鍵に依存したテーブルにおいてルックアップ系列として変換される。例えば、このアプローチの具体例について、Ｓ．Ｃｈｏｗ，Ｐ．Ｅｉｓｅｎ，Ｈ．Ｊｏｈｎｓｏｎ，Ｐ．Ｃ．ｖａｎ  Ｏｏｒｓｃｈｏｔによる“Ｗｈｉｔｅ−Ｂｏｘ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ａｎ  ＡＥＳ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”を参照されたい。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
コンピュータシステムに対するサイドチャネル攻撃に対する既知の対応策は、完全には満足いくものでない。例えば、ランダム性の導入は統計解析によって反撃されうる。ソフトウェアの難読化は、プログラムの処理のより先進的な解析によって反撃されうる。従って、より多くのより良好な対応策が必要とされる。
【課題を解決するための手段】
【００１０】
この問題は複数の入力値に対して同時に作用するテーブルネットワークの導入によって対処される。テーブルネットワークは、異なる入力又は入力グループに異なる関数を適用するものであってもよい。実際にそれは２つの関数を実行するため、複数の入力の２つ以上を単一の値に暗号化する暗号を利用して、攻撃者がテーブルネットワークが意図する関数を決定すること不可能になる。２０１２年１２月２１日に出願された“Ｃｏｍｐｕｔｉｎｇ  ｄｅｖｉｃｅ  ｃｏｍｐｒｉｓｉｎｇ  ａ  ｔａｂｌｅ  ｎｅｔｗｏｒｋ”という名称の米国６１／７４０，６９１号の米国仮出願、及び／又は２０１２年１２月２７日の出願日とＥＰ１２１９９３８７の出願番号の同一名称“Ｃｏｍｐｕｔｉｎｇ  ｄｅｖｉｃｅ  ｃｏｍｐｒｉｓｉｎｇ  ａ  ｔａｂｌｅ  ｎｅｔｗｏｒｋ”の欧州特許出願を参照されたい。
【００１１】
当該システムはかなりセキュリティを追加しているが、特に攻撃も出るが更に拡大された場合、攻撃のベクトルを残している。攻撃者がフルアクセスを有し、これにより、彼がシステムにおいて生じる全てを観察するだけでなく、プログラムを変更可能な攻撃者について準備することを想定する。テーブルエントリに対する変更と変数に対する変更との２つの変更を考える。第１のタイプの変更は、プログラム実行の開始前に変更が可能であるため、攻撃者に対してあまり想定せず、後者のタイプの変更は、プログラムの実行中に実行され、このため、より困難であると考えられる。例えば、攻撃者は、以下の攻撃を試みるかもしれない（最も可能性があるのは自動化された方法で）。何れの実行も元のプログラムと変更されたプログラムとの出力における相違を示さない場合、変更されたテーブルエントリと変更されていないテーブルエントリが、関連するデータに関する限り等しく、難読化計算、すなわち、いわゆる、状態変数と状態関数とにおいてのみ異なると結論づける。十分な時間が与えられると、正しい計算に関する限り、等しい値のクラスからマップが構成されてもよい。効果的には、状態変数は排除される。明確にするため、符号化前、攻撃者は、状態値は異なるがデータ値が同じであるか直接的には観察できないが、彼はテーブル変更の効果を解析することからこれを推測できるかもしれない。
【００１２】
プログラム変更に対する柔軟性の増加による関数入力値に対するデータ関数を計算するよう構成される計算装置を有することが効果的であろう。
【００１３】
同一出願人によって２０１３年２月２２日に出願された“Ｃｏｍｐｕｔｉｎｇ  ｄｅｖｉｃｅ  ｃｏｎｆｉｇｕｒｅｄ  ｗｉｔｈ  ａ  ｔａｂｌｅ  ｎｅｔｗｏｒｋ”という名称による欧州特許出願１３１５６３０２が参照され、参照することによりここに援用される。当該出願は、符号化、テーブルネットワークなどの更なる具体例を含む。
【００１４】
少なくともこの懸念に対処する関数入力値に対してデータ関数を計算するよう構成される計算装置が提供される。
【００１５】
計算装置は、電子ストレージと、当該ストレージに結合される電子プロセッサとを有する。ストレージはテーブルネットワークの系列を記憶する。プロセッサは、テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力とグローバル状態入力とに対して繰り返される関数を計算するよう構成される。
【００１６】
系列のテーブルネットワークは、対応するデータ関数と状態関数とについて構成され、対応するデータ関数に従ってデータ入力をデータ出力にマッピングし、状態関数に従って状態入力を状態出力に同時にマッピングするよう構成される。
【００１７】
電子プロセッサは、系列のテーブルネットワークの適用を繰り返すよう構成され、繰り返し適用されるテーブルネットワークのテーブルネットワーク、すなわち、第１のテーブルネットワークをグローバルデータ入力とグローバル状態入力とに適用し、繰り返しの後続のテーブルネットワークを系列の前のテーブルネットワークのデータ出力と状態出力とに適用し、系列の繰り返される適用は、グローバルデータ入力に対してグローバルデータ関数を決定し、グローバル状態入力に対してグローバル状態関数を決定し、これにより、中間データ出力と中間状態出力とを取得する。
【００１８】
電子ストレージは更に、系列のテーブルネットワークになされた変更に対処するためテーブルネットワークの系列と連携するよう構成される保護テーブルネットワークを記憶し、保護テーブルネットワークは、中間状態出力とグローバル状態入力とを入力として受信するよう構成される。保護テーブルネットワークは、グローバル状態入力に適用されるグローバル状態関数が中間状態出力を生成することを検証するよう構成される。
【００１９】
それは、ホワイトボックス暗号化により可能なコード難読化がより一般的に適用可能である場合、効果的である。従来のホワイトボックス暗号化は静的であり、それはアルゴリズムを固定的なテーブルネットワークに変換し、入出力の符号化など、テーブル難読化を利用してネットワークを変換する。このタイプの難読化は、状態変数と共にデータ変数を符号化することによって改良されうる。それは、例えば、ホワイトボックス暗号化において利用されるようなテーブルベースの計算のセキュリティが非静的な計算において適用可能である場合、効果的である。例えば、テーブルベースの計算を利用することに対する１つ障害は、ループ、ｗｈｉｌｅ−ｄｏ、ｆｏｒ−ｕｎｔｉｌ構造などの繰り返し構造にシステムを適用することである。
【００２０】
システムは、繰り返し適用されるテーブル又はテーブルネットワークの系列を提供する。データ関数と共に、当該系列はまた状態関数を計算する。状態関数を検証することによって、繰り返し全体が検証される。系列におけるテーブルネットワークは系列の順序で適用され、当該系列は、全てのテーブルネットワークを同じ順序で複数回適用することによって繰り返される。実施例では、当該系列は２回以上適用される。
【００２１】
合成されたデータ及び状態計算の系列を検証することは、系列が状態変数と共に暗号化されるデータ変数（入力又は出力）に対して実行される場合、更に向上する。実施例では、グローバルデータ入力とグローバル状態入力とは、単一のグローバル入力に一緒に符号化される。実施例では、系列のテーブルネットワークのデータ入力と状態入力とは、単一の入力に一緒に符号化される。実施例では、系列のテーブルネットワークのデータ出力と状態出力とは、単一の出力に一緒に符号化される。実施例では、中間データ出力と中間状態出力とは、単一の中間出力に一緒に符号化される。実施例では、保護されたデータ出力と保護された状態出力とは、単一の保護された出力に一緒に符号化される。
【００２２】
系列のテーブルネットワークを１回適用することによって取得される状態関数は、単一繰り返し状態関数として参照される。単一繰り返し状態関数がデータ関数とは独立に選択されてもよいことは、発明者の洞察であった。単一繰り返し状態関数は、テーブルネットワークとしての実現が系列において用いられるより少ないテーブルしか必要とせず、第１の系列におけるテーブルネットワークより小さいストレージしか必要としないように選択されてもよい。さらに、単一繰り返し状態関数は、単一繰り返し状態関数の繰り返しがより少ないテーブル及び／又はストレージしか必要としないように選択されてもよい。実施例では、状態テーブルネットワークは、系列におけるテーブルネットワークより少ないテーブルしか一緒に有さない。実施例では、ストレージ上の状態テーブルネットワークのサイズは、ストレージ上の系列のサイズより小さい。状態テーブルネットワーク及び／又は保護テーブルネットワークは、繰り返されず、第１の系列が繰り返される場合でさえ、１回しか適用されない。
【００２３】
例えば、単一繰り返し状態関数の効果的な選択は、冪等関数である。冪等関数の複数の繰り返しは、関数の１回の繰り返しと同じ結果を与える。従って、第１の系列の複数回の適用と同じ状態関数を取得するため、単一繰り返し状態関数は、１回しか適用される必要がない。これは、保護ネットワークの構成をかなり簡単化する。
【００２４】
単一繰り返し状態関数の他の効果的な選択は、冪零関数である。冪零関数は、関数のｑ回の適用が恒等式になるような関連する数ｑを有する。これは、ｑ＋１回の適用が単一繰り返し状態関数自体に等しくなるため、保護ネットワークが単一繰り返し状態関数のｑ回までの適用を検証可能であることしか必要としないことを意味する。
【００２５】
実施例では、保護テーブルネットワークは、系列の繰り返し数に応じて更なる入力を受信するよう構成される。これは、保護ネットワークが単一繰り返し状態関数の多数の適用の結果を検索することを可能にする。繰り返し数の受信は、冪零の単一繰り返し状態関数を用いて良好に適合される。この場合、状態ネットワークは、検証状態を取得するため、グローバル状態入力と繰り返し数との組み合わせを検索してもよい。
【００２６】
例えば、更なる入力は、おそらく符号化形式による繰り返し数であってもよい。冪等関数については、繰り返し数が０以上であるか更なる入力が示す場合、十分である。これは単一ビットして表現できる。にもかかわらず、より大きな符号化が可能である。同様に、オーダｑの置換について、繰り返し数のｑによるモジュロが十分である。実施例では、ループは２つのテーブルネットワークとして実現され、１つは所定の繰り返し数までの繰り返しのためのものであり、他方は制限のない繰り返し数のためのものである。前者のテーブルネットワークは、更なる入力を受信してもよく、所定の繰り返し数に限定され、後者のテーブルネットワークは、更なる入力を受信しなくてもよい。計算装置は、このとき繰り返し数に応じて、２つのテーブルネットワークからテーブルネットワークを選択するための制御ロジックを有することが可能である。
【００２７】
実施例では、制御コードは、系列の繰り返し数をカウントし、保護ネットワークへの入力として繰り返し数を供給するよう構成される。
【００２８】
単一繰り返し状態関数のための特に興味深い選択は恒等式である。この場合、系列のテーブルネットワークにより実現される個々の状態関数は、それらの関数の合成が恒等式である限り、任意の関数であってもよい。これは、グローバル状態入力が系列の最後の繰り返しの最後のテーブルネットワークの最後の状態出力に等しいことを検証することによって利用可能である。
【００２９】
保護ネットワークは、系列が受信するものと同じグローバル状態入力に対して実行されてもよいが、これは必ずしも必須でない。保護ネットワークの状態入力と第１の系列とは異なるソースから生じてもよい。異なるソースは、改ざんがない場合、双方の状態が同じであるように構成される。繰り返された第１の系列と保護ネットワークとを適用した後、状態の相違がデータ値を変更させる。
【００３０】
実施例では、系列における少なくとも１つのテーブルネットワークは、例えば、前のテーブルネットワーク以外の更なるソースから追加的な入力を受信する。テーブルネットワークの中間データ出力は追加的な入力に依存し、中間状態出力は追加的な入力に依存しない。追加的な入力は追加的な状態入力と共に出力されてもよいし、又は出力されなくてもよい。このように、追加的な入力は中間状態出力と検証状態との間の関係を妨げない。追加的な入力が状態変更に寄与しなくても、追加的な入力を受信するテーブルにおける変更は、おそらくテーブルの状態出力を変更させる。従って、このような追加的な入力に関する計算に対して更なるチェックがなされる。例えば、追加的な入力は、系列がブロック暗号の単一のラウンドを表す場合、ラウンドキーであってもよい。
【００３１】
本発明の態様は、電子ストレージと、当該ストレージに結合される電子プロセッサとを有し、テーブルネットワークの系列を適用するよう構成される計算装置に関する。当該系列は、保護ネットワークにおける効率的な実現を可能にする単一繰り返し状態関数を有する。当該系列は、繰り返し適用される必要はない。にもかかわらず繰り返しが必要とされる場合、保護ネットワークでなく第１の系列のみを繰り返す代わりに、第１の系列と保護ネットワークとの双方を繰り返すことが可能である。
【００３２】
計算装置は、例えば、携帯電話、セットトップボックス、コンピュータなどのモバイル電子装置などの電子装置である。
【００３３】
本発明の態様は、データ関数の系列を取得し、テーブルネットワークの第１の系列、保護テーブルネットワーク及びコンピュータコードを生成するよう構成されるコンパイラに関する。コンピュータコードは、第１の系列の繰り返しの適用と、その後の保護テーブルネットワークの適用とを制御するよう構成される。コンパイラは、電子プロセッサと電子メモリとを有してもよく、メモリは、プロセッサをコンパイラとして設定するコンピュータコードを記憶する。
【００３４】
本発明の態様は、計算方法に関する。本発明による方法は、コンピュータによる実現される方法としてコンピュータ上で、専用のハードウェアにおいて、又は双方の組み合わせにより実現されてもよい。本発明による方法の実行可能コードは、コンピュータプログラムプロダクトに記憶されてもよい。コンピュータプログラムプロダクトの具体例は、メモリ装置、光記憶装置、集積回路、サーバ、オンラインソフトウェアなどを含む。好ましくは、コンピュータプログラムプロダクトは、当該プログラムプロダクトがコンピュータ上で実行されると、本発明による方法を実行するためのコンピュータ可読媒体に記憶された非一時的なプログラムコード手段を有する。
【００３５】
好適な実施例では、コンピュータプログラムは、当該コンピュータプログラムがコンピュータ上で実行されるとき、本発明による方法の全てのステップを実行するよう構成されるコンピュータプログラムコード手段を有する。好ましくは、コンピュータプログラムは、コンピュータ可読媒体上に実現される。
【図面の簡単な説明】
【００３６】
本発明の上記及び他の態様は、後述される実施例を参照して明らかになるであろう。
【図１ａ】図１ａは、複合テーブルネットワーク１００の概略的なブロック図である。
【図１ｂ】図１ｂは、テーブルネットワーク１００の変形の概略的なブロック図である。
【図２】図２は、複合テーブルネットワーク２００の概略的なブロック図である。
【図３】図３は、複合テーブルネットワーク３００の概略的なブロック図である。
【図４】図４は、計算装置４００の概略的なブロック図である。
【図５】図５は、複合テーブルネットワーク５００の概略的なブロック図である。
【図６】図６は、コンパイル方法６００の概略的なフローチャートである。
【図７】図７は、計算方法７００の概略的なフローチャートである。  異なる図面において同一の参照番号を有するアイテムは同じ構造的特徴及び同じ機能を有するか、又は同じ信号であることが留意されるべきである。このようなアイテムの機能及び／又は構造が説明される場合、詳細な説明においてそれの繰り返しの説明は必要でない。
【発明を実施するための形態】
【００３７】
本発明は多数の異なる形態による実施例が可能であるが、本開示は本発明の原理の一例としてみなされるべきであり、本発明を図示及び説明された特定の実施例に限定することを意図していないという理解によって、１つ以上の特定の実施例が図面において図示され、ここで詳細に説明される。
【００３８】
図１ａは、複合テーブルネットワーク１００の概略的なブロック図である。
【００３９】
計算装置は、テーブルのネットワークを介し計算装置の計算の全て又は一部を実行することによって、攻撃者に対して保護されうる。テーブルネットワークは、変数及びテーブルを符号化することによって保護できる。にもかかわらず、攻撃は懸念を残す。１つの可能な攻撃ベクトルは、テーブルを変更し、計算を実行し、当該変更が有する効果を確認することである。このようにして、攻撃者は、利用される暗号化における洞察を取得しうる。これに対処するため、データ変数に加えて状態変数を導入してもよい。状態変数は、データ変数の計算パス又はその一部を反映する変数である。しかしながら、状態変数に対して実行される計算の性質は、データ変数に対して実行される計算と異なりうる。状態変数は、計算中に各種方法により検証されうる。状態及びデータ変数はしばしば１つの変数に一緒に符号化されるため、データ変数は影響を受けるが、状態変数は受けないように、攻撃者がテーブルを変更することは困難である。状態変数が改ざんされたことが検出されると、装置は適切なアクションをとってもよい。当該検出は明示的なチェックを介してでなく、しばしば暗黙的に実行可能である。さらに、状態変数のため、同一のデータが複数の表現を有する。これらの状態変数の整合性をチェックすることは、あるタイプの攻撃を検出することを可能にする。
【００４０】
図１ａは、複数のテーブル又はサブテーブルネットワークから構成される複合テーブルネットワーク１００を示す。複合テーブルネットワーク１００は、電子プロセッサを有し、電子ストレージにアクセス可能な計算装置と共に機能するよう設計される。複合テーブルネットワーク１００を構成する複数のより小さなテーブルネットワークが、ストレージに記憶される。電子プロセッサはストレージに結合され、各自の入力値及び出力値にテーブルを適用するよう構成される。
【００４１】
複合テーブルネットワーク１００は、テーブルネットワーク系列１１０及び保護テーブルネットワーク１５０を有する。
【００４２】
系列１１０は、１つ以上のテーブルネットワークを有する。図１ａにおいて、系列１１０はテーブルネットワーク１１２及び１１４を有する。テーブルネットワークは、１つのいテーブルから構成されてもよいし、又は関数を計算するため連携する複数のテーブルを有してもよい。また、テーブルネットワーク１１２及び１１４は、同様に単一のテーブルであってもよい。
【００４３】
より大規模な計算については、計算又はその一部を単一のテーブル又はテーブルネットワークとして表現するトレードオフがある。後者は、攻撃者がシステムを攻撃することを試みることが可能なより多くのポイントを提供するが、他方、ネットワークはより小さなストレージスペースを要求するかもしれない。ある計算は、それが大きすぎるため、実際的な表現を単一のテーブルとして有さず、この場合、テーブルネットワークが必要とされる。例えば、完全なＡＥＳ計算は、単一のテーブルでなく、テーブルネットワークによって表現されてもよい。典型的には、テーブルは、機能的に同じであるテーブルネットワークによって置換可能である。テーブルネットワークとの区別が必要とされるとき、“単一テーブル”又は“モノリシックテーブル”としてテーブルを参照する。
【００４４】
系列１１０に加えて、計算装置は、ある計算結果を計算するため、多数の更なるテーブルネットワーク及び／又はテーブルネットワーク系列を組み合わせてもよい。
【００４５】
簡単化のため、テーブルネットワークは単一のテーブル又は複数の連携するテーブルであってもよいことを記憶して、系列１１０の要素をテーブルネットワークとして参照する。系列１１０は、１つ以上のテーブルネットワークを有してもよい。図１ａにおいて、Ｔ１及びＴ２として参照する２つのテーブル１１２及び１１４が示される。より多くの又はより少ないテーブルネットワークが可能である。特に、系列１１０は、単一のテーブル又は単一のテーブルネットワーク１１２から構成されてもよい。系列１１０は複数のテーブルネットワークを有してもよい。
【００４６】
保護テーブルネットワーク１５０について、同じ理由付けが適用され、それは単一のテーブルとして表現されてもよく、実際、以下に提供される選択の一部は、保護テーブルネットワーク１５０を単一のテーブルとしての表現に良好に適合させる。簡単化のため、それの入出力動作は１つのテーブルによって完全に置換できることを記憶して、保護テーブルネットワーク１５０をテーブルネットワークとして参照する。
【００４７】
プロセッサは、系列１１０のテーブルネットワークを適用することによって、グローバルデータ入力（１２１，ｗ０）及びグローバル状態入力（１２１，ｓ０）に対して繰り返し関数を計算するよう構成される。すなわち、系列１１０のテーブルネットワークは、グローバルデータ及び状態入力に対して複数回適用される。
【００４８】
系列１１０における各テーブルネットワークは、データ入力及び状態入力を受信する。データ変数は文字ｗにより参照され、状態変数は文字ｓにより参照される。テーブルネットワーク１１２及び１１４などの系列１１０のテーブルネットワークＴｉは、対応するデータ関数ｆｉ及び状態関数ｇｉについて構成される。
【００４９】
このようにして、変数系列は、例えば、以下を取得可能な２つのテーブルネットワーク及び２つの繰り返しなどについて生成される（参照番号は図１ａを参照する）。
【００５０】
【表１】
0006046870.tif 000002
繰り返し回数は２より多くてもよい。ちょうど２回の繰り返しである場合、参照番号１２４は同一のデータを番号１２３と参照する。繰り返しにおける各テーブルネットワークは、対応するデータ関数ｆｉに従ってデータ入力ｗｉ−１をデータ出力ｗｉにマッピングし、同時に状態関数ｇｉに従って状態入力ｓｉ−１を状態出力ｓｉにマッピングする。データｗｉ−１及び状態入力ｓｉ−１は、最初のテーブルを除いて前のテーブルの出力であり、この場合、それが入力である。
【００５１】
データ及び状態変数のジョイント暗号化を示すため、記号（ｗ，ｓ）を利用する。例えば、データ及び状態変数を、データと状態との双方が組み合わされた変数ｕにマッピングする暗号化関数Ｅ（ｗ，ｓ）を定義してもよい。マッピングＥは可逆など単射であり、すなわち、ジョイント暗号化が与えられると、元のデータ及び状態値を復元できる。逆マッピングは、データ及び状態抽出器についてρ及びσによりそれぞれ示され、これにより、Ｅ（ρ（ｕ），σ（ｕ））＝ｕである。
【００５２】
状態及びデータ変数は様々なサイズを有しうる。系列１１０が単一のテーブルしか有さない場合、これらのサイズは通常は、４〜８ビットのデータサイズなど、やや適度なものとなる。状態サイズはデータサイズに等しいか、又は若干小さくてもよく、すなわち、２〜８ビットである。しかしながら、系列１１０がテーブルネットワークを含む場合、データ及び状態値は原理的には無制限であり、すなわち、１２８ビット、２５６ビットなどである。
【００５３】
一般に、系列１１０の繰り返される適用中、データ入力及び出力は、それの対応する状態入力又は出力と共に暗号化される。
【００５４】
系列の繰り返される適用は、グローバルデータ入力に対してグローバルデータ関数を決定し、またグローバル状態関数を決定する。系列１１０が２つのテーブルネットワークを有する場合、グローバルデータ関数は、
【００５５】
【数１】
0006046870.tif 000003
によって提供され、グローバル状態関数は、グローバル状態入力に対して
【００５６】
【数２】
0006046870.tif 000004
によって提供され、中間データ出力（１２６，ｗｉｎｔｅｒ＝ｆ（ｗ０））及び中間状態出力（１２６，ｓｉｎｔｅｒ＝ｇ（ｓ０））を取得する。また、ｓｉｎｔｅｒ及びｗｉｎｔｅｒは、１２６として参照される単一の値に一緒に暗号化される。
【００５７】
繰り返し回数は固定されてもよいし、又はロープ制御変数を介し制御されてもよい。ループ制御変数は、“ｉ”又は“インデックス”として参照されることもある。特に、後者のケースでは、プロセッサは、ループ制御変数の回数系列１１０を適用するよう制御ロジックにより構成されてもよい。例えば、制御ロジックは、回数を表すロープ制御変数にアクセスしてもよい。制御ロジックは、各繰り返しによってループ制御変数を減らす。制御ループ制御変数に対する処理は、テーブルネットワーク自体として実現されてもよい。
【００５８】
ループ制御変数がゼロでないとき、新たな繰り返しが実行されるように、制御は繰り返し後にリターンされ、ループ制御変数がゼロである場合、制御はわたされる。当該制御はテーブルネットワークとして表現されてもよい。例えば、テーブルは、変数に依存してジャンプするためのマシーンアドレスを計算してもよい。
【００５９】
ループ制御変数を用いて繰り返し回数を制御する代わりに、繰り返し回数は、ｗｈｉｌｅ条件などの他の手段により制御されてもよい。この場合、ループ制御変数は、実際に実行された繰り返し回数をカウントする。
【００６０】
保護テーブルネットワーク１５０は、系列のテーブルネットワークに対してなされた変更に反撃するためテーブルネットワーク系列と連携するよう構成される。保護テーブルネットワーク１５０は、入力として中間状態出力ｓｉｎｔｅｒ及びグローバル状態入力１３１と入力として受信するよう構成される。
【００６１】
保護テーブルネットワーク１５０が受信するグローバル状態入力１３１は、系列１１０が適用されるグローバル状態入力のコピーであってもよい（ｓ０）。例えば、状態を取得するため、入力１２１に対して状態抽出テーブル１６０を適用してもよい。抽出された状態は、符号化形式となる。この可能性が、図１ｂに示される。しかしながら、保護テーブルネットワーク１５０はまた、入力１２１と異なるソースから取得される状態変数を受信してもよい。例えば、前の計算は、２つの出力、１）状態出力と共に符号化されたデータ出力と、２）状態出力とを生成していてもよい。これら２つの状態出力は同じであるべきであるが、これは、特に保護テーブルネットワーク１５０において以降の計算においてチェックのみされる。図１ａは、双方の可能性と共に利用されてもよい。データ及び状態変数を一緒に符号化する変数はロング変数として参照され、データ又は状態のみはショート変数として参照される。
【００６２】
保護テーブルネットワーク１５０は、グローバル状態入力（ｓ０）に適用されるグローバル状態関数（ｇ）が、ｓｉｎｔｅｒ＝ｇ（ｓ０）？として表記される中間状態出力を生成することを検証するよう構成される。
【００６３】
図１ａにおいて、保護テーブルネットワーク１５０は、状態テーブルネットワーク１３０Ｔｃ及びアラインテーブル１４０の２つのテーブルを有する。状態テーブルネットワークＴｃは、グローバル状態関数（ｇ）について構成され、状態入力１３１を検証状態出力１３２ｓｃにマッピングするよう構成され、ｇ（ｓ０）に等しくなるべきである。保護テーブルネットワーク１５０は、入力としてグローバル状態入力１３１をとり、検証状態出力１３２を取得するため、それ状態テーブルネットワーク１３０を適用する。好ましくは、状態テーブルネットワーク１３０Ｔｃにおけるテーブル数は、系列１１０におけるテーブル数より厳密に少ない。
【００６４】
アラインテーブル１４０は、検証状態出力１３２ｓｃ及び中間データ／状態出力（１４７，ｕ＝（ｗｉｎｔｅｒ，ｓｉｎｔｅｒ））を受信し、出力として保護されたデータ及び状態出力１４３を生成し、任意的にはまた保護された状態出力１４５を生成する。中間データ／状態出力１４７ｕにおける状態が検証状態出力１３２と同じである場合、データ及び状態出力１４３におけるデータは中間データ／状態出力１４７ｕにおけるデータに等しく、データ及び状態出力１４３における状態は、状態置換１４４が適用された検証状態出力１３２ｓｃ（又はｕにおける状態、それらはこの場合同じである）に等しい。当該置換は省略されてもよいが、それの存在は、アラインテーブル１４０の出力が、誤りが検出されなかった場合でさえそれの入力１４７と異なることを保証する。
【００６５】
アラインテーブル１４０は、関数ｚ１４２及び任意的な置換又は順列（ｐｅｒｍｕｔａｔｉｏｎ）１４４から構成されてもよい。検証状態出力１３２及び中間データ／状態出力１４７ｕ＝（ｗｉｎｔｅｒ，ｓｉｎｔｅｒ）は、ｚ関数１４２に対する入力である。ここで、σ（ｕ）＝ｓｃである場合、ｚ（ｕ，ｓｃ）＝ρ（ｕ）である。関数ρ及びσはそれぞれデータ及び状態抽出器である。従って、アラインテーブル１４０は、検証状態出力が中間状態出力（ｓｉｎｔｅｒ＝ｓｃ？）に等しいことを検証する。
【００６６】
σ（ｕ）≠ｓｃである場合、ｚの出力はランダムなデータ出力であってもよい。当該出力はρ（ｕ）と常に異なるか、又はしばしば、すなわち、少なくとも９０％のケースにおいて異なることを要求してもよい。出力はある入力値に対して少なくとも異なるべきである。
【００６７】
置換１４４は、状態に置換（ｐｅｒｍ）を適用し、ここで、当該状態は中間データ／状態出力１４７から取得されるが、検証状態がまた可能であった。アラインテーブルにおいて置換を有することは、誤り、すなわち、未許可のテーブル変更が検出されたか否かの事実に関係なく、テーブルの出力が変更可能であることを保証する。これは、テーブル１４０における変更が改ざんにより導入された変更を判断するのに利用される攻撃を回避する。
【００６８】
ｚ関数から取得されたデータ出力と置換１４４からの状態とは、保護されたデータ及び状態出力１４３（ｚ（ｕ，ｓｃ），Ｐｅｒｍ（ｓｃ））において一緒に符号化される。状態出力はまた、状態出力１４５Ｐｅｒｍ（ｓｃ）として別々に符号化された出力であってもよい。出力１４３及び１４５を有することは、以下の計算が入力１３１及び１２１と同様に入力としてこれらを利用することを可能にする。出力１４３及び１４５は、“保護された出力”と参照される。
【００６９】
テーブル１４０は、関数１４２，１４４が別々には見えない単一のテーブルであってもよい。テーブルネットワーク１３０はまた、保護テーブルネットワーク１５０が２つの単一のテーブルを有するように、単一のテーブルとして実現されてもよい。実施例では、状態テーブルネットワーク１３０及び／又はアラインテーブル１４０は、複数のテーブルを有するテーブルネットワークである。保護テーブルネットワーク１５０は、例えば、単一の繰り返し状態関数が恒等式である場合、単一のテーブルであってもよい。
【００７０】
系列１１０において使用される状態関数は、データ関数から独立に選択されてもよい。これは、効果的な選択が可能であることを意味する。例えば、データ関数がそうでなくても、等しい（ｇ０）となる系列におけるテーブルネットワーク（Ｔｉ）に対応する全ての状態関数（ｇｉ）を選択してもよい。状態関数について適切な選択をすることによって、それらの関数構成は、データ関数の関数構成が計算するのにシンプルでなかったとしても、計算するのにシンプルであってもよい。
【００７１】
系列１１０のテーブルネットワークの単一の繰り返しにより決定される状態入力に対する関数は、単一繰り返し状態関数
【００７２】
【数３】
0006046870.tif 000005
として参照される。単一繰り返し状態関数
【００７３】
【数４】
0006046870.tif 000006
が特にシンプルになるように、個々の状態関数ｇｉを選択してもよい。系列が単一のテーブルネットワークのみを有する場合、
【００７４】
【数５】
0006046870.tif 000007
である。テーブルネットワークの系列が繰り返し適用されるとき、単一繰り返し状態関数
【００７５】
【数６】
0006046870.tif 000008
が繰り返し適用される。
【００７６】
実施例では、単一繰り返し状態関数
【００７７】
【数７】
0006046870.tif 000009
は冪等（ｉｄｅｍｐｏｔｅｎｔ）である。冪等関数は、
【００７８】
【数８】
0006046870.tif 000010
という性質を有し、冪等関数を１回適用することは入力を変えるかもしれないが、それを複数回適用することは関数をさらには変えない。特に、
【００７９】
【数９】
0006046870.tif 000011
は冪等であってもよく、恒等式でなくてもよい。ランダムな冪等関数は以下のように選択されてもよい。まず、固定点及び非固定点における全ての状態値をパーティションし、少なくとも１つの固定点があるべきであり、次に各非固定点ｘについて、固定点ｙを選択し、
【００８０】
【数１０】
0006046870.tif 000012
を設定する。このアルゴリズムは、テーブルにおける実現に良好に適している。パーティション及び選択はランダムであってもよい。
【００８１】
繰り返し数が少なくとも１つであると知られ、
【００８２】
【数１１】
0006046870.tif 000013
が冪等である場合、状態テーブルネットワーク１３０は、正確な繰り返し数を知る必要なく、
【００８３】
【数１２】
0006046870.tif 000014
について構成されてもよい。
【００８４】
実施例では、系列におけるテーブルネットワークの１つ以上又は全ては、前のテーブルネットワーク以外の更なるソースから追加的な入力を受信する。テーブルネットワークのデータ出力は追加的な入力に依存しうる。追加的な入力は追加的な状態入力と共に暗号化されてもよいし、暗号化されなくてもよく、にもかかわらず、状態入力は追加的な入力に依存しない。このように、追加的な入力は中間状態出力と検証状態との間の関係を乱さない。
【００８５】
典型的には、計算装置は、当該装置に記憶されている適切なソフトウェアを実行するマイクロプロセッサ（図示せず）を有し、例えば、当該ソフトウェアは、ＲＡＭなどの揮発性メモリ又はフラッシュ（図示せず）などの不揮発性メモリなどの対応するメモリにダウンロード及び／又は記憶されたものであってもよい。
【００８６】
図２は、複合テーブルネットワーク２００の概略的なブロック図である。図２は、状態テーブルネットワーク１３０が追加的な入力１３３を有することを除いて、図１とほぼ同様であり、ｋは系列の繰り返し数１１０である。状態テーブルネットワーク１３０は、単一繰り返し状態関数
【００８７】
【数１３】
0006046870.tif 000015
の繰り返しの効果を計算するよう構成される。例えば、定数の加算として、単一繰り返し状態関数
【００８８】
【数１４】
0006046870.tif 000016
を選択してもよい。この場合、状態テーブルネットワーク１３０は、ｓ＋ｋｃ（ｓは入力１３１を参照）を計算するよう構成可能である。後者の関数は小規模テーブルナットワークにおいて容易に実現可能である。従って、状態テーブルネットワーク１３０について必要とされるストレージ量は、系列１１０について必要とされるものよりはるかに小さい。
【００８９】
【数１５】
0006046870.tif 000017
が冪等であり、繰り返し数がゼロでありうる場合、状態テーブルネットワーク１３０は、２つの入力値１３３、すなわち、ゼロと非ゼロについて構成すれさえすればよい。
【００９０】
実施例では、
【００９１】
【数１６】
0006046870.tif 000018
は冪零（ｎｉｌｐｏｔｅｎｔ）であり、すなわち、関数
【００９２】
【数１７】
0006046870.tif 000019
のｑ個の合成が恒等式に等しくなるような整数ｑが存在する。このような関数の具体例は、ｑを分割する長さによる循環（ｃｙｃｌｅ）のみを有する循環分解を有する置換であり、すなわち、
【００９３】
【数１８】
0006046870.tif 000020
は、
【００９４】
【数１９】
0006046870.tif 000021
のｑ個の合成が恒等式に等しくなるように、オーダｑの置換である。このような場合、状態テーブルネットワーク１３０は、ｇの高々ｑ個の合成を計算するのに十分大きいものであればよい。この場合、それの値のモジュロｑしか必要でないため、更なる入力１３３が簡単化されうる。
【００９５】
【数２０】
0006046870.tif 000022
が恒等式である場合、保護テーブルネットワーク１５０は単一のテーブルとしてより容易に実現されうる。
【００９６】
図３は、更なる他のオプションを示すブロック暗号である。ここで、
【００９７】
【数２１】
0006046870.tif 000023
は恒等式となるよう選択される。保護テーブルネットワーク１５０は、グローバル状態入力（ｓ０）が中間状態出力に等しいことを検証するよう構成される（ｓｉｎｔｅｒ＝ｓ０？）。この場合、テーブル１３０は完全に省略されてもよい。
【００９８】
所望の単一繰り返し状態関数を取得するためｇｉを選択する１つの方法は以下の通りである。系列１１０がｎ個の関数ｇｉを定義するｎ個のテーブルネットワークを有すると仮定する。まず、
【００９９】
【数２２】
0006046870.tif 000024
を選択し、状態変数の全ての値に対する置換として
【０１００】
【数２３】
0006046870.tif 000025
を表現する。次に、
【０１０１】
【数２４】
0006046870.tif 000026
についてランダムな置換を選択する。最後に、単一繰り返し関数
【０１０２】
【数２５】
0006046870.tif 000027
からの最後の状態関数ｇｎ及びランダムな置換の逆を、例えば、
【０１０３】
【数２６】
0006046870.tif 000028
として選択する。このアルゴリズムは、例えば、
【０１０４】
【数２７】
0006046870.tif 000029
が恒等式又は冪零であるときに適用されてもよい。実施例では、単一繰り返し状態関数は、特に、例えば、単一繰り返し状態関数が冪零又は冪等である場合でも、系列の少なくとも１つのテーブルネットワーク（Ｔｉ）の状態関数（ｇｉ）と異なる。実施例では、単一繰り返し状態関数は、特に単一繰り返し状態関数が冪零又は冪等である場合でも、系列の何れかのテーブルネットワーク（Ｔｉ）の各状態関数（ｇｉ）と異なる。
【０１０５】
図４は、計算装置４００の概略的なブロック図である。
【０１０６】
図４は、記憶装置４１０を有する計算装置４００を示す。図４に示される装置は、図１，２，３，５に示されるテーブルネットワークと共に利用されてもよい。
【０１０７】
記憶装置４１０は、典型的には、１つ以上の不揮発性メモリであるが、またハードディスク、光ディスクなどであってもよい。記憶装置４１０はまた、ダウンロード又は受信されたデータを有する揮発性メモリであってもよい。計算装置４００は、プロセッサ４５０を有する。プロセッサは、典型的には、メモリに記憶されるコード４５５を実行する。便宜上、コードは記憶装置４１０に記憶されてもよい。コードは、プロセッサに計算を実行させる。装置４００は、入力値を受信し、及び／又は結果を送信するための任意的なＩ／Ｏ装置４６０を有してもよい。Ｉ／Ｏ装置４６０は、ネットワーク接続、着脱可能な記憶装置などであってもよい。
【０１０８】
記憶装置４１０は、図１〜３，５の１つによる１つ以上のテーブルネットワークを有する。
【０１０９】
実施例では、計算装置は、実行中に以下のように動作しうる。計算装置４００は入力値を受信する。当該入力値は、例えば、符号化テーブル４４１を用いて符号化される。従って、入力値は符号化された入力値として取得される。入力値は、例えば、装置４６０などを介し符号化された入力値として直接取得可能であることに留意されたい。入力値を符号化された入力値に符号化することは、状態入力が選択される必要があることを意味する。これを実行するための複数の方法があり、例えば、状態入力は、乱数生成器などによってランダムに選択されてもよい。状態入力はアルゴリズムに従って選択されてもよく、アルゴリズムは複雑化され、難読化に付加される。状態入力値はまた定数であってもよいし、数のシーケンス、すなわち、一定のインクリメント、すなわち、１を有する整数のシーケンスから順次とられてもよく、あるスタートポイントで開始され、当該スタートポイントはゼロ、乱数などであってもよい。状態入力を乱数として選択し、次の状態入力選択のそれぞれについて１だけ増加することは、特に効果的な選択である。状態入力がオフデバイスに選択される場合、攻撃者は、何れで状態入力値が選択され、それらが何であるかを追跡する方法を有さない。
【０１１０】
プロセッサ４５０は、記憶装置４１０におけるプログラム４５５を実行する。プログラムは、プロセッサに符号化された入力値又は結果として得られた出力値にルックアップテーブルを適用させる。ルックアップテーブルは、何れかの論理又は算術関数について作成されてもよく、このため、ルックアップテーブルのシーケンスを利用することによって、何れかの計算が実行されてもよい。これはプログラムを難読化することを助ける。この場合、単一の関数入力値は複数の符号化された入力値によって表現されうるため、難読化は特に効果的である。さらに、一部又は全てのテーブル及び／又はテーブルネットワークは、複数の関数の性質を有するテーブルネットワークの複数の関数の性質を有し、一部又は全てが結果の検証のため第２のテーブルネットワークとペアリングされる。
【０１１１】
あるポイントでは、結果値が検出される。必要である場合、結果は復号化テーブル４４２などを用いて復号化されてもよい。しかしながら、当該結果はまた符号化形式でエクスポートされてもよい。入力値はまた入力装置から取得されてもよく、出力値は画面上に示すため利用されてもよい。
【０１１２】
計算は符号化されたデータワードに対して実行される。計算は、テーブルルックアップアクセスのシーケンスを適用することによって実行される。用いられる入力値は、計算装置の外部から受信した入力値であってもよいが、前のルックアップテーブルアクセスによって取得されてもよい。このように、新たなルックアップテーブルアクセスについて利用される中間結果が取得される。あるポイントでは、中間結果の１つは関数の符号化された結果である。
【０１１３】
計算装置４００は、状態入力値をデータ関数入力に割り当てるための乱数生成器を有してもよい。
【０１１４】
図５は、複合テーブルネットワーク５００の概略的なブロック図である。テーブルネットワーク５００は、テーブルネットワーク１ａと同じである。また、図５では、出力１４５及びテーブル１３０は任意的である。しかしながら、図５において、系列１１０は少なくとも２つのテーブルネットワークを有し、さらに、系列１１０は繰り返されず、入力に対して１回適用される。グローバル状態関数は恒等式（図示せず）であってもよい。この場合、系列はほとんどオーバヘッドなく検証されうる。グローバル状態関数が恒等式でない場合、テーブル１３０が利用されてもよい（図５に示されるように）。しかしながら、系列１１０における複数のテーブルを検証するため、単一のテーブルネットワーク又はテーブル１３０しか必要とされない。特に、ストレージ（５１０）における状態テーブルネットワーク１３０のサイズは、ストレージにおける系列１１０のサイズより小さい。
【０１１５】
例えば、複合テーブルネットワーク５００は、複数のラウンド、すなわち、ＡＥＳ、ＤＥＳなどを有するブロック暗号を表すものであってもよい。ブロック暗号の各ラウンドは、系列１１０のテーブルネットワークによって計算され、ここで、データ関数はブロック暗号ラウンドを表す。各データ関数は状態関数と結合される。状態関数は、グローバル状態関数が恒等式となるように選択される。例えば、ラウンドの第１の半分では、状態関数はデータ関数に等しいが、ラウンドの第２の半分では、状態関数は第１の半分における状態関数の逆である。この結果、系列はデータ関数によりブロック暗号を計算するが、状態関数により恒等式を計算する。
【０１１６】
図６は、コンパイル方法６００をフローチャートとして示す。ステップ６１０において、第１のコンピュータプログラムが受信機により受信される。ステップ６２０において、辞書式解析が、例えば、辞書式解析手段によってトークンを特定するため実行される。おそらくマクロ拡張などの処理がまた実行される。ステップ６３０において、プログラムが構文解析器（ｐａｒｓｅｒ）により解析される。例えば、構文解析器は、第１のプログラムのプログラミング言語の形式的文法に従って構文解析ツリーを生成する。構文解析器は、プログラムにおける異なる言語構成を特定し、適切なコード生成ルーチンを呼び出す。特に、１つ以上の演算子（ｏｐｅｒａｔｏｒ）が特定される。この場合、ステップ６４０において、コード生成はコード生成器により実行される。コード生成中、コードと、必要に応じて付属のテーブルとが生成される。付属のテーブルは、２つの関数、１つは必要な演算子のためのものであり、すなわち、データ関数と状態関数とについて構成されるテーブルを含む。
【０１１７】
コンパイラは、１つ以上の関数を特定するよう構成される。この場合、ステップ６４０において、コード生成はコード生成器により実行される。コード生成中、コードとテーブルネットワークの系列１１０が生成される。また、保護テーブルネットワーク１５０が生成される。生成されたコードは、系列１１０を繰り返し適用するよう構成される。上述されたように、結果に対して保護テーブルネットワーク１５０が適用される。
【０１１８】
ステップ６５５において、生成されたテーブルはテーブルベースにマージされる。いくつかのテーブルは複数回生成されることがよく起きるためである。この場合、それらを複数回記憶することは必要とされない。例えば、アッドテーブルは１回しか必要及び生成されなくてもよい。全てのコードがマージされ、全てのテーブルがマージされると、コンパイル処理は終了される。任意的には、最適化ステップがあってもよい。
【０１１９】
典型的には、コンパイラは符号化されたドメインを利用し、すなわち、ある基準に対応する全ての値又は少なくとも全ての値が符号化されるプログラムのセクションは、コードワードビットサイズ（ｎ）を有する。符号化されたドメインでは、処理は、ルックアップテーブルの実行により実行されてもよい。符号化されたドメインが入力されると、全ての値が符号化され、符号化されたドメインが残されると、値は復号化される。基準は、当該値が暗号鍵などの機密情報に相関するか、又は依存するということであってもよい。
【０１２０】
コンパイラを生成するための興味深い方法は以下である。ステップ６３０において、中間的コンパイルが実行される。これは、レジスタ転送言語などの中間的言語に対するものであってもよいが、また機械語コードコンパイルであってもよい。これは、図６のステップ６１０〜６３０について、テーブルネットワークを生成しない従来のコンパイラが利用されてもよいことを意味する。しかしながら、ステップ６４０において、コード生成は、中間的コンパイルに基づき実行される。例えば、機械語コードが利用された場合、各命令は当該命令の対応する演算子のない実装、すなわち、当該命令のテーブルベースの実装により置換される。これは、コンパイラを生成するための特に直接的な方法を表す。図６はまた、機械語でなく第２のプログラミング言語を生成するコンパイラを生成するのに利用されてもよい。
【０１２１】
図７は、テーブルネットワークの系列（１１０，Ｔ１，Ｔ２）を利用する計算方法７００の概略的なフローチャートであり、当該方法は、テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力（１２１，ｗ０）及びグローバル状態入力（１２１，ｓ０）に対して繰り返し関数を計算するよう構成される。
【０１２２】
当該方法は、系列のテーブルネットワーク（Ｔ１，Ｔ２，Ｔ１，Ｔ２）を繰り返し適用することを含み、繰り返し適用されるテーブルネットワークのテーブルネットワーク（Ｔ１）をグローバルデータ入力（ｗ０）及びグローバル状態入力（ｓ０）に適用し、当該繰り返しの後続するテーブルネットワーク（Ｔ２，Ｔ１，Ｔ２）を系列の前のテーブルネットワークのデータ出力及び状態出力に適用し、系列の繰り返される適用は、グローバルデータ入力に対するグローバルデータ関数
【０１２３】
【数２８】
0006046870.tif 000030
を決定し、グローバル状態入力に対するグローバル状態関数
【０１２４】
【数２９】
0006046870.tif 000031
を決定し、これにより、中間データ出力（ｗｉｎｔｅｒ＝ｆ（ｗ０））及び中間状態出力（ｓｉｎｔｅｒ＝ｇ（ｓ０））を取得する。
【０１２５】
系列のテーブルネットワークになされた変更に対処するためテーブルネットワークの系列と連携するよう構成される保護テーブルネットワーク（１５０）を適用することによって、グローバル状態入力（ｓ０）に適用されるグローバル状態関数（ｇ）が中間状態出力を生成することを検証し（ｓｉｎｔｅｒ＝ｇ（ｓ０）？）、保護テーブルネットワークは入力として中間状態出力（１２５；１２６，ｓｉｎｔｅｒ）及びグローバル状態入力（１３１，ｓ０）を受信するよう構成され、保護テーブルネットワークは、グローバル状態入力（ｓ０）に適用されるグローバル状態関数（ｇ）が中間状態出力を生成することを検証するよう構成される（ｓｉｎｔｅｒ＝ｇ（ｓ０）？）。
【０１２６】
当業者に明らかなように、当該方法を実行するための多数の異なる方法が可能である。例えば、ステップの順序は変更可能であり、又は一部のステップはパラレルに実行されてもよい。さらに、他の方法ステップがステップ間に挿入されてもよい。挿入されたステップは、ここに説明されるような方法の精緻化を表すものであるか、又は当該方法に関連しないものであってもよい。例えば、テーブル１３０がステップ７２０において利用される場合、テーブル１３０は、系列１１０に完全にパラレルに実行されてもよい。
【０１２７】
さらに、所与のステップは、次のステップが開始されるまで、完全に終了していなくてもよい。
【０１２８】
本発明による方法は、プロセッサシステムに方法７００を実行させるための命令を有するソフトウェアを用いて実行されてもよい。ソフトウェアは、システムの特定のサブエンティティによりとられたステップのみを含むものであってもよい。ソフトウェアは、ハードディスク、フロッピー（登録商標）、メモリなどの適切な記憶媒体に記憶されてもよい。ソフトウェアは、有線若しくは無線を介し又はインターネットなどのデータネットワークを利用して信号として送信されてもよい。ソフトウェアは、サーバ上でダウンロード及び／又はリモート使用のために利用可能とされてもよい。本発明による方法は、本発明による方法を実行するようＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）などのプログラマブルロジックを設定するよう構成されるビットストリームを用いて実行されてもよい。
【０１２９】
本発明はまた、本発明を実施するよう構成されるコンピュータプログラム、特にキャリアにおけるコンピュータプログラムに拡張されることが理解されるであろう。プログラムは、ソースコード、オブジェクトコード、コード中間ソース及び部分的にコンパイルされた形態などのオブジェクトコード、又は本発明による方法に実現において利用するのに適した他の何れかの形態におけるものであってもよい。コンピュータプログラムプロダクトに関する実施例は、提供された方法の少なくとも１つの処理ステップのそれぞれに対応するコンピュータ実行可能命令を有する。これらの命令は、サブルーチンに分割されてもよく、及び／又は静的又は動的にリンクされてもよい１つ以上のファイルに記憶されてもよい。コンピュータプログラムプロダクトに関する他の実施例は、提供されたシステム及び／又はプロダクトの少なくとも１つの各手段に対応するコンピュータ実行可能命令を有する。
【０１３０】
上述した実施例は本発明を限定するのでなく説明するものであり、当業者が他の多数の実施例を設計可能であることが留意されるべきである。
【０１３１】
請求項において、括弧内に配置された参照符号は、請求項を限定するものとして解釈されるべきでない。“有する”という動詞及びそれの派生語の使用は、請求項に記載された以外の要素又はステップの存在を排除するものでない。要素に先行する冠詞“ある”は、当該要素が複数存在することを排除するものでない。本発明は、複数の個別の要素を有するハードウェア及び適切にプログラムされたコンピュータによって実現されてもよい。複数の手段を列記した装置の請求項において、これらの手段の複数は１つ及び同じハードウェアアイテムにより実現されてもよい。特定の手段が相互に異なる従属形式の請求項に記載されているという単なる事実は、これらの手段の組み合わせが効果的に利用可能でないことを示すものでない。
【０１３２】
図１ａ、１ｂ、２〜５における参照番号のリスト
１００，２００，３００，４００，５００  複合テーブルネットワーク
１１０  テーブル又はテーブルネットワークの系列
１１２，１１４  テーブル又はテーブルネットワーク
１２１  グローバルデータ入力及びグローバル状態入力
１２２  テーブル１１２のデータ出力及び状態出力
１２４  テーブル１１２の繰り返しのデータ入力及び状態入力
１２３  テーブル１１４のデータ出力及び状態出力
１２５  テーブル１１２の繰り返しのデータ出力及び状態出力
１２６  テーブル１１４の繰り返しのデータ出力及び状態出力
１３０  グローバル状態関数について構成される状態テーブル又はテーブルネットワーク
１３１  検証グローバル状態入力
１３２  検証状態出力
１３３  系列の繰り返し数
１４０  アラインテーブル又はテーブルネットワーク
１４２  ｚ関数
１４３  保護されたデータ及び状態出力
１４４  置換
１４５  保護された状態出力
１４７  アラインテーブル１４０のデータ及び状態入力
１５０  保護テーブル又はテーブルネットワーク
１６０  状態抽出テーブル
４００  計算装置
４１０  ストレージ
４４１  符号化ルックアップテーブル
４４２  復号化ルックアップテーブル
４５０  コンピュータプロセッサ
４５５  機械語コード
４６０  Ｉ／Ｏ装置
４２１，４２２  単一入力ルックアップテーブル
４３１，４３２  複数入力ルックアップテーブル
４３１１，４３２３  単一入力ルックアップテーブル
【要約】
電子ストレージと、ストレージに結合される電子プロセッサとを有する計算装置であって、ストレージはテーブルネットワークの系列を記憶し、プロセッサは、テーブルネットワークの系列のテーブルネットワークを適用することによって、グローバルデータ入力とグローバル状態入力とに対して繰り返される関数を計算するよう構成され、系列のテーブルネットワークは、対応するデータ関数と状態関数とについて構成され、対応するデータ関数に従ってデータ入力をデータ出力にマッピングし、状態関数に従って状態入力を状態出力に同時にマッピングするよう構成され、電子プロセッサは、テーブルネットワークの系列の適用を繰り返すよう構成され、繰り返し適用されるテーブルネットワークのテーブルネットワークをグローバルデータ入力とグローバル状態入力とに適用し、繰り返しの後続のテーブルネットワークを系列の前のテーブルネットワークのデータ出力と状態出力とに適用し、系列の繰り返される適用は、グローバルデータ入力に対してグローバルデータ関数を決定し、グローバル状態入力に対してグローバル状態関数を決定し、これにより、中間データ出力と中間状態出力とを取得し、電子ストレージは更に、系列のテーブルネットワークになされた変更に対処するためテーブルネットワークの系列と連携するよう構成される保護テーブルネットワークを記憶し、保護テーブルネットワークは、中間状態出力とグローバル状態入力とを入力として受信するよう構成され、保護テーブルネットワークは、グローバル状態入力に適用されるグローバル状態関数が中間状態出力を生成することを検証するよう構成される計算装置。【図１ａ】
0006046870.tif 000032
【図１ｂ】
0006046870.tif 000033
【図２】
0006046870.tif 000034
【図３】
0006046870.tif 000035
【図４】
0006046870.tif 000036
【図５】
0006046870.tif 000037
【図６】
0006046870.tif 000038
【図７】
0006046870.tif 000039