(57)【特許請求の範囲】
【請求項１】
可換環において難読化された算術を実行するための電子計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算装置は、環要素をエンコードする整数リストに対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リストは、環要素を、該環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しくなるようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算装置は、
・増分環要素について定義された増分テーブルを記憶するよう構成された記憶部を有しており、
・前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなるよう入力環要素を出力環要素をエンコードする出力整数リストにマッピングし、
当該計算装置はさらに、環加算ユニットを有しており、前記環加算ユニットは、
・第一の加算入力環要素をエンコードする第一の加算入力整数リストおよび第二の加算入力環要素をエンコードする第二の加算入力整数リストを受領する段階であって、前記増分環要素は前記第一および第二の加算入力環要素から独立である、段階と、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定する段階であって、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、段階とを実行するよう構成されており、
前記加算出力整数リストを決定することが、
・一つまたは複数の基本元の冪乗の線形結合である環要素への前記増分テーブルの第一の適用によって、中間加算環要素をエンコードする中間加算整数リストを決定する段階であって、前記冪乗は前記第一および第二の加算入力整数リストから決定される、段階と、
・前記加算出力整数リストを決定する段階であって、前記中間加算整数リストから決定されるおよび前記第二の加算入力整数リストから決定される環要素への前記増分テーブルの第二の適用を含む、段階とを含む、
計算装置。
【請求項２】
環乗算ユニットをさらに有しており、前記環乗算ユニットは、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リストおよび第二の乗算入力環要素をエンコードする第二の乗算入力整数リストを受領する段階と、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定する段階であって、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、段階とを実行するよう構成されている、
請求項１記載の計算装置。
【請求項３】
前記整数リストが環要素をエンコードする仕方は、
・前記環要素が、基本元を前記整数リストの第一の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを引いたものに任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたものに、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを足したものに任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたもの、かける、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数のマイナスによって決定される冪乗にしたものを引いたものに任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数および第二の整数の第一の線形結合である冪乗にしたもの、足すまたは引く、前記基本元を前記第一の整数および前記第二の整数の第二の線形結合である冪乗にしたものに任意的に定数を乗算したものに等しくなるようにするものである、
請求項１または２記載の計算装置。
【請求項４】
前記中間加算整数リストを決定することがさらに、前記第一および第二の加算入力整数リストから決定された整数を、第一の適用から帰結する整数リスト中の整数に加算することを含む、請求項１記載の計算装置。
【請求項５】
・前記増分テーブルは、前記一つまたは複数の基本環要素を前記第一の整数リストの第一の整数から前記第二の整数リストの第一の整数を引いたもの乗したもの、足すまたは引く、ある基本環要素を前記第一の整数リストの第二の整数から前記第二の整数リストの第一の整数を引いたもの乗したもの、によって形成される環要素に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素を前記第一の整数リストの前記第一の整数から前記第一の整数リストの第二の整数を引いたもの乗したもの、足すまたは引く、ある基本環要素を前記第二の整数リストの第一の整数から前記第一の整数リストの前記第二の整数を引いたもの乗したもの、によって形成される環要素に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素を前記第一の整数リストの第二の整数から前記第一の整数リストの第一の整数を引いたもの乗したもの、足すまたは引く、ある基本環要素を前記第二の整数リストの第一の整数から前記第一の整数リストの前記第一の整数を引いたもの乗したもの、によって形成される環要素に適用される、
請求項１ないし４のうちいずれか一項記載の計算装置。
【請求項６】
・前記増分テーブルの前記第二の適用の前に、前記中間加算整数リストによって表わされる前記中間加算環要素が否定にされる、
請求項１ないし４のうちいずれか一項記載の計算装置。
【請求項７】
・整数リストによって表わされる環要素が、該整数リストを並べ替えることによって否定にされる、または
・整数リストによって表わされる環要素が、該整数リストの各整数に定数を加えるることによって否定にされる、または
・整数リストによって表わされる環要素が、該整数リストを並べ替え、該整数リストの一つまたは複数の整数に定数を乗算することによって否定にされる、
請求項１ないし６のうちいずれか一項記載の計算装置。
【請求項８】
前記増分テーブルが、前記入力環要素を表わす入力整数リストを入力として取る、請求項１ないし７のうちいずれか一項記載の計算装置。
【請求項９】
乗算出力整数リストを決定することが、
・前記第一および第二の乗算入力整数リストから、それぞれ第一および第二の中間乗算還要素をエンコードする第一の中間乗算整数リストおよび第二の中間乗算整数リストを決定し、
・前記第一および第二の中間乗算整数リストを前記環加算ユニットを通じて加算することを含む、
請求項２記載の計算装置。
【請求項１０】
・前記第一の中間乗算整数リストの第一の整数は、前記第一の乗算入力整数リストの第一の整数、足す、前記第二の乗算入力整数リストの第一の整数であり、
・前記第一の中間乗算整数リストの第二の整数は、前記第一の乗算入力整数リストの第一の整数、足す、前記第二の乗算入力整数リストの第二の整数であり、
・前記第二の中間乗算整数リストの第一の整数は、前記第一の乗算入力整数リストの第二の整数、足す、前記第二の乗算入力整数リストの第二の整数であり、
・前記第二の中間乗算整数リストの第二の整数は、前記第一の乗算入力整数リストの第二の整数、足す、前記第二の乗算入力整数リストの第一の整数である、
請求項９記載の計算装置。
【請求項１１】
・前記可換環が、ある整数を法とする整数によって形成される環である、または
・前記可換環が、ある整数多項式を法とする整数多項式によって形成される環である、
請求項１ないし１０のうちいずれか一項記載の計算装置。
【請求項１２】
請求項１ないし１１のうちいずれか一項記載の計算装置と、環エンコード装置とを有するシステムであって、前記環エンコード装置は、
・一つまたは複数の基本環要素について定義されたエンコード・テーブルを記憶するよう構成された記憶部を有しており、前記エンコード・テーブルは、環要素を、環要素が前記一つまたは複数の基本環要素の冪乗の線形結合に等しいように整数リストにマッピングするものであり、前記冪乗は前記整数リストによって決定される指数をもち、
前記環エンコード装置は、可換環の環要素を整数リストとしてエンコードするよう構成されており、
前記計算装置は、コンピュータ・ネットワークを通じて、エンコードされた情報を受領するよう構成されている、
システム。
【請求項１３】
請求項１ないし１１のうちいずれか一項記載の計算装置と、環デコード装置とを有するシステムであって、前記環デコード装置は、
・コンピュータ・ネットワークを通じて、前記計算装置から受領された整数リストを可換環の環要素にデコードし、
・一つまたは複数の基本環要素について、前記環要素を、前記環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しいように決定するよう構成されており、前記冪乗は前記整数リストによって決定される指数をもつ、
システム。
【請求項１４】
可換環において難読化された算術を実行するための計算装置において使うための増分テーブルを計算するテーブル計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、前記計算装置は、環要素をエンコードする整数リストに対して作用し、前記整数リストは少なくとも二つ整数を有し、当該テーブル計算装置は、
・増分テーブルを構築するよう構成されたテーブル生成ユニットを有し、前記テーブル生成ユニットは、
・入力環要素を反復的に選択し、
・固定した増分環要素が前記入力環要素に環加算されたものに等しい出力環要素を決定し、
・前記出力環要素についてエンコードする出力整数リストを決定し、
・前記入力環要素を前記出力整数リストにマッピングするエントリーを増分テーブルに追加するよう構成されており、
当該テーブル計算装置は、構築された増分テーブルを前記計算装置内に記憶するよう構成されている、
テーブル計算装置。
【請求項１５】
可換環において難読化された算術を実行するための、計算装置によって実行される電子的な計算方法であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算方法は、環要素をエンコードする整数リストに対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リストは、環要素を、該環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しくなるようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、
前記計算装置の記憶部は、増分環要素について定義された増分テーブルを記憶しており、前記増分テーブルは、出力環要素が固定した増分環要素が入力環要素に環加算されたものに等しくなるよう入力環要素を出力環要素をエンコードする出力整数リストにマッピングするものであり、
当該計算方法は、前記計算装置の環加算ユニットによって環加算する段階を含み、前記環加算は、
・前記環加算ユニットが、第一の加算入力環要素をエンコードする第一の加算入力整数リストおよび第二の加算入力環要素をエンコードする第二の加算入力整数リストを受領し、
・前記環加算ユニットが、前記第一および第二の加算入力整数リストから決定される環要素に前記記憶部に記憶されている前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定することを含み、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しく、
前記加算出力整数リストを決定することが、
・一つまたは複数の基本元の冪乗の線形結合である環要素への前記増分テーブルの第一の適用によって、中間加算環要素をエンコードする中間加算整数リストを決定する段階であって、前記冪乗は前記第一および第二の加算入力整数リストから決定される、段階と、
・前記加算出力整数リストを決定する段階であって、前記中間加算整数リストから決定されるおよび前記第二の加算入力整数リストから決定される環要素への前記増分テーブルの第二の適用を含む、段階とを含む、
電子的な計算方法。
【請求項１６】
当該計算方法がさらに、前記計算装置の環乗算ユニットによって環乗算する段階を含み、前記環乗算は、
・前記環乗算ユニットが、第一の乗算入力環要素をエンコードする第一の乗算入力整数リストおよび第二の乗算入力環要素をエンコードする第二の乗算入力整数リストを受領し、
・前記環乗算ユニットが、前記第一および第二の乗算入力整数リストから決定される環要素に前記記憶部に記憶されている前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定することを含み、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、
請求項１５記載の電子的な計算方法。
【請求項１７】
プログラム可能な装置で実行されたときに請求項１５または１６記載の方法を実行するよう構成されているコンピュータ・プログラム命令を有するコンピュータ・プログラム。
【請求項１８】
・請求項１７記載のコンピュータ・プログラムを有する、
コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電子計算装置、環エンコード装置、環デコード装置、テーブル計算装置、電子計算方法、コンピュータ・プログラムおよびコンピュータ可読媒体に関する。
【背景技術】
【０００２】
ホワイトボックス暗号法およびより一般にはソフトウェア難読化において、計算はしばしば、そのままの値ではなくエンコードされた値に対して実行される。計算が平文値自身ではなくエンコードされた値に対して実行される場合、難読化されたソフトウェアのリバースエンジニアリングはより難しくなる。
【０００３】
エンコード後は、加算または乗算のような通常の演算はもはや、コンピュータの組み込みプリミティブを使って実行することはできない。エンコードされた値のストレートな加算は通常は、値の和のエンコードにはならない。同じことは乗算についてもいえる。公式でいうと、たいていのxおよびyについて、E(x)＋E(y)≠E(x＋y)となる。ここで、Eはエンコード関数を表わす。
【０００４】
この問題への解決策は、加算（A）および乗算（M）テーブルを導入することである。それらのテーブルは二つのエンコードされた値を入力として取り、加算演算または乗算演算のエンコードに対応するエンコードされた値を出力として生成する。それらのテーブルは：A(E(x),E(y))＝E(x＋y)；M(E(x),E(y))＝E(xy)として定義されてもよい。これらのテーブルは、エンコードされた値に対して直接、算術が実行されることを許容する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
テーブルを使った難読化された加算および乗算には少なくとも二つの欠点がある。第一に、テーブルがきわめて大きなものとなることがある。xおよびyがl〔エル〕ビットとして表わされる場合、各テーブルは22l・lビットを必要とする。
【０００６】
第二に、そのようなテーブルは簡単にソフトウェアにおいて見出されうる。より悪いことに、それらのテーブルは、エンコードされていたとしても、加算または乗算演算として識別されうる。これはたとえばエンコードにおいて保存されるこれらの関数の特性を通じてである。たとえば、乗算テーブルはM(E(0),E(x))＝E(0)を満たす。攻撃者はこのことおよび同様の特性を使ってテーブルがどの演算を表わしているかを推測しうる。
【課題を解決するための手段】
【０００７】
難読化された算術を実行するための改良された仕方をもつことが有利であろう。請求項において定義されるような計算装置が提供される。
【０００８】
本発明者らは、場合によっては、エンコードされた値に対する乗算および加算が、複数の値を単一のエンコードされた値にエンコードする必要なく、単一のテーブルを使って実行されうることを見出した。加算および乗算について同じテーブルが使用されるので、リバースエンジニアリングの際に加算または乗算のどちらが実行されるのかを見ることは困難になる。加算および乗算は外部から見たときは同じ演算に見えるので、本発明者らはこの方法を「同質難読化（homogenous  obfuscation）」と名付けた。たとえ攻撃者が使用されているテーブルをみつけることができたとしても、またどうにかしてその機能を増分テーブルとして割り出すことができたとしても、いまだ、加算または乗算演算のどちらが実行されるかを知ることはできない。テーブルが整数リストの要素に対して作用する仕方は、加算と乗算とで異なるが、これは、コード難読化、ホワイトボックス実装などといった伝統的な難読化を使って容易に隠すことができる。
【０００９】
加えて、使用される単一テーブルは背景技術において論じたものより小さい。約2l・lビットが必要とされる。たとえ加算のみが使用されるとしても、難読化された加算のために必要とされるテーブルは背景技術において提案されているテーブルより小さい。
【００１０】
本発明は、多くの異なる可換環Rに適用される。ただし、あらゆる環が整数リストとしてのエンコードを許容するわけではない。可換環は、多くの異なるおなじみの数学的構造、たとえばある数を法とする整数（Zn）またはある数および多項式を法とする多項式（Zn[x]/f(x)）を含む数学的概念である。体は可換間の特別な場合である。本稿で記述されるように、当業者は所与の環が上記難読化を許容するかどうかを検証できる。
【００１１】
たとえば、環要素〔環の元〕は二つの整数(a,b)としてエンコードされうる。算術は、エンコードされた環要素を該エンコードされた環要素に増分値を加えたものにマップする増分テーブルを使って、該エンコードに対して直接実行されることができる。たとえば、テーブルは、uc−ud＝ua−ub＋1である場合に(a,b)を(c,d)にマップしてもよい。加算および乗算はいずれも、該増分テーブルの反復適用によって実行される。
【００１２】
本稿でより十全に論じられるように、他の多くの可能性および変形がある。典型的には、任意の所与の実装において多くの変形のうちのどれが選ばれたかは攻撃者には未知である。
【００１３】
計算装置は電子装置であり、モバイル電子装置、たとえば携帯電話、セットトップボックス、コンピュータ、スマートカードなどであってもよい。
【００１４】
本稿に記載される難読化された算術は、幅広い範囲の実際的なアプリケーションにおいて適用されうる。そのような実際的なアプリケーションは、リバースエンジニアリングが防止されるべき、プライベートなハードウェアで走る安全なアプリケーション、たとえばバンキング・アプリケーションなどを含む。他のアプリケーションは、不用意なデータ漏洩が防止されるべきアプリケーションを含む。プログラムがプライベートなデータをリリースするようだまされる場合、漏れたデータがエンコードされていれば、懸念の度合いは低下する。難読化された算術は、アプリケーションを走らせているサーバーにも適用されうる。ユーザーがエンコードされた形でデータを送受信すれば、プライバシーが高まる。
【００１５】
本発明に基づく方法は、コンピュータ上でコンピュータ実装される方法として、あるいは専用ハードウェアにおいて、あるいは両者の組み合わせにおいて実装されうる。本発明に基づく方法のための実行可能コードまたはその一部はコンピュータ・プログラム・プロダクトに記憶されうる。コンピュータ・プログラム・プロダクトの例はメモリ・デバイス、光記憶デバイス、集積回路、サーバー、オンライン・ソフトウェアなどを含む。好ましくは、コンピュータ・プログラム・プロダクトは、前記プログラム・プロダクトがコンピュータ上で実行されるときに本発明に基づく方法を実行するためのコンピュータ可読媒体上に記憶された非一時的なプログラム・コード手段を有する。
【００１６】
ある好ましい実施形態では、コンピュータ・プログラムは、該コンピュータ・プログラムがコンピュータ上で実行されるときに本発明に基づく方法のすべての段階を実行するよう適応されたコンピュータ・プログラム・コード手段を有する。好ましくは、コンピュータ・プログラムはコンピュータ可読媒体上で具現される。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Chow  et  al,  "Whitebox  cryptography  and  an  AES  implementation"
【図面の簡単な説明】
【００１８】
本発明のこれらおよび他の側面は、以下に記載される実施形態から明白となり、これを参照することで明快にされるであろう。
【図１ａ】計算装置１００のある実施形態の例を概略的に示す図である。
【図１ｂ】環加算ユニット１３０のある実施形態の例を概略的に示す図である。
【図１ｃ】環乗算ユニット１４０のある実施形態の例を概略的に示す図である。
【図２】計算装置１０１のある実施形態の例を概略的に示す図である。
【図３】計算装置において使うための増分テーブルを計算するためのテーブル計算装置２００のある実施形態の例を概略的に示す図である。
【図４】難読化された算術を実行するための計算方法３００のある実施形態の例を概略的に示す図である。
【図５】加算方法４００のある実施形態の例を概略的に示す図である。
【図６】乗算方法５００のある実施形態の例を概略的に示す図である。
【図７】ａは、ある実施形態に基づくコンピュータ・プログラムを有する書き込み可能部分をもつコンピュータ可読媒体を示しており、ｂは、ある実施形態に基づくプロセッサ・システムの概略図である。  異なる図面において同じ参照符号をもつ項目は同じ構造的特徴および同じ機能をもつまたは同じ信号である。そのような項目の機能および／または構造が説明された場合、詳細な記述におけるその反復説明は必要ない。
【発明を実施するための形態】
【００１９】
本発明は多くの異なる形の実施形態が可能であるが、本開示は、本発明の原理を例解するものと考えられ、本発明を図示および記述される個別的な実施形態に限定することは意図されていないとの理解のもとに、一つまたは複数の個別的実施形態について図面に示し、本稿で詳細に記述する。
【００２０】
以下では、理解のために、実施形態の諸要素が動作において記述される。しかしながら、それぞれの要素がそれらによって実行されると記述されている機能を実行するよう構成されていることは明白であろう。
【００２１】
電子計算装置は、驚くほど小さいテーブルを使って効率的な算術を実行する。さらに、難読化された算術の技術分野では、演算がテーブルを通じて実行できればそれは利点であると考えられる。そのような演算は、たとえば伝統的なホワイトボックス技法（たとえば非特許文献１参照）を使って、容易にさらに難読化されうるからである。よって、算術演算をテーブルを使って表現する必要がある。実施形態は、従来技術よりも小さなテーブルを使って加算を実装する。たとえホワイトボックス暗号法のような追加的な難読化がなくても、電子計算装置は難読化に寄与する。本稿で示されるように、エンコードおよび増分テーブルが実装されうる多くの仕方がある。何らかの特定の実施形態においてどのエンコードが使われているかは攻撃者には未知であり、よって観察される計算は解釈するのがより困難になる。
【００２２】
実施形態は、乗算および加算演算が同じテーブルを使って実行されることを許容する。これはさらに、難読化に対する上乗せとなる。もはや、増分テーブルが使われるという事実から、どの演算が実行されるかを判別することはできないからである。下記では、まず、計算装置の実施形態のいくつかの可能なアーキテクチャーが論じられる。次に、難読化された算術を実行するためのいくつかの代替が論じられる。
【００２３】
図１は、計算装置１００のある実施形態の例を概略的に示している。計算装置１００は、有限可換環において難読化された算術を実行するための電子装置である。可換環の多くの例が知られている。下記では二つのそのような環：ある数を法とする整数（Zn）およびある数および多項式を法とする多項式（Zn[x]/f(x)）について例が与えられる。他の実施形態は他の可換環を使ってもよい。
【００２４】
環の要素は環要素〔環の元〕と称される。環要素に対して、加算と乗算が定義される。これらは環加算および環乗算と称される。
【００２５】
環要素は、必要に応じていかなる好適な形で表現されてもよい。たとえば、Znの要素は整数として表現されてもよく；Zn[x]/f(x)の要素は多項式として表現されてもよい。しかしながら、計算装置１００においては、環要素は整数リストとして表現される。たとえば、環要素aは計算装置１００において、リスト(a1,a2)として表現される。これは非整数環、たとえば多項式環についてさえも成り立つ。整数リストは環要素を、環要素と整数リストとの間の何らかのマッピングに従ってエンコードする。任意の環要素が与えられると、その環要素を表わす少なくとも一つの整数リストがあり、任意の整数リストを与えられると、それが表わすちょうど一つの環要素がある。諸実施形態において、任意の環要素が整数リストとして表現されうる。
【００２６】
整数リストは少なくとも二つの要素をもつ。実のところ、加算および乗算演算は、整数リストが短いほど必要とするステップが少なくなる。よって、ある実施形態では、整数リストは常に二つの要素をもつ。メインの記述では、整数リストは整数対であると想定するが、三つ以上の要素をもつ整数リストの例も与えられる。一例として、(a1,a2)は環要素
【００２７】
【数１】
0006621813.tif 000002
にマップしてもよい。ここで、uは、基本環要素〔基本の環の元〕（base  ring  element）と称される特別な環要素である。複数の基本元を使うものを含め多くの変形が下記で論じられる。しかしながら、メインの議論では、「例示的エンコード」として、所与の整数リスト(a1,a2)が環要素
【００２８】
【数２】
0006621813.tif 000003
にマップすると想定する。
【００２９】
ある実施形態では、整数リスト中の整数は非負である。これは計算を単純化するが、必要ではない。さらに、ある実施形態では、整数リスト中の整数は、基本元の位数を法とされる。基本元uの位数は、uk＝1となる最小の整数kである。たとえばkを法とする演算を実行することによって整数リスト中の値を範囲［0,k−1］内に保つことが便利である。
【００３０】
計算装置１００はオペランド・ストア１５０を有していてもよい。オペランドは、オペランド・ストア１５０に整数リストとして記憶される。算術は、オペランド・ストア１５０に記憶されているオペランドに対して実行されてもよい。算術の結果はオペランド・ストア１５０に記憶されてもよい。ここで、算術の結果は新たな演算において使われてもよく、あるいは異なる装置に出力されるなどしてもよい。
【００３１】
計算装置１００は、ある増分環要素（increment  ring  element）について定義された増分テーブルTを記憶するよう構成されている記憶部１１０を有する。増分テーブルは入力環要素を、出力環要素をエンコードする出力整数リストにマップし、出力環要素は、増分環要素が入力環要素に環加算されたものに等しくなる。ある実施形態では、入力環要素は整数リストとして表現される。このようにして、テーブルTは整数リストを整数リストにマップする。いずれも同じエンコード、たとえば同じマッピングに基づいている。しかしながら、入力環要素が代替的なエンコードでの整数リストとして表現されている実施形態がある。いずれにせよ、入力環要素はデジタル形式で表現され、テーブルが入力環要素を出力環要素にマップすることを許容する。
【００３２】
テーブルは、何らかのフォーマットの入力環要素を、関連付けられた出力整数リストと一緒にリストしてもよい。テーブルは、入力環を省略して、出力整数リストのみをリストすることによって、記憶部において表現されてもよい。たとえば、これは、入力環が正準フォーマットで表現される場合になされてもよい。
【００３３】
たとえば、上記例示的エンコードを想定すると、入力環要素
【００３４】
【数３】
0006621813.tif 000004
はテーブルTによって出力整数リストにマッピングされてもよい。この場合、入力環要素は整数リストとして表現されてもよく、((k1,k2))＝(l1,l2)となりうる。この右辺は出力環要素
【００３５】
【数４】
0006621813.tif 000005
をエンコードする。出力環要素は増分環要素が入力環要素に環加算されたものに等しい。たとえば、増分環要素が1であれば、l＝k＋1である。ある実施形態では、増分要素は1であってもよいが、これは必須ではない。たとえば、上記例示的エンコードを使うと、増分要素は、tの何らかの値、たとえば0≦t＜位数(u)となる任意の値についてのutと選んでもよい。
【００３６】
増分テーブルは、背景技術において述べたテーブルよりずっと小さい。背景技術のテーブルは二つの入力、たとえば二つのエンコードされた数を受けて、エンコードされた出力を生じる。しかしながら、テーブルTは、一つのエンコードされた出力を生じるために一つのエンコードされた入力を取るだけであり、増分環要素は固定されている。両者のエンコードが同様の量のスペースを取るとすると、Tの入力スペースはほぼ平方根に低減される。これはかなりのサイズ改善である。
【００３７】
計算装置１００は環加算ユニット１３０および環乗算ユニット１４０を有する。計算装置１００は環否定ユニット１２０をも有していてもよい。ある実施形態では、環乗算ユニット１４０は、加算を実行するために加算ユニット１３０を使ってもよい；加算ユニット１３０は否定ユニット１２０を使ってもよい。これは、図１では、ユニット１２０、１３０、１４０の間の線によって示されている。しかしながら、ユニットは二重にあってもよく、たとえば、加算ユニット１３０が自分自身の否定を行なってもよく、乗算１４０が自分自身の加算を行なってもよい。否定（negation）は「符号の変化」とも称される。
【００３８】
否定ユニット１２０は、否定入力環要素（negation-input  ring  element）aをエンコードする否定入力整数リスト（negation-input  integer  list）(a1,a2)を受領してもよい。否定ユニット１２０は、否定出力環要素（negation-output  ring  element）bをエンコードする否定出力整数リスト(b1,b2)を決定するよう構成されている。否定出力環要素は、否定入力環要素の符号を変えたものである。たとえば、否定出力環要素は、加法についての中立環要素（0）から否定入力環要素を引いたものに等しい。よって、b＝−aである。
【００３９】
ある実施形態では、否定ユニットは、否定入力整数リストを並べ替えることによって出力整数リストを計算してもよい。上記例示的エンコード
【００４０】
【数５】
0006621813.tif 000006
を使うと、出力整数リストは(a2,a1)であってもよい。並べ替えによる否定は、要素の読み出し元のアドレスを変えることによってコードにおいて効率的に実装でき、必ずしもメモリにおける実際の順序を変えるものではない。
【００４１】
ある実施形態では、否定ユニットは、整数リストの各整数に定数を加算することによって出力整数リストを計算してもよい。たとえば、上記例示的エンコードにおいてum＝−1となるような整数mを使うと、たとえば、出力整数リストは(a1＋m,a2＋m)となりうる。
【００４２】
環加算ユニット１３０は、第一の加算入力環要素をエンコードする第一の加算入力整数リスト(a1,a2)と第二の加算入力環要素をエンコードする第二の加算入力整数リスト(b1,b2)とを受領するよう構成される。たとえば、環加算ユニット１３０は、これら二つのオペランドをオペランド・ストア１５０から受領してもよい。環加算ユニット１３０は、第一および第二の加算入力整数リストから決定される環要素に増分テーブルを適用することによって、加算出力環要素をエンコードする加算出力整数リストを決定するよう構成される。加算出力環要素は、第一の加算入力環要素および第二の加算入力環要素の環加算に等しい。
【００４３】
ある実施形態では、整数リストの特定の環要素へのマッピングは複数のサブマッピングを含み、各サブマッピングは整数リストの整数と関連付けられ、サブマッピングは整数を環要素にマッピングする。マッピングは、関連付けられた整数に適用されるサブマッピングの線形結合、例えば和である。サブマッピングは、基本元を、関連付けられた整数によって決定される冪乗にすることであってもよい。たとえば、上記の例示的エンコードにおいて、(a1,a2)は、サブマッピング
【００４４】
【数６】
0006621813.tif 000007
の和であると言われてもよい。
【００４５】
図１ｂは、加算ユニット１３０のある実施形態を示している。加算ユニット１３０は第一の加算入力整数リスト１３１および第二の加算入力整数リスト１３２を受領する。加算ユニット１３０は、第二の加算入力整数リスト１３２の整数から得られた環要素を、第一の加算入力環要素に逐次反復的に加算するよう構成された中間加算ユニット１３４を有する。たとえば、中間加算ユニット１３４は、第一の整数リスト要素に初期化される中間和１３３に対して加算してもよい。加算は、記憶部１１０からの増分テーブルの適用に関わる。
【００４６】
環乗算ユニット１４０は、第一の乗算入力環要素をエンコードしている第一の乗算入力整数リスト(r1,r2)および第二の乗算入力環要素をエンコードしている第二の乗算入力整数リスト(s1,s2)を受領する。たとえば、乗算ユニット１４０は、第一および第二の乗算入力整数リストから決定される環要素に増分テーブルを適用することによって乗算出力環要素をエンコードしている乗算出力整数リストを決定するよう構成される。乗算出力環要素は第一の乗算入力環要素および第二の乗算入力環要素の環乗算に等しい。
【００４７】
図１ｃは、乗算ユニット１４０のある可能な実施形態を示している。乗算ユニット１４０は第一の乗算入力整数リスト１４１および第二の乗算入力整数リスト１４２を受領する。乗算ユニット１４０は、第一および第二の乗算入力整数リスト１４１、１４２から、それぞれ第一および第二の中間乗算還要素をエンコードする第一の中間乗算整数リスト１４５  (t1,t2)および第二の中間乗算整数リスト１４６  (u1,u2)を決定するよう構成された中間乗算ユニット１４４を有する。乗算ユニット１４０は、第一１４５および第二の中間乗算整数リスト１４６を環加算ユニット１３０を通じて加算するよう構成される。中間整数リストを決定することは、整数リスト内の整数に対する算術演算に関わってもよいが、増分テーブルを要求しない。
【００４８】
計算装置１００は任意的には、可換環の環要素を整数リストとしてエンコードするための環エンコード・ユニット１７０と、整数リスト(a,b)を可換環の環要素（x）にデコードするための環デコード・ユニット１６０とを有する。エンコード・ユニット１７０および／またはデコード・ユニット１６０は、たとえば計算装置１００がエンコードされた入力を受け取るおよび／またはエンコードされた出力を報告するときは、不在であってもよい。エンコード・ユニット１７０および／またはデコード・ユニット１６０は、スタンドアローンのユニットとして、たとえばエンコード装置および／またはデコード装置１６０として実装されてもよい。
【００４９】
環エンコード・ユニット１７０は、一つまたは複数の基本環要素（u）について定義されたエンコード・テーブルを記憶するよう構成された記憶部１７２を有していてもよい。該エンコード・テーブルは、環要素（x）を整数リスト（(a,b)）にマッピングして、環要素が前記一つまたは複数の基本環要素の冪乗の組み合わせに等しくなるようにする（x＝ua−ub）。ここで、冪乗は、前記整数リストによって決定された指数をもつ。エンコード・ユニット１７０は、エンコードされた環要素をオペレーター・ストア１５０において記憶してもよい。エンコード・ユニット１７０はシステムが平文情報とともに機能することを許容する。
【００５０】
環デコード・ユニット１６０は、一つまたは複数の基本環要素（u）について、環要素（x）を決定し、前記環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しくなるようにする（x＝ua−ub）。ここで、冪乗は、整数リストによって決定された指数をもつ。たとえば、デコード・ユニット１６０は、整数リストを環要素にマッピングするデコード・テーブルを記憶しているストアを有していてもよい。たとえば、デコード・ユニット１６０は、前記冪乗およびその線形結合を計算する計算ユニットを有していてもよい。
【００５１】
多くの興味深い実施形態は、エンコードおよびデコード・ユニット１６０および１７０の一方または両方を省略する。たとえば、計算装置１００は、エンコードされた情報を、コンピュータ・ネットワーク、たとえばインターネットを通じて受領するよう構成されてもよい。難読化された計算装置１００が走るシステム、たとえば難読化された計算ソフトウェアを実行するコンピュータの権利者は、入力情報のためや、システム１００によって出力される、たとえばコンピュータ・ネットワークを通じて送信し返される情報のために使われたエンコードを知らなくてもよい。よって、たとえ計算がクラウドで実行されるとしても、情報の所有者は、自分の情報が安全であるといういくらかの安心をもつ。エンコードされた形での情報に対する演算は典型的には暗号法、たとえば暗号化を使っては可能ではない。たとえ背景技術において概説されたようにテーブル・システムが使われるとしても、これは二つのテーブルを必要とする。
【００５２】
典型的には、計算装置１００は、装置１００において記憶された適切なソフトウェアを実行するマイクロプロセッサを有する。たとえば、そのソフトウェアは、対応するメモリ、たとえばRAMのような揮発性メモリまたはフラッシュ（図示せず）のような不揮発性メモリ（図示せず）においてダウンロードされているおよび／または記憶されているのでもよい。あるいはまた、装置１００は、全体的にまたは部分的に、プログラム可能な論理において、たとえばフィールドプログラマブルゲートアレイ（FPGA）として実装されてもよい。装置１００は全体的または部分的に、いわゆる特定用途向け集積回路（ASIC）、すなわち特定の用途のためにカスタマイズされる集積回路（IC）として実装されてもよい。
【００５３】
ある実施形態では、電子計算装置は、対応するユニットの機能を実行するよう構成された環加算回路および環乗算回路を有する。計算装置は、否定回路をも有していてもよい。該回路は、たとえばVerilogおよびVHDLのようなハードウェア記述言語において機能を記述することによって得られる、CMOSのような集積回路であってもよい。それらの回路は、プロセッサ回路および記憶回路であってもよく、プロセッサ回路が記憶回路に電子的に表現されている命令を実行してもよい。それらの回路もFPGA、ASICなどでありうる。
【００５４】
テーブル・ストア１１０およびオペランド・ストア１５０は電子記憶、たとえばメモリとして実装されてもよい。両者は同じメモリの一部であってもよいが、相異なるメモリであってもよい。テーブル・ストア１１０は不揮発性の非書き込み可能なもの、たとえばROMまたは一度書き込み複数読み出し（WORM）メモリであってもよい。オペランド・ストア１５０は揮発性または不揮発性の書き込み可能なメモリ、たとえばフラッシュまたはRAMであってもよい。
【００５５】
図２は、計算装置１０１のある実施形態の例を概略的に示している。計算装置１０１は計算装置１００の洗練である。ある実施形態では、計算装置１０１は複数環加算ユニット、複数の環乗算ユニットおよび任意的には複数の否定ユニットを有する。たとえば、図２は、三つの乗算ユニット１４０．１、１４０．２および１４０．３および二つの加算ユニット１３０．１および１３０．２を示している。これらのユニットは、それぞれユニット１４０および１３０と同じ設計であってもよい。乗算および加算ユニットは比較的小さなスペースを取る。たとえば、ソフトウェアで実装されるとき、これらのユニットは高々数百の低レベルのコンピュータ命令しか必要としない。特に、コンピュータ・プログラムにおいて必要とされるそれぞれの乗算または加算について、上記加算および／または乗算ユニットのコピーが使用されてもよい。このことは、伝統的な難読化技法を許容する。例として、図２は、難読化された算術を使って、多項式ax2＋bx＋cがどのようにして計算されうるかを示している。
【００５６】
複数の算術ユニット、たとえば加算、乗算、否定、の演算は、そのデータ依存性によって許容されるいかなる順序で順序付けられてもよい。たとえば、演算１４０．３は順序１４０．１、１４０．２、１３０．１および１３０．２において１３０．１より前のどの点に挿入されてもよい。さらに、その後の乗算または加算の順序は逆にされてもよい。こうして、図２のような図は、多くの仕方で、ソフトウェア・プログラムのための線形な順序に変換されてもよい。これらのユニットが厳密に分離されることは必要ではない。第一のユニットのための命令は別のユニットのための命令の間に散りばめられてもよい。
【００５７】
図３は、計算装置において使うための増分テーブルを計算するためのテーブル計算装置２００のある実施形態の例を概略的に示している。増分テーブルは、計算装置１００のような装置において使われてもよい。増分テーブルは、非一時的な記憶装置、たとえばハードディスク、不揮発性メモリ・チップなどに記憶されてもよい。
【００５８】
テーブル計算装置２００は、増分テーブルを構築するよう構成されたテーブル生成ユニット２１０を有する。たとえば、テーブル生成ユニットは下記を実行するよう構成されていてもよい。
・入力環要素、たとえばxを反復的に選択する。
・増分環要素が入力環要素に環加算されたものに等しい出力環要素を決定する。たとえば、増分値が1であればy＝x＋1。
・出力環要素についてエンコードする出力整数リストを決定する。たとえば、テーブル計算装置２００は、エンコード・ユニット１７０のようなエンコード・ユニットを有していてもよい。
・入力環要素を出力整数リストにマッピングする増分テーブルにエントリーを追加する。
【００５９】
これらの段階は、すべての環の要素が整数リストにマッピングされ終わるまで実行されてもよい。いくつかの実施形態では、諸要素がスキップされて、部分的な増分テーブルを構築してもよい。たとえば、ある種の環要素が生起しないことがコンテキストから知られていてもよい。
【００６０】
環R、潜在的な基本環要素u、エンコード、たとえば上記の例示的エンコードおよび整数リスト長、たとえば2を与えられて、デコード・テーブルが下記で与えるように生成されてもよい。kはuの位数であるとする。
・あらゆる整数リストを生成する。これはたとえば、前記整数リスト長のすべての整数リストを生成し、リスト中の各位置について0からkの手前までのすべての整数を許容することによる。たとえば、(0,0),(0,1),(1,0),(1,1),(0,2),(1,2),(2,2),(2,0),(2,1),(0,3),…などを生成する。
・各生成された整数リストについて、該整数リストによってエンコードされる環要素を計算し、その整数リストをそのデコードに関連付けるエントリーをデコード・テーブルに追加する。
【００６１】
デコードは、デコード・テーブルを使っても使わなくてもよいが、そのようなテーブルも有用である。デコード・テーブルから、たとえば該テーブルを環要素についてソートすることによって、エンコード・テーブルが生成されうるからである。環要素が複数のエンコードをもつことがありうる。たとえば、環要素0（加算についての中立元）は上記の例示的エンコードでは、任意のaについて(a,a)と表現されうる。そのような複数のエンコードは、テーブルから除去されてもよい。これはたとえば、所与の環要素について、複数のエントリーのうちの一つを除いてすべてを削除することによる。あるいは複数のエンコードをテーブルに残して複数のエントリーのうちのランダムなものにエンコードするようエンコード・テーブルを使うことによる。
【００６２】
デコードまたはエンコード・テーブルの構築は、環要素uが基本環要素であるかどうかを見出すために使われてもよい。いくつかの環要素がエンコードをもたないことが判明したためエンコード・テーブルの構築が失敗したら、uは基本環要素ではない。
【００６３】
下記では、エンコード、増分テーブル、環加算方法および環乗算方法のいくつかの実施形態が呈示される。計算装置１００の前記否定、加算および乗算ユニットはこれらの実施形態の任意のもののために構成されうる。すべての例は任意の可換環、特にZnおよびZn[x]/f(x)に当てはまる。ここではnは正の整数である。さらに、可換環の任意の元が、選ばれたエンコードにおいて表現されうることが大いに好ましい。すべての可換環が、所与のエンコードにおいて、たとえば所与の型の整数リスト表現としてすべての元が表現されることを許容するわけではない。可換環Rを与えられたとき、Rにおける任意の元が所与のエンコード型を使って整数リストとして表現されうる場合、完全な同質難読化を許容するということにする。当業者は、エンコードが与えられたとき、所与の可換環が完全な同質難読化を許容するかどうかの検証を、たとえばあらゆる許容されるエンコードを生成し、それらが一緒になって所与の環のすべての元を表わすことを検証することによって、実行できる。いくつかの用途については、エンコードがいくつかのギャップをもつことが許容されてもよい。これは、結果として、それらのギャップでは、少なくともその難読化された整数リスト・エンコードを使ってでは、算術が実行できないことになりうる。特定の型のエンコードを許容する可換環の具体例はのちに呈示する。
【００６４】
下記では、まず、例示的エンコードの記述が与えられる。多くの型のエンコードがあるが、環要素が整数のリストとして表現されうることは共通している。これらの整数は環要素ではない。たとえば、環が整数環でなく、たとえば多項式環であっても元は整数リストとして表現されうる。使用されるエンコード、どのように所与の整数リストが環要素にマッピングされるかは、エンコードと称される。典型的には、整数リストは常に同じ長さであるが、これは必須ではない。一般に、エンコードがより多くの型の整数リスト、たとえばより長いリストを許容するほど、所与の環要素が異なる仕方で整数リストとしてエンコードされうる可能性が高くなる。
【００６５】
上記例示的エンコードをもつ可換環Rを与えられたとき、Rの任意の元aが何らかの整数a1およびa2についてua1−ua2と書ける特別な環要素uがある。そのような特別な環要素を基本環要素と称することにする。すべての可換環がこのやり方でエンコードされうるのではないが、十分に多くの可換環について該エンコードは有用である。整数a1およびa2はそれ自身としては環Rの環の元ではない；これらは基本元の位数を法として演算対象となる整数である。環要素aは基本元uの冪乗、つまりua1およびua2の線形結合に等しいことを注意しておく。この場合、線形結合はそれらの冪乗に＋1または−1を乗算して足すことによって、より具体的には、第一の冪乗から第一の冪乗を引くことによって、得られる。計算装置は、上記の仕方でエンコードされた環要素に対して作用する。加算、否定および乗算ユニットはこのエンコードにおいて環要素に作用できる。
【００６６】
増分テーブルTは加算および乗算演算両方において中心的な役割を演じる。増分テーブルは入力環要素をマッピングする。この場合、入力環要素は整数リストとして表現されていてもよい。たとえば、入力環要素k＝uk1−uk2を表現する入力整数リスト(k1,k2)を与えられて、テーブルTはこれを、出力環要素l＝ul1−ul2をエンコードする出力整数リストにマッピングする。たとえば、T((k1,k2))＝(l1,l2)。出力環要素は増分環要素が入力環要素に環加算されたものに等しい。この例では、増分要素は1、すなわち環乗算についての恒等元である環要素に取られてもよい。この場合、l＝k＋1である。テーブルが、同じエンコードを使う諸環要素に直接適用されうることが便利である。よって上記整数リスト表現をもつ諸環要素に適用されうる。それにもかかわらず、テーブルが代替的なエンコードにおける環要素に適用される実施形態がある。該代替的なエンコードも、代替的な型だが、整数リストであってもよい。また、増分環要素は1である必要はない。
【００６７】
下記では、演算、否定、加算および乗算が記述される。
【００６８】
否定。
否定入力環要素a＝ua1−ua2を表わす否定入力整数リスト(a1,a2)を与えられて、該整数リストを並べ替えることによって、この場合は順序を逆にすることによって、否定出力整数リストが得られてもよい。否定出力整数リストは(a2,a1)であってもよい。多くの環Rについてそうであるようにum＝−1となるmが存在するとすると、否定は代替的には、整数リストの各整数に定数、たとえばmを加算することによって得られてもよい。この場合、否定出力整数リストは(a1＋m,a2＋m)であってもよい。−a＝ua2−ua1＝ua1+m−ua2+mなので、これは成立する。整数リストにおける算術は好ましくは、基本元の位数を法として行なわれる。ここで、整数リストの整数は基本元の指数に対応する。よって、基本元の位数を法として同じである整数は同じ環要素をエンコードする。
【００６９】
加算。
第一の加算入力環要素a＝ua1−ua2をエンコードする受領された第一の加算入力整数リスト(a1,a2)および第二の加算入力環要素b＝ub1−ub2をエンコードする第二の加算入力整数リスト(b1,b2)を加算するには、まず、中間加算環要素cをエンコードする中間加算整数リスト（(c1,c2)）が決定される。
【００７０】
環要素cは、第一の加算入力環要素aに、基本元uの、第二の加算入力整数リスト、特に第二の加算入力整数リストの最初の整数から決定される冪乗を加えたものであってもよい。この例では、c＝ua1−ua2＋ub1としてもよい。これを計算するには、c＝ua1−ua2＋ub1＝(ua1-b1−ua2-b1＋1)ub1であることを観察する。括弧内の項は、増分テーブルを使うエンコードにおいて書き直されてもよい。環要素ua1-b1−ua2-b1への増分テーブルの第一の適用を通じて、要素ud1−ud2＝ua1-b1−ua2-b1＋1が得られる。たとえば、T((a1−b1,a2−b1))＝(d1,d2)による。すると、c1＝d1＋b1およびc2＝d2＋b1が得られる。このように、中間加算整数リスト（(c1,c2)）を決定することはさらに、第二の加算入力整数リストから決定された整数を第一の適用から帰結する整数リストにおける整数に加算することを含んでいてもよい。ub1を整数リスト表現におけるある環要素に、この場合はaに加えることは、時に、正の還元（positive  reduction）ステップと称される。
【００７１】
このように、加算ユニットは、中間加算環要素c＝ua1−ua2＋ub1＝uc1−uc2を整数リスト(c1,c2)として得た。中間加算環要素は、このように、一つまたは複数の基本元の冪乗の線形結合である。ここで、それらの冪乗は、第一および第二の加算入力整数リストから決定される。この場合、増分テーブルが適用されるのは、前記一つまたは複数の基本環要素（u）を第一の整数リストの最初の整数（a1）から第二の整数リストの最初の整数（b1）を引いたもの乗したものから、前記基本環要素（u）を第一の整数リストの第二の整数（a2）から第二の整数リストの最初の整数（b1）を引いたもの乗したものを引いたものによって形成される環要素ua1-b1−ua2-b1である。
【００７２】
この例では、加算出力整数リストは、中間加算整数リストおよび第二の加算入力整数リストから決定された環要素への増分テーブルの第二の適用を通じて決定されてもよい。これは、中間加算環要素cと、基本元を第二の加算入力整数リスト、たとえば第二の加算入力整数リストの第二の整数b2から決定される冪乗にしたもののマイナスとの和を計算することを含んでいてもよい：c−ub2＝uc1−uc2−ub2。これは、増分テーブルの第二の適用前に、中間加算整数リストによって表わされる中間加算環要素を否定にすることによって達成されてもよい。cの否定は、上記のようになされてもよい。例として並べ替えを使うが、同じ動作は、指数に定数を加えることによって実行されてもよい。否定後は、前記和は、基本元を第二の加算入力整数リストから決定される冪乗にしたもののプラス（マイナスではなく）を使ってもよい：−c＋ub2＝uc2−uc1＋ub2。この演算は上記と同じ型であり、ub1を加えるのと同じ仕方でテーブル適用を通じて実行できる。この後は、結果が再び否定にされる。完全な加算は、二回の否定と同じ増分テーブルTの二回のテーブル適用を使ってもよい。
【００７３】
整数リスト表現における環要素から、この場合cから−ub2を引くことは、時に負の還元（negative  reduction）ステップと称される。負の還元ステップは否定にして、上記正の還元ステップを実行し、再び否定にすることによって実行されてもよい。
【００７４】
乗算。
第一の乗算入力環要素r＝ur1−ur2をエンコードする受領された第一の乗算入力整数リスト(r1,r2)と第二の乗算入力環要素s＝us1−us2をエンコードする第二の乗算入力整数リスト（(s1,s2)）とを乗算するために、第一の中間乗算整数リスト(t1,t2)および第二の中間乗算整数リスト(u1,u2)が決定される。乗算出力環要素をエンコードする乗算出力整数リストは、第一および第二の中間要素から決定される。他の実施形態では、二つより多くの中間乗算整数リストがあってもよい。r・s＝(ur1−ur2)(us1−us2)＝ur1+s1−ur1+s2＋ur2+s2−ur2+s1＝(ur1+s1−ur1+s2)＋(ur2+s2−ur2+s1)＝t＋uとなる。展開された積の項を二つの項tおよびuに分割することは、異なる仕方で、たとえば(ur1+s1−ur2+s1)＋(ur2+s2−ur1+s2)のようになされてもよい。
【００７５】
このように、整数リストとして表現されている二つの環要素を乗算するために、それらの環要素は二つの新たな整数リストに変換されてもよく、該新たな変数リストを加算して乗算への答えを得ることができる。加算は上記のようになされてもよい。たとえば、乗算ユニットは中間整数リストを計算して、乗算ユニットに送ってもよい。
【００７６】
たとえば、第一の中間乗算整数リストの第一の整数t1は、第一の乗算入力整数リストの第一の整数r1に第二の乗算入力整数リストの第一の整数s1を加えたものであってもよく、第一の中間乗算整数リストの第二の整数t2は、第一の乗算入力整数リストの第一の整数r1に第二の乗算入力整数リストの第二の整数s2を加えたものであってもよい：t1＝r1＋s1、t2＝r1＋s2；第二の中間乗算整数リストの第一の整数u1は、第一の乗算入力整数リストの第二の整数r2に第二の乗算入力整数リストの第二の整数s2を加えたものであってもよく、第二の中間乗算整数リストの第二の整数u2は、第一の乗算入力整数リストの第二の整数r2に第二の乗算入力整数リストの第一の整数s1を加えたものであってもよい：u1＝r2＋s2、u2＝r2＋s1。
【００７７】
ある実施形態では、たとえばたった今開示した例では、算術は整数リストに対して実行され、環要素は何らかの自然な表現での環要素として計算される必要はない。ここで変形のいくつかを論じる。変形の多くは独立である。たとえば、変形エンコードが加算を実行するための変形と組み合わされてもよい。
【００７８】
たとえばua1-b1に対応する整数リストにおいて計算が実行されるときの難読化された算術を通じて、値はuの位数を法として約されてもよい。たとえばuの位数が30であれば、すべての計算はmod  30で実行されてもよい。
【００７９】
増分値。
増分値は1である必要はない。異なる増分値を使うには少なくとも二つの仕方がある。第一に、式c＝ua1−ua2＋ub1＝(ua1-b1−ua2-b1＋1)ub1は、c＝ua1−ua2＋ub1＝(ua1-b1+t−ua2-b1+t＋ut)ub1-tに修正されてもよい。これは、値utを加える増分テーブルが構築されうることを意味する。この増分テーブルは、整数tが加えられるほかは同じ整数リストに適用される。増分テーブルの第一の適用後、b1の代わりに数b1−tが加えられる。
【００８０】
増分値を変更するもう一つの仕方は、環におけるgの反復加算がpを与えるようRの二つの元gおよびpを取るというものである。たとえば、h・g＝g＋…＋g＝pとなる整数hがある。増分値p、たとえばp＝1またはp＝utをもつ増分テーブルTpがあるとする。gを増分値として増分テーブルTgが構築されうる。直接Tpを適用するのと同じ効果を得るために、テーブルTgがh回適用されてもよい。異なる増分値をもつ異なる増分テーブルを使うことは、たとえば難読化を高めるために、単一の実施形態において組み合わされてもよい。この構築は、後続の加算計算を変えることなく複数の増分値が組み合わされうるという利点をもつ。
【００８１】
増分テーブルの構築も変更されてもよい。たとえば、中間加算環要素についての式に戻るが、c＝ua1−ua2＋ub1＝(ua1-b1−ua2-b1＋1)ub1という因子分解の代わりに、c＝ua1−ua2＋ub1＝(ua1-a2＋ub1-a2−1)ua2ということが観察される。この公式を使って、増分値−1について増分テーブルが構築されることができる。この型の増分値は環要素ua1-a2＋ub1-a2に適用される。この環要素は上記の例示的エンコードをもたない。にもかかわらず、この環要素は整数リスト、たとえば(a1−a2,b1−a2)として表現されることができる。よって、この増分テーブルは整数リストを入力として取り、整数リストを出力として生じる。しかしながら、先の例とは異なり、入力整数リストは出力エンコードとは異なるエンコードをもつ。さらに、加算ユニットへの入力において使われるエンコードはギャップをもたない、すなわち任意の環要素がこのエンコードにおいて表現されうることがずっと好ましいものの、この増分テーブルのこの代替的な入力エンコードがギャップをもたない必要性はない。テーブル入力として表現される必要のあるすべての要素は、構築によって表現できる。
【００８２】
増分テーブルをたとえば整数リスト(a1−a2,b1−a2)として表現されている環要素ua1-a2＋ub1-a2に適用したのち、整数a2が増分テーブルの出力の両方の要素に加算される。結果は、上記で定義した中間値cである。第二のテーブル適用を実行するために、否定にし、この代替的な増分テーブルを使ってub2を加算し、再び否定にするという上記と同じ構築が使われてもよい。上記で示される構築を使って、増分値は−1から他の値に変えられてもよい。
【００８３】
増分テーブルを環要素ua1-a2＋ub1-a2に適用することは、著しい利点をもつ。式は対称的であり、よって整数リスト表現を入力値として使うとT(a1−a2,b1−a2)＝T(b1−a2,a1−a2)となる。このことは、増分テーブルを圧縮された形で記憶することを許容する。テーブルの約半分が記憶されればよいのである。たとえば、T(x,y)を記憶するのはx≦yの場合のみとすることができる。この方法のわずかな潜在的な不都合は、中間整数リストが異なるエンコードを使うということである。
【００８４】
さらなる変形として、増分テーブルはua2-a1＋ub1-a1に適用されてもよい。
【００８５】
上記の例示的エンコードについて示した原理はいくつかの代替的なエンコードに適用されうる。第一の代替的なエンコードは、エンコードa＝ua1＋ua2を使って環要素aを整数リスト(a1,a2)としてエンコードするというものである。任意の環要素がこの仕方でエンコードされうるような基本環要素uをもつ環は、正の難読化された算術を許容すると言われる。上記の例示的エンコードは、負の難読化された算術と称される。基本環要素uをもつ正の難読化された算術を許容する任意の環について、um＝−1となるような整数mが存在することが数学的に証明されうる。さらに、負の難読化された算術を許容する環は、そのような値mが存在する場合にかつその場合にのみ正の難読化された算術を許容する。正の難読化された算術を許容する任意の環は負の難読化された算術も許容するが、逆は真ではない。
【００８６】
正の難読化された算術は、上記で概説した負の難読化された算術についてとほぼ同じ線に沿って行なわれる。手短かには、整数リストの符号の変化が、整数リスト中のすべての整数に値mを加えることによって行なわれてもよい。加算入力a＝ua1＋ua2およびb＝ub1＋ub2を与えられると、加算は、中間的なc＝ua1＋ua2＋ub1を計算することによって、たとえば(ua1-b1＋ua2-b1＋1)ub1を通じて、実行されてもよい。増分テーブルは、増分値1をもってua1-b1＋ua2-b1に適用される。正の還元が二度、ub1およびub2の両方について適用されてもよい。負の還元は必要ない。これは加算を単純化する。増分テーブルの構築は、上記のように、uの異なる冪乗を使うことによって変えられてもよい。増分値は上記のように変えられてもよい。正の難読化された算術は、増分テーブルが常に対称的であり、圧縮された形で記憶されうるという利点をもつ。正の難読化の難点は、この型のエンコードを許容する環がより少ないということである。
【００８７】
これまでに与えたエンコードは任意的に、何らかのvについての一定の環要素w＝uvを乗算されてもよい。こうして、整数リスト(a1,a2)は環要素a＝w(ua1−ua2)を表現してもよい。否定にするステップは変更ない。正の還元ステップはc＝wua1−wua2＋wub1＝(wua1-b1−wua2-b1＋w)ub1となる。増分テーブルは増分値としてwを使ってもよく、同じエンコード型をもつwua1-b1−wua2-b1に適用される。乗算は、整数リスト(r1,r2)および(s1,s2)として表現されたr＝wur1−wur2およびs＝wus1−wus2を、r・s＝(wur1−wur2)(wus1−wus2)＝(wur1+s1+v−wur1+s2+v)＋(wur2+s2+v−wur2+s1+v)＝t＋uを使って乗算しうる。
【００８８】
さらなる代替的なエンコードはa＝ua1(ua2−u-a2)によって、または定数1/2をかけてua1（(ua2−u-a2)/2）によって与えられる。奇数の位数をもつ基本環要素uをもつ負の難読化された算術を許容する環について、任意の環要素xがua1（(ua2−u-a2)/2）と書けることを証明できる。これはエンコードを、たとえば整数リストから環要素へのマップを変更する。環が負の難読化をもつ場合も、基本環要素が奇数の位数をもつ限り、この表現ができる。
【００８９】
加算および乗算ステップは、種々のエンコードについて対応して適応されることができる。たとえば、エンコードされた形の数a＝ua1(ua2−u-a2)を与えられたとき、a＝ua'1−ua'2となるようなa'1およびa'2をa1およびa2を使って計算してもよい。これはたとえば、uの位数を法とするa1＋a2およびuの位数を法とするa1−a2を計算することによる。これらの整数を使って、上記の加算および乗算が使用されうる。
【００９０】
双曲表現を得るためにやったことは、任意の種類の線形変換に一般化できる。変換が可逆であれば、新たな表現はもとの表現と等価である。
【００９１】
表現a＝ua1−ua2および行列形式で書かれた関係
【００９２】
【数７】
0006621813.tif 000008
があるとする。
【００９３】
変換が環Zkにおいて単位元である行列式mp−noをもつ場合には、a3およびa4での表現は他方と等価である。kは環Rにおけるuの位数である。これはgcd(mp−no,k)＝1である場合にかつその場合にのみ成り立つ。双曲表現は例であり（1/2の乗算を含め）、kが奇数であることを要求する。その場合には変換の行列式が2（または−2）になるからである。
【００９４】
上記方法を別の例を用いて説明する。環Z79を考え、u＝8とする。この元は位数k＝13をもち、Z79におけるすべての元は、何らかの指数について差ua1−ua2として書けることがわかっている。変換
【００９５】
【数８】
0006621813.tif 000009
を考える。行列式は5  mod  13であり、よって行列は逆をもつ。逆行列は
【００９６】
【数９】
0006621813.tif 000010
である。
【００９７】
Z79におけるすべてのxについて、x＝8α−8βとなるようなαおよびβをみつけられることがわかっている。だが、この変換を使うと、x＝810γ+8δ−86γ+4δとなるような値γおよびδをみつけることができることをただちに演繹できる。
【００９８】
このことは、大きなクラスの諸表現が等価であることを示している。線形変換は、二つの加法的定数r,sを含めて
【００９９】
【数１０】
0006621813.tif 000011
とすればアフィン変換に拡張されうる。
【０１００】
この変換は、線形変換Mが可逆であれば、可逆である。
【０１０１】
整数リストにおける整数の数。
これまで論じた例では、整数リストにおける要素の数は常に2であった。この数には利点がある。すなわち、計算ステップ数を削減する。他方、整数リスト中により多くの要素を許容することは、難読化を許容する環の数を拡張する。下記の例は、リスト当たり三つの整数を考えるが、より多数が可能であり、同様に機能する。
【０１０２】
それぞれ要素ua1＋ua2＋ua3およびub1＋ub2＋ub3をエンコードしている第一の整数リスト(a1,a2,a3)および第二の整数リスト(b1,b2,b3)を考える。否定にすることは、リスト中の整数に定数mを加算することによってできる。加算は、第二の整数リストにおける各整数についての、この場合三回の増分テーブルの適用によってできる。第一の中間加算整数リストはua1＋ua2＋ua3＋ub3＝(ua1-b3＋ua2-b3＋ua3-b3＋1)ub3から計算されうる。この場合、増分値は1であり、増分テーブルはua1-b3＋ua2-b3＋ua3-b3に適用される。乗算するには、第二の整数リスト中と同数の中間乗算整数リスト、たとえば(a1＋b1,a2＋b1,a3＋b1)、(a1＋b2,a2＋b2,a3＋b2)、(a1＋b3,a2＋b3,a3＋b3)が作られる。
【０１０３】
複数の異なる基本環要素。
us＝vおよびvt＝uとなるような指数をもつ二つの基本元uおよびvを考える。整数リスト(a1,a2)は環要素a＝ua1−va2をエンコードし、(b1,b2)についても同様。否定は、(a1,a2)を(sa2,ta1)にマッピングすることによって得られる。正の還元ステップua1−va2＋ub1＝(ua1-b1−va2-tb1＋1)ub1。増分値は1であり、テーブルは整数リスト(a1−b1,a2−tb1)に適用される。負の還元は否定を使って正の還元に帰着されうる。乗算は加算に帰着されうる。
【０１０４】
下記では、負および／または正の難読化を許容する環についての例が与えられる。
【０１０５】
環Rは法nについての整数環Znであってもよい。
【０１０６】
たとえば、nは13で、基本環要素u＝4であってもよい。この要素は位数6をもつ。下記では、すべての環要素0〜6が上記の例示的エンコードを使って整数リストとしてエンコードされる。ここで、すべての要素が複数のエンコードをもつことを注意しておく。挙げられている第一のエンコードについて、整数リストを与えられたときにどのように対応する環要素が見出されうるかを例証するマッピングの例を与えた。環要素7〜12は、環要素1〜6を否定にすることによって見出されうる。
【０１０７】
【表１】
0006621813.tif 000012
この例は、この環では43＝−1なので、正の難読化も許容する。
【０１０８】
負の難読化を許容するnおよびuについての他の値は：n＝151,u＝2；u＝87,u＝20;n＝79,u＝8などである。
【０１０９】
本発明者らは、負および／または正のエンコードを許容する環の多数の例を発見した。本稿に記載された与えられた負および／または正のエンコードから、多くの変形が導出可能であることを注意しておく。
【０１１０】
環Rは、多項式fおよび法nについての多項式環Zn[x]/f(x)であってもよい。多項式は既約である必要はない。fが既約でなければ、体ではない可換環が得られる。任意の可換な多項式環Rが難読化を許容することがわかる。
【０１１１】
たとえば、いくつかの体が与えられる。
【０１１２】
体F(2^6)
この体はF2[x]/(x^6+x^4+x^3+x+1)と同型である。基本u=x^3の位数は21である。
【０１１３】
体F(2^8)
この体はF2[x]/(x^8+x^4+x^3+x^2+1)と同型である。
基本u=x^3の位数は85である。
基本u=x+1の位数は51である。
【０１１４】
体F(2^10)
この体はF2[x]/(x^10+x^6+x^5+x^3+x^2+x+1)と同型である。
基本u=x^3の位数は341である。
基本u=x^7+x^6+x^4+x^3+x^2+xの位数は93である。
【０１１５】
体F(2^12)
この体はF2[x]/(x^12+x^7+x^6+x^5+x^3+x+1)と同型である。
基本u=x^3の位数は1365である。
基本u=x^5の位数は819である。
基本u=x^7の位数は585である。
基本u=x^9の位数は455である。
基本u=x^8+x^7+x^6+x^4+x^2+xの位数は315である。
基本u=x^10+x^9+x^8+x^6+x^4+x^3の位数は273である。
基本u=x^11+x^10+x^7+x^5+x^3+x^2+x+1の位数は195である。
【０１１６】
図４は、可換環（たとえばZn；Zn[x]/f(x)）において難読化された算術を実行するための計算方法３００の実施形態の例を概略的に示す。環は有限個の環要素をもつ。環要素に対して環加算および環乗算が定義されている。本計算方法は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用する。整数リストは少なくとも二つ整数を有する。本計算方法は、
・増分環要素（1；ut）について定義された増分テーブル（T）を記憶する段階であって、前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなるよう（l＝k＋1）入力環要素（k＝uk1−uk2）を出力環要素（l＝ul1−ul2）をエンコードする出力整数リストにマッピングする（T((k1,k2))＝(l1,l2)）、段階と；
・環加算する段階であって、前記環加算は
・第一の加算入力環要素をエンコードする第一の加算入力整数リスト（(a1,a2)）および第二の加算入力環要素をエンコードする第二の加算入力整数リスト（(b1,b2)）を受領３１０し、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定３２０することを含み、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、段階と；
・環乗算する段階であって、前記環乗算は
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リスト（(r1,r2)）および第二の乗算入力環要素をエンコードする第二の乗算入力整数リスト（(s1,s2)）を受領３３０し、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定３４０することを含み、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、段階とを含む。
【０１１７】
図５は、装置１００または方法３００などにおいて使用されうる加算方法４００の実施形態の例を概略的に示している。この例は、上記の例示的エンコードを使う。本方法は、他のエンコードに適応されてもよい。本稿に記載されるすべての変形が適用されうる。この例は増分値1をもち、増分テーブルは因子ub1をくくり出すことによって構築される。
【０１１８】
方法４００は、加算オペランドを受領すること４１０を含む。これは、第一の加算入力整数リスト、たとえば(a1,a2)を受領４１０し、第二の加算入力整数リスト、たとえば(b1,b2)を受領４２０することを含んでいてもよい。
【０１１９】
方法４００はさらに、中間加算整数リスト、たとえば(c1,c2)を決定４２０することを含む。たとえば、これは、第一および第二の加算入力整数リストから決定された環要素に増分テーブルを適用することを含んでいてもよい。特に、増分テーブルは整数リストに適用されてもよい。該整数中の要素は入力整数リスト中の要素から導出される。
【０１２０】
たとえば、決定４２０は、(a1−b1,a2−b1)に増分テーブルを適用４２２してたとえば(d1,d2)を得て；第二の加算入力整数リストから決定された整数b1を第一の適用から帰結する整数リスト中の整数に加算４２４すること、たとえば(c1,c2)＝(d1＋b1,d2＋b1)を含んでいてもよい。
【０１２１】
方法４００はさらに、中間加算整数リストおよび第二の加算入力整数リストから決定された環要素への増分テーブルの第二の適用を通じて加算出力整数リストを決定４３０することを含む。より長い整数リストについては、これは追加的な増分テーブル適用を含んでもよい。たとえば、これは中間加算整数リストを否定すること４３１、たとえば(c2,c1)に並べ替えることを含んでいてもよい。増分テーブルの適用４３２および加算４３４は、加算入力整数リスト(a1,a2)が中間整数リスト(c2,c1)によって置き換わり、b1がb2によって置き換わっているほかは、適用４２２および加算４２４と同じである。最後に、４３４の結果が否定にされて４５３、難読化加算の結果が得られる。
【０１２２】
今のように負の難読化の代わりに正の難読化が使われる場合には、否定４３１、４３５は省略されてもよい。
【０１２３】
図６は、装置１００または方法３００などにおいて使用されうる乗算方法５００の実施形態の例を概略的に示している。この例は、方法４００と同じエンコードおよび増分テーブルを使う。
【０１２４】
方法５００は、乗算オペランドを受領すること５１０を含む。これは、第一の乗算入力整数リスト、たとえば(r1,r2)を受領５１０し、第二の乗算入力整数リスト、たとえば(s1,s2)を受領５１４することを含んでいてもよい。
【０１２５】
方法５００はさらに、第一および第二の中間乗算整数リストを決定５２０することを含む。たとえば、５２０は、第一の中間乗算整数リストを決定し５２２、第二の中間乗算整数リストを決定する５２４ことを含んでいてもよい。これらはたとえば、それぞれ(s1＋r1,s1＋r2)および(s2＋r2,s2＋r1)として選ばれてもよいが、他の選択肢もある。乗算はこれらの数を加算方法４００において加算することによって続く。
【０１２６】
テーブルは適用４２２および適用４３２において使われるだけであり、方法４００および５００の他のどこでも使われていないことを注意しておく。加算も乗算も同じテーブルを使い、いずれもテーブルを同じ回数（二回）使う。他の演算は、たとえば基本環要素の位数を法とした、整数リスト中の整数に対する小さな算術演算を含む。
【０１２７】
上記の諸方法を実行するための多くの異なる仕方が可能である。このことは当業者には明白であろう。たとえば、段階の順序は変えられてもよく、いくつかの段階は並列に実行されてもよい。さらに、段階と段階の間に、他の方法段階が挿入されてもよい。挿入される段階は、本稿に記載されるような方法の洗練を表わしていてもよく、あるいは本方法に無関係であってもよい。さらに、所与の段階は次の段階が開始される前に完全に完了していないこともありうる。
【０１２８】
実施形態に基づく方法は、プロセッサ・システムに方法３００、４００および５００のうちの任意のものを実行させるための命令を含むソフトウェアを使って実行されてもよい。ソフトウェアは、システムの特定のサブエンティティによって行なわれる段階のみを含んでいてもよい。ソフトウェアは、ハードディスク、フロッピー、メモリなどといった好適な記憶媒体に記憶されていてもよい。ソフトウェアは、ワイヤに沿ったあるいは無線の信号として、あるいはデータ・ネットワーク、たとえばインターネットを使って送られてもよい。ソフトウェアはダウンロードおよび／またはサーバー上でのリモート使用のために利用可能にされてもよい。方法は、本方法を実行するようプログラム可能な論理、たとえばフィールドプログラマブルゲートアレイ（FPGA）を構成するよう構成されたビットストリームを使って実行されてもよい。
【０１２９】
実施形態が、実施形態を実施するために適応されたコンピュータ・プログラム、特に搬送波上または搬送波中のコンピュータ・プログラムに拡張されることは理解されるであろう。プログラムは、ソースコード、オブジェクトコード、部分的にコンパイルされた形のようなコード中間ソースおよびオブジェクトコードの形で、あるいは実施形態に基づく方法の実装において使うために好適な他の任意の形でありうる。コンピュータ・プログラム・プロダクトに関係する実施形態は、記載される方法のうち少なくとも一つの方法の処理段階のそれぞれに対応するコンピュータ実行可能命令を含む。これらの命令は、サブルーチンに分割され、および／または静的または動的にリンクされうる一つまたは複数のファイルにおいて記憶されてもよい。コンピュータ・プログラム・プロダクトに関係する別の実施形態は、記載されるシステムおよび／またはプロダクトのうち少なくとも一方の各手段に対応するコンピュータ実行可能命令を含む。
【０１３０】
図７のａは、コンピュータ・プログラム１０２０を有する書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示している。コンピュータ・プログラム１０２０は、プロセッサ・システムに、実施形態に基づく難読化算術を実行するための計算方法を実行させるための命令を含む。書き込み可能部分は、複数回の書き込みのために構成されていてもよく、あるいは一度だけの書き込みのために構成されていてもよい。コンピュータ・プログラム１０２０はコンピュータ可読媒体１０００上で、物理的なマークとして、あるいはコンピュータ可読媒体１０００の磁化によって具現されてもよい。しかしながら、他の任意の好適な実施形態も考えられる。さらに、コンピュータ可読媒体１０００はここでは光ディスクとして示されているが、コンピュータ可読媒体１０００はハードディスク、半導体メモリ、フラッシュメモリなどといったいかなる好適なコンピュータ可読媒体であってもよく、記録不可能でも記録可能でもよいことは理解されるであろう。コンピュータ・プログラム１０２０は、難読化算術を実行するための前記計算方法をプロセッサ・システムに実行させるための命令を含む。
【０１３１】
コンピュータ可読媒体、たとえばコンピュータ可読媒体１０００は増分テーブルおよび／またはデコード・テーブルおよび／またはエンコード・テーブルを含んでいてもよい。
【０１３２】
図７のｂは、実施形態に基づく処理システム１１００の概略的な表現を示している。プロセッサ・システムは、一つまたは複数の集積回路１１１０を有する。一つまたは複数の集積回路１１１０のアーキテクチャーは図７のｂに概略的に示されている。回路１１１０は、実施形態に基づく方法を実行するためおよび／またはそのモジュールもしくはユニットを実装するためにコンピュータ・プログラム・コンポーネントを走らせるための処理ユニット１１２０、たとえばCPUを有する。回路１１１０は、プログラミング・コード、データなどを記憶するためのメモリ１１２２を有する。メモリ１１２２の一部は読み出し専用であってもよい。回路１１１０は通信要素１１２６、たとえばアンテナ、コネクタまたはその両方などを有していてもよい。回路１１１０は、本方法において定義される処理の一部または全部を実行するための専用の集積回路１１２４を有していてもよい。プロセッサ１１２０、メモリ１１２２、専用IC  １１２４および通信要素１１２６は相互接続１１３０、たとえばバスを介して互いに接続されてもよい。プロセッサ・システム１１１０は、それぞれアンテナおよび／またはコネクタを使って接触式および／または非接触式通信のために構成されていてもよい。
【０１３３】
上述した実施形態は、本発明を限定するのではなく例解するものであり、当業者は多くの代替実施形態を設計できるであろうことを注意しておくべきである。
【０１３４】
請求項では、括弧内に参照符号があったとしてもその請求項を限定するものと解釈してはならない。動詞「有する／含む」およびその活用形の使用は、請求項において述べられているもの以外の要素やステップの存在を排除しない。要素の単数形の表現はそのような要素の複数の存在を排除しない。本発明は、いくつかの相異なる要素を有するハードウェアによって、および好適にプログラムされたコンピュータによって実装されうる。いくつかの手段を列挙する装置請求項では、これらの手段のいくつかが同一のハードウェア項目によって具現されてもよい。ある種の施策が互いに異なる従属請求項において記載されているというだけの事実が、これらの施策の組み合わせが有利に使用できないことを示すものではない。
【０１３５】
請求項では、括弧内の参照符号は実施形態の図面における参照符号または実施形態の公式を指し、それにより請求項の理解しやすさを増す。これらの参照は網羅的ではなく、請求項を限定するものと解釈してはならない。
いくつかの態様を記載しておく。
〔態様１〕
可換環（Zn；Zn[x]/f(x)）において算術を実行するための電子計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算装置は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リスト（(a1,a2)）は、環要素（a）を、該環要素が一つまたは複数の基本環要素（u；u,v）の冪乗の線形結合に等しくなる（a＝ua1−ua2；a＝ua1−va2）ようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算装置は、
・増分環要素（1；ut）について定義された増分テーブル（T）を記憶するよう構成された記憶部を有しており、
・前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなる（l＝k＋1）よう入力環要素（k＝uk1−uk2）を出力環要素（l＝ul1−ul2）をエンコードする出力整数リストにマッピングし（T((k1,k2))＝(l1,l2)）、
当該計算装置はさらに、環加算ユニットを有しており、前記環加算ユニットは、
・第一の加算入力環要素をエンコードする第一の加算入力整数リスト（(a1,a2)）および第二の加算入力環要素をエンコードする第二の加算入力整数リスト（(b1,b2)）を受領する段階であって、前記増分環要素は前記第一および第二の加算入力環要素から独立である、段階と、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定する段階であって、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、段階とを実行するよう構成されている、
計算装置。
〔態様２〕
環乗算ユニットをさらに有しており、前記環乗算ユニットは、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リスト（(r1,r2)）および第二の乗算入力環要素をエンコードする第二の乗算入力整数リスト（(s1,s2)）を受領する段階と、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定する段階であって、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、段階とを実行するよう構成されている、
態様１記載の計算装置。
〔態様３〕
前記整数リスト（(a1,a2)）が環要素（a）をエンコードする仕方は、
・前記環要素が、基本元を前記整数リストの第一の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを引いたもの（a＝ua1−ua2）に任意的に定数を乗算したもの（a＝t(ua1−ua2)）に等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたものに、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを足したもの（a＝ua1＋ua2）に任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたもの、かける、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数のマイナスによって決定される冪乗にしたものを引いたもの（a＝ua1(ua2−u-a2)）に任意的に定数を乗算したもの（a＝ua1(ua2−u-a2)/2）に等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数および第二の整数の第一の線形結合である冪乗にしたもの、足すまたは引く、前記基本元を前記第一の整数および前記第二の整数の第二の線形結合である冪乗にしたもの（行列Mを与えられて
【数１１】
0006621813.tif 000013
となるようなx＝ub1＋ub2またはx＝ub1−ub2）に任意的に定数を乗算したものに等しくなるようにするものである、
態様１または２記載の計算装置。
〔態様４〕
前記加算出力整数リストを決定することが、
・一つまたは複数の基本元の冪乗の線形結合である環要素（ua1-b1−ua2-b1）への前記増分テーブルの第一の適用によって、中間加算環要素をエンコードする中間加算整数リスト（(c1,c2)）を決定する段階であって、前記冪乗は前記第一および第二の加算入力整数リストから決定される、段階（uc1−uc2＝ua1−ua2＋ub1）と、
・前記加算出力整数リストを決定する段階であって、前記中間加算整数リストから決定されるおよび前記第二の加算入力整数リストから決定される環要素への前記増分テーブルの第二の適用を含む、段階とを含む、
態様１または３記載の計算装置。
〔態様５〕
前記中間加算整数リスト（(c1,c2)）を決定することがさらに、前記第一および第二の加算入力整数リストから決定された整数を、第一の適用から帰結する整数リスト中の整数に加算することを含む、態様４記載の計算装置。
〔態様６〕
・前記増分テーブルは、前記一つまたは複数の基本環要素（u）を前記第一の整数リストの第一の整数（a1）から前記第二の整数リストの第一の整数（b1）を引いたもの乗したもの、足すまたは引く、ある基本環要素（u）を前記第一の整数リストの第二の整数（a2）から前記第二の整数リストの第一の整数（b1）を引いたもの乗したもの、によって形成される環要素（ua1-b1−ua2-b1；ua1-b1＋ua2-b1）に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素（u）を前記第一の整数リストの前記第一の整数（a1）から前記第一の整数リストの第二の整数（a2）を引いたもの乗したもの、足すまたは引く、ある基本環要素（u）を前記第二の整数リストの第一の整数（b1）から前記第一の整数リストの前記第二の整数（a2）を引いたもの乗したもの、によって形成される環要素（ua1-a2＋ub1-a2；ua1-a2＋ub1-a2）に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素（u）を前記第一の整数リストの第二の整数（a2）から前記第一の整数リストの第一の整数（a1）を引いたもの乗したもの、足すまたは引く、ある基本環要素（u）を前記第二の整数リストの第一の整数（b1）から前記第一の整数リストの前記第一の整数（a1）を引いたもの乗したもの、によって形成される環要素（ub1-a1−ua2-a1；ua2-a1＋ub1-a1）に適用される、
態様４または５記載の計算装置。
〔態様７〕
・前記増分テーブルの前記第二の適用の前に、前記中間加算整数リストによって表わされる前記中間加算環要素が否定にされる、
態様４ないし６のうちいずれか一項記載の計算装置。
〔態様８〕
・整数リストによって表わされる環要素が、該整数リストを並べ替えることによって否定にされる、および／または
・整数リストによって表わされる環要素が、該整数リストの各整数に定数を加えるることによって否定にされる、および／または
・整数リスト（(a1,a2)）によって表わされる環要素が、該整数リストを並べ替え、該整数リストの一つまたは複数の整数に定数を乗算する（(sa2,ta1)）ことによって否定にされる、
態様１ないし７のうちいずれか一項記載の計算装置。
〔態様９〕
前記増分テーブルが、前記入力環要素（k＝uk1−uk2）を表わす入力整数リスト（(k1,k2)）を入力として取る、態様１ないし８のうちいずれか一項記載の計算装置。
〔態様１０〕
乗算出力整数リストを決定することが、
・前記第一および第二の乗算入力整数リストから、それぞれ第一および第二の中間乗算還要素をエンコードする第一の中間乗算整数リスト（(t1,t2)）および第二の中間乗算整数リスト（(u1,u2)）を決定し、
・前記第一および第二の中間乗算整数リストを前記環加算ユニットを通じて加算することを含む、
態様２記載の計算装置。
〔態様１１〕
・前記第一の中間乗算整数リストの第一の整数（t1）は、前記第一の乗算入力整数リストの第一の整数（r1）、足す、前記第二の乗算入力整数リストの第一の整数（s1）であり、
・前記第一の中間乗算整数リストの第二の整数（t2）は、前記第一の乗算入力整数リストの第一の整数（r1）、足す、前記第二の乗算入力整数リストの第二の整数（s2）であり（t1＝r1＋s1、t2＝r1＋s2）、
・前記第二の中間乗算整数リストの第一の整数（u1）は、前記第一の乗算入力整数リストの第二の整数（r2）、足す、前記第二の乗算入力整数リストの第二の整数（s2）であり、
・前記第二の中間乗算整数リストの第二の整数（u2）は、前記第一の乗算入力整数リストの第二の整数（r2）、足す、前記第二の乗算入力整数リストの第一の整数（s1）である（u1＝r2＋s2、u2＝r2＋s1）、
態様１０記載の計算装置。
〔態様１２〕
・前記可換環が、ある整数を法とする整数によって形成される環（Zn）である、または
・前記可換環が、ある整数多項式を法とする整数多項式によって形成される環（Zn[x]/f(x)）である、
態様１ないし１１のうちいずれか一項記載の計算装置。
〔態様１３〕
態様１記載の計算装置と一緒に使うための、可換環（Zn；Zn[x]/f(x)）の環要素を整数リストとしてエンコードする環エンコード装置であって、当該環エンコード装置は、
・一つまたは複数の基本環要素（u）について定義されたエンコード・テーブルを記憶するよう構成された記憶部を有しており、前記エンコード・テーブルは、環要素（x）を、環要素が前記一つまたは複数の基本環要素の冪乗の線形結合に等しい（x＝ua−ub）ように整数リスト（(a,b)）にマッピングするものであり、前記冪乗は前記整数リストによって決定される指数をもつ、
環エンコード装置。
〔態様１４〕
態様１記載の計算装置と一緒に使うための、整数リスト（(a,b)）を可換環（Zn；Zn[x]/f(x)）の環要素（x）にデコードする環デコード装置であって、当該環デコード装置は、一つまたは複数の基本環要素（u）について、前記環要素（x）を、前記環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しい（x＝ua−ub）ように決定するよう構成されており、前記冪乗は前記整数リストによって決定される指数をもつ、
環デコード装置。
〔態様１５〕
可換環（Zn；Zn[x]/f(x)）において算術を実行するための計算装置において使うための増分テーブルを計算するテーブル計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、前記計算装置は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用し、前記整数リストは少なくとも二つ整数を有し、当該テーブル計算装置は、
・増分テーブルを構築するよう構成されたテーブル生成ユニットを有し、前記テーブル生成ユニットは、
・入力環要素を反復的に選択し、
・増分環要素が前記入力環要素に環加算されたものに等しい出力環要素を決定し、
・前記出力環要素についてエンコードする出力整数リストを決定し、
・前記入力環要素を前記出力整数リストにマッピングするエントリーを増分テーブルに追加するよう構成されている、
テーブル計算装置。
〔態様１６〕
可換環（Zn；Zn[x]/f(x)）において算術を実行するための電子的な計算方法であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算方法は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リスト（(a1,a2)）は、環要素（a）を、該環要素が一つまたは複数の基本環要素（u；u,v）の冪乗の線形結合に等しくなる（a＝ua1−ua2；a＝ua1−va2）ようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算方法は、
・増分環要素（1；ut）について定義された増分テーブル（T）を記憶する段階であって、前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなる（l＝k＋1）よう入力環要素（k＝uk1−uk2）を出力環要素（l＝ul1−ul2）をエンコードする出力整数リストにマッピングする（T((k1,k2))＝(l1,l2)）、段階と、
・環加算する段階であって、前記環加算は、
・第一の加算入力環要素をエンコードする第一の加算入力整数リスト（(a1,a2)）および第二の加算入力環要素をエンコードする第二の加算入力整数リスト（(b1,b2)）を受領し、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定することを含み、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、
電子的な計算方法。
〔態様１７〕
環乗算する段階を含み、前記環乗算は、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リスト（(r1,r2)）および第二の乗算入力環要素をエンコードする第二の乗算入力整数リスト（(s1,s2)）を受領し、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定することを含み、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、
態様１６記載の電子的な計算方法。
〔態様１８〕
プログラム可能な装置で実行されたときに態様１６または１７記載の方法を実行するよう構成されているコンピュータ・プログラム命令を有するコンピュータ・プログラム。
〔態様１９〕
・態様１８記載のコンピュータ・プログラム、および／または
・態様１記載の電子計算装置によって使用される前記増分テーブルを有する、
コンピュータ可読媒体。
【符号の説明】
【０１３６】
１００  計算装置
１１０  増分テーブルを記憶するよう構成された記憶部
１２０  環否定ユニット
１３０  環加算ユニット
１４０  環乗算ユニット
１５０  オペランド・ストア
１６０  デコード・ユニット
１７０  エンコード・ユニット
１７２  エンコード・テーブルを記憶するよう構成された記憶部
【図１ａ】
0006621813.tif 000014
【図１ｂ】
0006621813.tif 000015
【図１ｃ】
0006621813.tif 000016
【図２】
0006621813.tif 000017
【図３】
0006621813.tif 000018
【図４】
0006621813.tif 000019
【図５】
0006621813.tif 000020
【図６】
0006621813.tif 000021
【図７ａ】
0006621813.tif 000022
【図７ｂ】
0006621813.tif 000023