(57)【要約】  計算デバイス２００は、ｎ個の入力変数をｍ個の出力変数に写像するデータ関数Ｓを評価する。前記計算デバイスは、選択変数を入力として受け取る選択メカニズム２２０と、１つ又は複数の評価変数を受け取り、受け取られた評価変数について評価関数を評価する評価メカニズム２１０であって、評価関数が評価変数を入力として受け取る、評価メカニズム２１０とを備える。
2019504343.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の入力変数をｍ個の出力変数に写像するデータ関数を評価する計算デバイスであって、前記データ関数が選択関数及び評価関数を含む計算として前記計算デバイスにおいて構成され、前記入力変数が１つ又は複数の選択変数及び１つ又は複数の評価変数に区分され、前記選択変数（υ）の特定の値の組合せごとに、対応する選択関数（Ｑυ）及び評価関数（Ｐυ）が定義され、
前記計算デバイスが、
前記１つ又は複数の選択変数を受け取り、受け取られた前記選択変数について前記選択関数を評価する選択メカニズムであって、選択関数が前記選択変数を入力として受け取り、前記選択関数の出力が、前記選択関数において受け取られた前記選択変数が、前記選択関数に対応する前記特定の値の組合せに等しいか否かを示す、選択メカニズムと、
前記１つ又は複数の評価変数を受け取り、受け取られた前記評価変数について前記評価関数を評価する評価メカニズムであって、評価関数が前記評価変数を入力として受け取り、前記評価関数の出力が、前記評価変数と、前記評価関数に対応する前記選択変数の前記特定の値の組合せとの和集合を入力とする前記データ関数の出力を表す、評価メカニズムと、
前記選択メカニズム及び前記評価メカニズムの前記出力を、前記入力変数に対する前記データ関数の前記出力に結合する結合メカニズムであって、同一の特定の値の組合せに対応する選択関数（Ｑυ）及び評価関数（Ｐυ）の積の総和（ΣｖＱυＰυ）をとり、前記総和が前記選択変数（υ）の全ての値の組合せに対するものである、結合メカニズムと
を備える、計算デバイス。
【請求項２】
前記選択メカニズムが前記選択関数を実装する複数の選択ユニットを備え、且つ／又は前記評価メカニズムが前記評価関数を実装する複数の評価ユニットを備える、請求項１に記載の計算デバイス。
【請求項３】
前記選択変数が、複数の選択変数のグループにさらに区分され、選択関数が、前記複数の選択変数のグループの中のグループにそれぞれが対応する複数のサブ選択関数の積として前記計算デバイスにおいて構成され、サブ選択関数が、前記グループ内の前記選択変数を入力として受け取り、前記サブ選択関数の出力が、受け取られた前記選択変数が、前記選択関数に対応する前記グループ内の特定の値の組合せと等しいか否かを示す、請求項１又は２に記載の計算デバイス。
【請求項４】
前記入力変数及び／又は出力変数がビットである、請求項１乃至３のいずれか一項に記載の計算デバイス。
【請求項５】
ブロック暗号として構成され、前記データ関数が前記ブロック暗号のｓボックスである、請求項１乃至４のいずれか一項に記載の計算デバイス。
【請求項６】
前記ブロック暗号がＤＥＳ又はトリプルＤＥＳブロック暗号であり、前記ｓボックスがＤＥＳのｓボックスの１つである、請求項５に記載の計算デバイス。
【請求項７】
前記入力変数の数（ｎ）が前記出力変数の数（ｍ）よりも大きく、前記評価変数の数が前記出力変数の数に等しい、請求項１乃至６のいずれか一項に記載の計算デバイス。
【請求項８】
前記入力変数のうちの１つ又は複数が符号化される、請求項１乃至７のいずれか一項に記載の計算デバイス。
【請求項９】
符号化された前記入力変数が複数のシェアとして符号化され、詳細には、前記符号化された入力変数が、複数の符号化済みシェアとして符号化され、より詳細には、前記複数のシェアが複数のステートと共に符号化される、請求項８に記載の計算デバイス。
【請求項１０】
前記選択関数が選択多項式として実装され、且つ／又は前記評価関数が評価多項式として実装される、請求項１乃至９のいずれか一項に記載の計算デバイス。
【請求項１１】
前記選択関数が複数のデータ関数に使用される、請求項１乃至１０のいずれか一項に記載の計算デバイス。
【請求項１２】
前記選択メカニズム、評価メカニズム及び／又は前記結合メカニズムがテーブルネットワークとして実装される、請求項１乃至１１のいずれか一項に記載の計算デバイス。
【請求項１３】
ｎ個の入力変数をｍ個の出力変数に写像するデータ関数を評価する計算方法であって、前記データ関数が選択関数及び評価関数を含む計算として前記計算方法において構成され、前記入力変数が１つ又は複数の選択変数及び１つ又は複数の評価変数に区分され、前記選択変数（υ）の特定の値の組合せごとに、対応する選択関数（Ｑυ）及び評価関数（Ｐυ）が定義される計算方法において、
前記１つ又は複数の選択変数を受け取り、受け取られた前記選択変数について前記選択関数を評価する選択メカニズムのステップであって、選択関数が前記選択変数を入力として受け取り、前記選択関数の出力が、前記選択関数において受け取られた前記選択変数が、前記選択関数に対応する前記特定の値の組合せに等しいか否かを示す、選択メカニズムのステップと、
前記１つ又は複数の評価変数を受け取り、受け取られた前記評価変数について前記評価関数を評価する評価メカニズムのステップであって、評価関数が前記評価変数を入力として受け取り、前記評価関数の出力が、前記評価変数と、前記評価関数に対応する前記選択変数の前記特定の値の組合せとの和集合を入力とする前記データ関数の出力を表す、評価メカニズムのステップと、
前記選択メカニズムのステップ及び前記評価メカニズムのステップの前記出力を、前記入力変数に対する前記データ関数の前記出力に結合する結合メカニズムのステップであって、同一の特定の値の組合せに対応する選択関数（Ｑυ）及び評価関数（Ｐυ）の積の総和（ΣｖＱυＰυ）をとることを含み、前記総和が前記選択変数（υ）の全ての値の組合せに対するものである、結合メカニズムのステップと
を有する、計算方法。
【請求項１４】
コンピュータ上で実行された場合に、請求項１３に記載の計算方法を実施するコンピュータプログラム命令を含む、コンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算デバイス、計算方法、コンピュータプログラム、及びコンピュータ可読媒体に関する。
【背景技術】
【０００２】
ホワイトボックスモデルでは、ハッカーは、たとえば、スマートフォン又はＰＣなどのコンピューティングデバイス上で実行されるソフトウェアに対して完全な制御を取得することができる場合がある。ホワイトボックス暗号の目標は、そのようなハッカーからソフトウェア実装を保護することである。
【０００３】
ホワイトボックスモデルにおいて鍵を含む暗号方式が保護されなければならない場合、これは通常、セキュアソフトウェア及びその実行環境のアクセス及び完全な制御を有する攻撃者が、鍵に関するいかなる検知可能な情報も抽出できてはならないことを意味する。
【０００４】
攻撃者が情報内の鍵へのアクセスを取得しないようにする１つの手法は、機密アルゴリズムの一部又は全部をテーブルネットワークとして実装することである。テーブルは符号化済み変数に演算を行う。攻撃者は、符号化に関する知識がないので、テーブルがどのような演算を行うのかを決定することは困難である。テーブルアクセスによって演算を置き換えると、通常はコードサイズが増加する。また、テーブルをさらに保護するためのいくつかの対策は、コードサイズをさらに増加させるという効果を有する。
【０００５】
たとえば、攻撃者が実行中の実装にアクセス可能な場合に鍵に関する情報を取得する１つの可能な攻撃はいわゆる衝突攻撃であり、これは攻撃者が異なる入力についての異なる実行において鍵依存変数を測定するものである。攻撃者は衝突に関する統計、すなわち、異なるメッセージについての異なる実行において同一の値をとる変数を収集する。最終的に、攻撃者は鍵を抽出するのに十分な情報を収集することができる。相互情報量解析（ＭＩＡ：Ｍｕｔｕａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ａｎａｌｙｓｉｓ）はそのような攻撃の一例である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
衝突攻撃から保護するために、変数ｗをｎ個のシェア｛ｗｉ｝ｉによって表して、ｗの衝突が完全な集合｛ｗｉ｝ｉの衝突のみから検出され得るようにすることができる。後者はより低い確率を有するので、衝突攻撃はより困難になる。シェアの計算は、テーブルのサイズが再び大幅に増加するという効果を有する。
【課題を解決するための手段】
【０００７】
いくつかの入力変数をいくつかの出力変数に写像するデータ関数を評価する計算デバイスが提供される。データ関数は選択関数及び評価関数を含む計算として計算デバイスにおいて構成される。入力変数は１つ又は複数の選択変数及び１つ又は複数の評価変数に区分される。選択変数の特定の値の組合せごとに、対応する選択関数及び評価関数が定義される。
【０００８】
計算デバイスは、
１つ又は複数の選択変数を受け取り、受け取られた選択変数について選択関数を評価する選択メカニズムであって、選択関数が選択変数を入力として受け取り、選択関数の出力が、選択関数において受け取られた選択変数が、選択関数に対応する特定の値の組合せに等しいか否かを示す、選択メカニズムと、
１つ又は複数の評価変数を受け取り、受け取られた評価変数について評価関数を評価する評価メカニズムであって、評価関数が評価変数を入力として受け取り、評価関数の出力が、評価変数と、評価関数に対応する選択変数の特定の値の組合せとの和集合を入力とするデータ関数の出力を表す、評価メカニズムと、
選択メカニズム及び評価メカニズムの出力を、入力変数に対するデータ関数の出力に結合する結合メカニズムと
を備える。
【０００９】
評価関数及び選択関数の両方が、入力としてデータ関数よりも少ない入力を受け取る。結果として、評価関数及び選択関数を実装するためのコードサイズが削減される。これは、評価関数及び／又は選択関数がテーブル又はテーブルネットワークとして実装されるホワイトボックス実装において特に重要であり、その理由は、これがより小さいテーブルを必要とするためである。評価変数及び選択変数への区分の結果、回路サイズが増加するが、コードサイズは削減される。また、選択関数は、変数が複数の符号化済みシェアとして表される場合に使用されるような、多項式ベースの実装で実装するのが容易な、特に単純な関数である。選択関数は異なるデータ関数について同一であるので、複数のデータ関数に再利用され、これによりコードサイズがさらに削減される。
【００１０】
一実施形態では、選択変数が、複数の選択変数のグループにさらに区分され、選択関数が、複数の選択変数のグループの中のグループにそれぞれが対応する複数のサブ選択関数の積として計算デバイスにおいて構成され、サブ選択関数が、グループ内の選択変数を入力として受け取り、サブ選択関数の出力が、受け取られた選択変数が、選択関数に対応するグループ内の特定の値の組合せと等しいか否かを示す。
【００１１】
選択変数のさらなる細分化は、選択メカニズムを実装するためのコードサイズをさらに減少させる。
【００１２】
選択メカニズムによって、選択変数に基づいて正しい評価関数が選択される。評価メカニズムは、選択変数及び評価変数の異なる可能な値についてデータ関数の結果を評価する。評価関数は、入力として評価変数のみを必要とする。評価変数は、評価関数に対応する特定の選択変数値の組合せによって、評価関数において補われる。これにより評価関数の数は増加するが、そのような関数のサイズは減少する。
【００１３】
選択メカニズムは選択システムとして、たとえば、回路及び／又はプロセッサ上で実行される適切なソフトウェアの形態で実装される。評価メカニズムは評価システムとして、たとえば、回路及び／又はプロセッサ上で実行される適切なソフトウェアの形態で実装される。たとえば、前記ソフトウェアは、テーブルネットワークにおける複数のテーブル参照動作を含む。
【００１４】
一実施形態では、入力変数の１つ又は複数が符号化される。実際に、選択変数及び評価変数の全てが符号化されてもよい。符号化済み変数への演算は、同一の符号化について符号化されたテーブルによって行われる。
【００１５】
変数、特に選択変数及び評価変数を符号化する重要な手法は、変数を複数の符号化済みシェアとして符号化することである。演算を有限体の多項式として表現することによって、このように符号化された変数に対して演算が実行される。多項式は、加算及び乗算などの演算を表すテーブルを使用して評価される。このタイプの符号化の利点は、加算及び乗算用のテーブルが多項式評価を通じて再利用されることである。これにより、コードサイズがさらに削減される。
【００１６】
計算デバイスは電子デバイス、たとえば、携帯電話などのモバイル電子デバイスである。計算デバイスは、セットトップボックス、スマートカード、コンピュータなどである。
【００１７】
本明細書に記載の計算の方法は、広範囲の実用的なアプリケーションにおいて適用される。そのような実用的なアプリケーションは、暗号化アプリケーションを含む。たとえば、情報の署名、復号及び暗号化などは、暗号化操作の実施に使用される鍵を明かすことなくソフトウェアで行われる。たとえば、計算デバイスは、たとえば独自のアルゴリズムを使用する機密アプリケーションに使用される。攻撃者がソフトウェアをリバースエンジニアリングする難しさが高まる。
【００１８】
本発明による方法は、コンピュータ上でコンピュータ実施される方法として、若しくは専用ハードウェアで、又はその両方の組合せで実装される。本発明による方法の実行可能コードは、コンピュータプログラム製品に記憶される。コンピュータプログラム製品の例は、メモリデバイス、光記憶デバイス、集積回路、サーバ、オンラインソフトウェアなどを含む。好ましくは、コンピュータプログラム製品は、前記プログラム製品がコンピュータ上で実行された場合に本発明による方法を実施するためのコンピュータ可読媒体に記憶された非一時的プログラムコードを含む。
【００１９】
好ましい一実施形態では、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行された場合に本発明による方法の全てのステップを実施するように適合されるコンピュータプログラムコードを含む。好ましくは、コンピュータプログラムはコンピュータ可読媒体上に具現化される。
【００２０】
本発明の別の態様は、コンピュータプログラムをダウンロード可能にする方法を提供する。この態様はコンピュータプログラムが、たとえば、ＡｐｐｌｅのＡｐｐ  Ｓｔｏｒｅ、ＧｏｏｇｌｅのＰｌａｙ  Ｓｔｏｒｅ、又はＭｉｃｒｏｓｏｆｔのＷｉｎｄｏｗｓ  Ｓｔｏｒｅにアップロードされた場合、及びコンピュータプログラムが、そのようなストアからダウンロード可能である場合に使用される。
【００２１】
本発明のさらなる詳細、態様、及び実施形態が、単なる例として図面を参照して説明される。図中の要素は簡潔且つ明瞭にするように示されており、必ずしも縮尺通りに描かれていない。図中では、説明済みの要素に対応する要素は同一の参照符号を有し得る。
【図面の簡単な説明】
【００２２】
【図１】データ関数の一例を概略的に示す図である。
【図２ａ】計算デバイスの一実施形態の一例を概略的に示す図である。
【図２ｂ】評価メカニズムの一実施形態の一例を概略的に示す図である。
【図２ｃ】選択メカニズムの一実施形態の一例を概略的に示す図である。
【図２ｄ】選択メカニズムの一実施形態の一例を概略的に示す図である。
【図２ｅ】計算デバイスの一実施形態の一例を概略的に示す図である。
【図３】変数を符号化する一例を概略的に示す図である。
【図４ａ】テーブルネットワークの一実施形態の一例を概略的に示す図である。
【図４ｂ】テーブルネットワークの一実施形態の一例を概略的に示す図である。
【図５ａ】計算方法のフローチャートを概略的に示す図である。
【図５ｂ】計算方法のフローチャートを概略的に示す図である。
【図６ａ】ＤＥＳブロック暗号の一実施形態の一例を概略的に示す図である。
【図６ｂ】ＤＥＳラウンド関数の一実施形態の一例を概略的に示す図である。
【図７ａ】一実施形態によるコンピュータプログラムを含む書き込み可能部分を有するコンピュータ可読媒体を概略的に示す図である。
【図７ｂ】一実施形態によるプロセッサシステムの表現を概略的に示す図である。
【発明を実施するための形態】
【００２３】
本発明は多くの異なる形式の実施形態が可能であるが、図面に示され、本明細書で詳細に説明されるのは１つ又は複数の特定の実施形態であって、本開示が本発明の原理の例示と見なされるべきであり、本発明を図示及び説明される特定の実施形態に限定するものではないという了解の下でのものである。
【００２４】
以下では、理解のために、動作中の実施形態の要素が説明される。しかしながら、それぞれの要素が、それらによって実施されるように記載された機能を実施するように構成されることは明らかであろう。
【００２５】
さらに、本発明は実施形態に限定されず、本発明は上述の、又は相異なる従属請求項に記載された各々の新規の特徴又は特徴の組合せの中にある。
【００２６】
図６ａは、ＦＩＰＳ４６−３からコピーされたものであるが、特にＤＥＳブロック暗号を示し、一般にはブロック暗号を示す。ブロック暗号は、ブロック暗号ラウンドのシーケンスが作用するブロック暗号入力６１０を受信し、ＤＥＳの場合は１６ラウンドが存在し、トリプルＤＥＳでは４８である。第１のブロック暗号ラウンドはブロック暗号入力６１０に作用し、次のラウンドのそれぞれは前のラウンドの出力に作用する。ブロック暗号ラウンドでは、ラウンド関数ｆが前のラウンドの出力の一部に適用される。ブロック暗号入力は、ＤＥＳの場合、６４ビットのデータサイズを有する。各ブロック暗号ラウンドは、そのブロック暗号ラウンド入力を修正して、ブロック暗号ラウンド出力を生成する。全てのブロック暗号ラウンド入力及び出力は同一のデータサイズを有する。ＤＥＳはブロック暗号の最初及び最後に初期転置及び逆初期転置を有することに留意されたい。これらは鍵に依存しないので、暗号に関する重要性はない。
【００２７】
データ暗号化規格には、６４ビットブロックの鍵付きブロック符号化が記述されている。この鍵は公式には６４ビットであるが、実際にはそのうちの５６ビットのみが暗号化で使用される。暗号化及び復号は、ラウンドと呼ばれる１６回の反復を使用する。１≦ｒ≦１６のラウンドｒにおいて、４８ビットのラウンド鍵Ｋｒが使用され、そのビットは５６個の鍵ビットの（ラウンド依存の）サブセットである。
【００２８】
ＤＥＳラウンド関数ｆが図６ｂに示されており、
【数１】
2019504343.tif 000003
によって与えられる。ここで、Ｐは３２ビットの転置であり、Ｅは拡大写像（ｅｘｐａｎｓｉｏｎ  ｍａｐ）であって、ビットの半分を複製することによって長さ３２のビット列を長さ４８のビット列に写像するものである。ＳボックスＳは、６ビットの部分列にグループ単位で作用して、長さ４８のビット列を長さ３２のビット列に写像し、
Ｓ（ｂ１ｂ２ｂ３・・・ｂ４８）＝Ｓ１（ｂ１・・・ｂ６）｜｜Ｓ２（ｂ７・・・ｂ１２）｜｜・・・｜｜Ｓ８（ｂ４３・・・ｂ４８）
ここで、各ＳボックスＳｉは長さ６のビット列を長さ４のビット列に写像し、｜｜は連結を表す。図６ｂでは、ｓボックスＳ１の入力は参照６１１を有し、出力は参照６１２を有する。
【００２９】
Ｓボックス（置換ボックス）は、ブロック暗号のシャノンの撹乱（Ｓｈａｎｎｏｎ  ｃｏｎｆｕｓｉｏｎ）を増加させるためにブロック暗号でよく使用される。Ｓボックスは、一実施形態によるデータ関数として符号化されるのに特に適している。復号は逆方向に、すなわち、下から上へ行くことによって実行される。逆ラウンド関数は、
【数２】
2019504343.tif 000004
によって与えられる。
【００３０】
ＤＥＳはわずか５６ビットの鍵しか使用しないので、完全な鍵空間検索が実行可能であるが、特にソフトウェア実装での差分故障攻撃を使用した鍵回復は桁違いに速くなる。トリプルＤＥＳは３つの５６ビット鍵（Ｋ（１）、Ｋ（２）、Ｋ（３））を使用し、最初に鍵Ｋ（１）によるＤＥＳ暗号化を実施し、続いて鍵Ｋ（２）によるＤＥＳ復号、続いて鍵Ｋ（３）によるＤＥＳ暗号化を実施して暗号化する。
【００３１】
本明細書では、ブロック暗号の主要な例としてＤＥＳが使用され、データ関数の主要な例としてＤＥＳのＳボックスが使用される。実際に、ＤＥＳに基づく実施形態が広範にテストされており、以下にさらに示されるように、ＤＥＳのホワイトボックス符号化が一実施形態ではかなり小さいことが分かった。ＤＥＳの結果はただちにトリプルＤＥＳに渡り、その理由は、ＳボックスがＤＥＳと同一であるためである。他の実施形態は他のブロック暗号に、たとえば、ＡＥＳに、特にそのｓボックスに適用される。ＡＥＳはＤＥＳのようにＦｅｉｓｔｅｌ型ではないが、置換転置ネットワーク（ＳＰＮ：ｓｕｂｓｔｉｔｕｔｉｏｎ−ｐｅｒｍｕｔａｔｉｏｎ  ｎｅｔｗｏｒｋ）ブロック暗号である。ＳボックスＤＥＳは入力の方が出力よりも多いが（６対４）、ＡＥＳのＳボックスは入力及び出力の数が等しい。
【００３２】
一般に、以下に説明されるシステムの実施形態は、たとえば安全な実装を必要とする他の関数にも使用される。たとえば、ハッシュ又はメッセージ認証コードなどのセキュリティプリミティブが、一実施形態を使用して実装される。
【００３３】
図１は、データ関数１００の一例を概略的に示す。データ関数Ｓは、ｎ個の入力変数１１０をｍ個の出力変数１２０に写像する。たとえば、データ関数はＳボックス、たとえば、ＤＥＳのＳボックスである。データ関数１００の入力はビットであり、たとえば、ＤＥＳのＳボックスの場合、６個の入力ビット及び４個の出力ビットが存在する。ＡＥＳのＳボックスの場合、８個の入力及び出力ビットが存在する。ビット数は異なってもよく、たとえば、８個の入力ビット及び４個の出力ビットなどでもよい。
【００３４】
以下では、データ関数１００を
【数３】
2019504343.tif 000005
の形式の関数として表す。これは、２ｎの元を有する数学の体から、２ｍの元を有する体へのものである。たとえば、ＡＥＳのＳボックスのように、ｎ＝ｍとしてもよい。ｍ＜ｎの実施形態は、より小さい体Ｆ２ｍで全ての計算を行うことができるので特に有利であり、ｍ＜ｎの関数を「ファンネル（ｆｕｎｎｅｌ）」関数と呼ぶことにし、その理由は、範囲がドメインよりも真に小さいためである。ビットではなく、たとえば、３つ以上の異なる値をとる変数が使用される場合、それに応じてより大きい体を使用して計算を実行する。
【００３５】
図２ａは、計算デバイス２００の一実施形態の一例を概略的に示す。図１のデータ関数を実現するには、特に入力及び／又は出力の符号化が使用される場合、多くのストレージが必要となる。たとえば、ホワイトボックス実装では、図１のデータ関数はモノリシックテーブルとして実装される。しかしながら、ＤＥＳのＳボックスの場合でも、そのようなテーブルのデータ量は急速に増加する。たとえば、各ビットが１６個のシェアとして符号化され、各シェアがステートビットをさらに有し、計１６ステートビットとなる場合（可能な符号化のさらなる情報については以下を参照）、Ｓボックスの入力サイズは３２×６＝１９２ビットに膨らむ。これは、モノリシックテーブルが途方もなく大きくなり、２１９２個のエントリを有することを意味する。したがって、ホワイトボックスにおいて安全に符号化され得るが、記憶スペースはより少なくて済むデータ関数を符号化する異なる手法が望まれている。
【００３６】
計算デバイス２００は、入力２１１を受け取るように構成される。入力２１１は、データ関数１００の入力と同様である。入力は符号化される。入力２１１は複数のビットである。また、入力２１１はビットの代わりに、ある他の体、たとえば、Ｆ４（４つの元を有する体）からも取得される。入力変数は、１つ又は複数の選択変数と、１つ又は複数の評価変数とに区分される。原理的には、任意の区分が可能であるが、異なる選択肢には異なるトレードオフがある。一般的に言えば、選択ビットの数を増加させると実装サイズが小さくなるが、より少ない選択ビットを選択すると実装が高速になる。実装サイズとは、実装のストレージサイズ、特にホワイトボックス実装で使用されるテーブルサイズの合計を指す。テーブルが大きいとキャッシュミスが発生し、ひいては実行も遅くなる。
【００３７】
データ関数１００は、選択関数及び評価関数を含む計算として計算デバイス２００において構成される。選択変数（υ）の特定の値の組合せごとに、対応する選択関数δυ及び評価関数Ｓυが定義される。混乱を避けるために、評価関数Ｓυは必ずしもＤＥＳのＳボックスのいずれかに関連する必要はなく、また、インデックスυはここでは選択変数を指すことに留意されたい。
【００３８】
計算デバイス２００は、選択メカニズム２２０を備える。選択メカニズム２２０は、１つ又は複数の選択変数２２２を受け取るように構成される。選択変数である入力変数２１１の中の入力変数は、２２２で示されている。選択メカニズム２２２は、受け取られた選択変数について選択関数δυを評価するように構成される。たとえば、選択メカニズム２２０は、選択変数について選択変数（υ）の特定の値の組合せごとに各選択関数δυを評価する。選択関数δυは選択変数を入力として受け取り、選択関数の出力は、選択関数で受け取られた選択変数が選択関数に対応する特定の値の組合せ（ν）と等しいか否かを示す。選択メカニズムの出力は２２４で示されている。
【００３９】
選択関数は、複数の入力を有することを除いて、クロネッカーのデルタ関数である。数学的表記では、δｉ（ｊ）は、
【数４】
2019504343.tif 000006
を表す。
【００４０】
上記の例では、ｉ及びｊは、たとえば、全ての選択変数について、複数の入力を表す。さらに、選択関数は必ずしも出力０及び１を、便利ではあるが、返す必要はなく、他の値を使用してもよく、原理的には任意の２つの異なる値が使用され、計算デバイス２００の他の場所に収容される。
【００４１】
計算デバイス２００は、評価メカニズム２１０を備える。評価メカニズム２１０は、１つ又は複数の評価変数２１２を受け取り、受け取られた評価変数について評価関数を評価するように構成される。評価変数である入力変数２１１の中の入力変数は、２１２で示されている。
【００４２】
評価関数は入力として評価変数を受け取り、評価関数の出力は、評価変数と、評価関数に対応する選択変数の特定の値の組合せとの和集合を入力とするデータ関数の出力を表す。換言すれば、評価関数は、データ関数が評価変数を、評価関数が対応する選択変数の特定の値と共に入力として受け取っていたならば、データ関数が与えていたであろう結果を与える。
【００４３】
実施形態におけるアイデアは、選択関数が入力に存在する選択変数の特定の値の組合せを選択すること、ある意味では正しい評価関数を選択することである。選択関数は非常に実装が容易な関数である。選択関数は選択ビットの数のみに依存し、異なるデータ関数に対して同一である。したがって、選択関数は、同一の計算デバイスにおいて異なるデータ関数に対して再利用される。
【００４４】
評価メカニズム及び選択メカニズムは、評価ユニット及び選択ユニットとも呼ばれる。
【００４５】
計算デバイス２００は、選択メカニズム及び評価メカニズムの出力を、入力変数に対するデータ関数の出力に結合するように構成される結合メカニズムを備える。たとえば、結合メカニズムは、同一の特定の値の組合せに対応する選択関数（δυ）及び評価関数（Ｓυ）の積の総和（ΣｖδυＳυ）をとる。選択関数が値０及び１を与える場合、これは正しい評価関数を正確に特定する。選択関数が０及び１以外のある他の値を与える場合、選択関数の何らかの他の線形結合が使用される。
【００４６】
一実施形態では、総和は、選択変数（υ）の全ての値の組合せにわたるものである。このようにして、データ関数は、全ての入力変数に対して正しくエミュレートされる。しかしながら、選択変数のある組合せが発生しないことが分かっている場合、選択変数の可能な組合せにわたって総和をとるだけでよい。これにより、計算デバイスのサイズがさらに削減される。
【００４７】
以下、一実施形態の数学的説明が、さらなる明確化及び例示のために与えられる。
【００４８】
検討されるデータ関数は、関数
【数５】
2019504343.tif 000007
であり、ｍ＜ｎとしてもよいことに留意されたい。入力位置（又は変数）の集合｛１，．．．，ｎ｝から選択変数として位置ｉ１，．．．，ｉｎ−ｍを選択し、ｍ個の残りの位置をｐ１，．．．，ｐｍとし、評価変数を含む。ここで、各
【数６】
2019504343.tif 000008
について、関数
【数７】
2019504343.tif 000009
を、Ｓν（ｘ１・・・ｘｍ）＝Ｓ（ｙ１・・・ｙｎ）とすることによって定義し、ここで、ｊ＝１，．．．，ｎ−ｍについて、
【数８】
2019504343.tif 000010
であり、ｊ＝１，．．．，ｍについて、
【数９】
2019504343.tif 000011
である。換言すれば、各
【数１０】
2019504343.tif 000012
について、入力のｎ−ｍの選択をνで指定される値に設定することによって、関数ＳνがＳから得られる。Ｓ（ｘ）を計算するために、ｎ−ｍ個の選択された位置における入力ｘの値を考え、その値がνである場合、関数Ｓνを残りの入力シンボルに適用する。
【００４９】
Ｓ（ｘ）の安全な、ホワイトボックスなどの評価において、選択メカニズムは
【数１１】
2019504343.tif 000013
を選択し、次いで、入力ｘ及び出力Ｓ（ｘ）の両方に関する情報を明かすことなく、結果
【数１２】
2019504343.tif 000014
を返す。結合メカニズム２３０は、以下の恒等式
【数１３】
2019504343.tif 000015
を使用し、ここで、δｉ（ｊ）は、
【数１４】
2019504343.tif 000016
を満たす。
【００５０】
図２ｂは、評価メカニズム２１０の一実施形態の一例を概略的に示す。評価メカニズム２１０は、評価関数を実装する複数の評価ユニットを備え、図示されているのは評価ユニット２１５及び２１６である。評価ユニットはテーブル、たとえば、ルックアップテーブル、又はテーブルネットワークとして実装される。たとえば、図２ｂの評価メカニズムは、評価メカニズム２１０で受け取られた評価変数に対して関数２１５及び２１６を含む評価関数のそれぞれを評価する。選択関数の可能な値の組合せごとの評価関数が含まれる場合、正しい結果が評価関数に含まれることになる。複数の評価関数の複数の結果の中から正しい結果を選択することは、選択メカニズムによって実行される。
【００５１】
図２ｃは、選択メカニズム２２０の一実施形態の一例を概略的に示す。選択メカニズム２２０は、選択関数を実装する複数の選択ユニットを備え、図示されているのは選択ユニット２２５及び２２６である。選択ユニットはテーブル、たとえば、ルックアップテーブル、又はテーブルネットワークとして実装される。
【００５２】
図２ｄは、選択メカニズム２２０の一実施形態の一例を概略的に示す。一実施形態では、選択変数は、複数の選択変数のグループにさらに区分される。次いで、選択関数は、複数の選択変数のグループの中のグループにそれぞれが対応する複数のサブ選択関数の積として計算デバイス２００において構成され得、サブ選択関数はグループ内の選択変数を入力として受け取り、サブ選択関数の出力は、受け取られた選択変数が、選択関数に対応するグループ内の特定の値の組合せと等しいか否かを示す。
【００５３】
たとえば、図２ｄの選択メカニズム２２０において、選択ユニット２２５．１及び選択ユニット２２６．１は、第１のグループの選択変数を受け取り、選択ユニット２２５．２及び選択ユニット２２６．２は、第２のグループの選択変数を受け取る。３つ以上のグループがあってもよい。必要に応じて、選択変数及びダミー変数の数がグループ数の倍数になるまで、いくつかの選択変数がダミー変数、たとえば０でパディングされ、後者の場合、選択ユニットにおける入力の数は同一である。結合ユニット２２７は、同一の値の組合せに対応する選択ユニットの出力を結合するように構成される。たとえば、結合ユニット２２７は、結合ユニット２２５．１及び２２５．２の出力を、たとえば、乗算又は論理積演算によって結合する。
【００５４】
たとえば、一実施形態では、データ関数はファンネル関数であり、ｎ個の入力変数及びｍ個の出力変数を有する（ｍ＜ｎ）。この実施形態では、評価変数の数はｍとして選択され、選択変数の数はｎ−ｍとして選択される。選択変数のグループ数は、
【数１５】
2019504343.tif 000017
として選択される。これらの選択により、全ての計算を
【数１６】
2019504343.tif 000018
において行うことが可能となり、後者により、複数の異なる体において計算が必要とされる場合よりも、符号化された乗算及び加算テーブルのさらなる再利用が可能になる。たとえば、ｎ＝８及びｍ＝３の場合、１つのパディングビットを有する２つのグループの選択ビットが使用される。
【００５５】
以下、一実施形態の数学的記述が、さらなる明確化及び例示のために与えられる。より小さい出力体
【数１７】
2019504343.tif 000019
のみにわたる計算を保証するために、選択ビット
【数１８】
2019504343.tif 000020
をｍビットのチャンクに分割し、たとえば、
【数１９】
2019504343.tif 000021
とし、ここで、
【数２０】
2019504343.tif 000022
であり、各
【数２１】
2019504343.tif 000023
である。ｎ−ｍがｍで割り切れない場合、選択ビットを先行ゼロでパディングすることを、結果のビット数がｍで割り切れるまで行った後、分割を行う。ビットの代わりにｑ値の変数が使用される場合、上記の２ｍはｑｍに置き換えられる。
【００５６】
（ｉ１，ｉ２）＝（ｘ１，ｘ２）から、ｉ１＝ｘ１且つｉ２＝ｘ２の場合に限り、
【数２２】
2019504343.tif 000024
となる。
【００５７】
後者の結果は加算としても示され、論理比較
【数２３】
2019504343.tif 000025
となる。この式では、「＝」演算は、たとえば、等しくない場合は０を、等しい場合は１を返すクロネッカーデルタのような論理演算として解釈される。論理比較も、符号化済み変数に対してテーブルネットワークを使用して実行される。３つ以上のグループが使用される場合、式中の「２」はグループ数で置き換えられる。
【００５８】
一実施形態では、図２ｄの選択メカニズム２２０は、複数の選択変数のグループのそれぞれについて全ての値の組合せに対する選択関数を含む。たとえば、選択変数の２つのグループＡ及びＢに分割された８つの選択変数が存在する場合、選択メカニズム２２０は、グループＡの全ての可能な値の組合せに対する選択関数と、グループＢの全ての可能な値の組合せに対する選択関数とを含む。選択関数の完全なセットに対して特定の値の組合せに対する選択関数をエミュレートするために、結合ユニット２２７は、グループＡ及びグループＢから正しい選択関数を結合するように構成される。変数のグループに対する選択関数は、一致の有無を示すために０及び１を出力することもできる。これらの値は、乗算又は加算などで簡単に結合することができる。
【００５９】
選択メカニズムは、選択関数を実装する複数の選択ユニットを備え、たとえば、複数の選択ユニットは、選択関数を直接表し、又は選択変数のグループに対する選択関数を表す。
【００６０】
選択ユニット及び／又は評価ユニットは、テーブル又はテーブルネットワークとして実装される。
【００６１】
一実施形態では、入力変数の数（ｎ）は出力変数の数（ｍ）よりも大きく、評価変数の数は出力変数の数と等しい。選択変数の数は、入力変数の数と出力変数の数との差（ｎ−ｍ）と等しい。これにより、たとえば、体
【数２４】
2019504343.tif 000026
において、より少数の変数を使用して、全ての計算を行うことが可能になる。
【００６２】
変数ｗを符号化するいくつかの手法が存在する。変数ｗは選択変数又は評価変数に直接対応する。しかしながら、変数ｗはいくつかの変数を一緒にまとめることもできる。たとえば、計算デバイス２００は、複数の変数に一緒に演算を行うように構成される。たとえば、一実施形態では、選択変数、評価変数、及び出力変数は、単一ビットを表すビット変数である。一実施形態では、複数のビット変数はより大きい変数へと結合される。
【００６３】
たとえば、一実施形態では、変数３１０は、２つ又は４つの選択変数又は評価変数を表す。たとえば、ファンネル関数の場合、より大きい変数が出力変数と同一のビット数（ｍ）を有する。（ｎ−ｍ）個の選択変数は、それぞれがより大きい変数で表される、（ｍ個の）変数の１つ又は複数のグループにまとめられる。
【００６４】
たとえば、ＤＥＳのｓボックスは、４つの出力ビット変数と、６つの入力ビット変数とを有する。この場合、より大きい変数ｗは４ビットを表す。入力ビットは、単一のより大きい４ビット変数によって表される４つの評価ビットと、同様に単一の（より大きい）４ビット変数によって表される２つの選択変数とに区分される。
【００６５】
たとえば、ＡＥＳのｓボックスは、８つの出力ビット変数と、８つの入力ビット変数とを有する。この場合、より大きい変数ｗは同様に４ビットを表す。入力ビットは、単一のより大きい４ビット変数によって表される４つの評価ビットと、同様に単一のより大きい４ビット変数によって表される４つの選択変数とに区分される。出力は、２つのより大きい４ビット変数によって表される。以下、ビット変数かより大きい変数かに関わらず、変数ｗが表現される手法が説明される。
【００６６】
変数ｗは、写像Ｅｎｃ（ｗ）を介して符号化される。符号化は暗号化の符号化であり、ランダムに選択されてもよく、又は秘密鍵を使用した暗号化などでもよい。使用される符号化は攻撃者には未知である。変数ｗが処理される場合、符号化はデバイス内で暗黙的に想定される。また、変数はステート変数ｓと共に符号化されるＥｎｃ（ｗ，ｓ）であり、これはｗと符号化との関係をさらに撹乱する。より安全な符号化は、変数を複数のシェアに分割し、各シェアを、好ましくはステート変数と共に符号化する。後者のタイプの符号化は最も安全であるが、特にこのタイプの符号化では、テーブルネットワークとしてのデータ関数の表現と組み合わせることが難しい。
【００６７】
図３は複数のシェアを使用する変数ｗを符号化する手法を示す。図３は変数３１０、ｗを示し、ｗの衝突が回避されるように、暗号化デバイス２００などの暗号化デバイスでの使用のためにｗが符号化される手法を示す。変数３１０、ｗは複数のシェアｗｊに分散される。ｗのビットサイズをｋと呼ぶことにする。一実施形態では、シェアｗｊのビットサイズはｗのビットサイズに等しい。異なる変数は異なるビットサイズを有し得る。たとえば、ｋは１，２，４以上である。一実施形態では、ｋ＝１，２，３，４、５、６、７、８又はそれ以上である。図示されているのはシェア３２１、３２２及び３２３である。
【００６８】
シェアは、
【数２５】
2019504343.tif 000027
となるように選択される。一実施形態では、この総和はＸＯＲ関数を使用して総和をとるが、他の選択肢も可能である。たとえば、総和は、算術加算モジュロ２ｋを使用する。
【００６９】
より一般的には、シェア（ｗｊ）を変数（ｗ）に写像する結合関数（ｄ（ｗ１，．．．，ｗｎ−１）＝ｗ）が定義される。結合関数は上述のＸＯＲ又は算術加算である。結合関数は、任意の単一のシェア（ｗｋ）から変数（ｗ）への写像であって、他のシェア（ｗ１，．．．，ｗｋ−１，ｗｋ＋１，．．．，ｗｎ−１）の値を固定することによって得られる写像が全単射であるという特性を有する。すなわち、関数
【数２６】
2019504343.tif 000028
は全単射であり、要素
【数２７】
2019504343.tif 000029
は固定値を表す。この特性は、ｗに関する情報を与えるシェアのサブセットが存在しないことを保証する。多数のそのような結合関数が存在する。たとえば、ｄはシェアの任意の線形結合
【数２８】
2019504343.tif 000030
であり、ここで係数αｊは奇数であり、総和は算術加算モジュロ２ｋを使用する。結合関数は多項式である。
【００７０】
図３は複数のステートｓｊをさらに示す。図示されているのはステート３３１、３３２及び３３３である。シェア３２１〜３２３の数はステート３３１〜３３３の数と同一である。ステートは変数の符号化に冗長性を導入する冗長データである。シェアのそれぞれはステートの１つと共に並べられ、符号化済みシェアｘｊ＝Ｅｎｃｊ（ｗｊ，ｓｊ）に符号化される。一実施形態では、符号化Ｅｎｃｊは異なる。たとえば、符号化Ｅｎｃｊはコンパイル時にランダムに選択される。符号化は、ｗｊに関して可逆である限り、すなわち、Ｅｎｃｊ及びｘｊが既知であればシェアｗｊが回復され得る限り、全単射であることは厳密には必須ではない。それにもかかわらず、実施形態では、符号化Ｅｎｃｊは全単射である。後者は実装においてより現実的な選択肢であり、解析を簡素化する。どの変数がどの符号化によってどの時点で符号化されるかが決定されると、テーブルは符号化を考慮に入れるように単純に適合される。ステートの使用は任意選択であるが、同一のデータ値に対して複数の表現が可能であるため、ステートが難読化が高まるので好ましい。
【００７１】
図３は、シェア３２１及びステート３３１が符号化３６１を介して符号化済みシェア３４１へと符号化されることを示す。また、シェア３２２及びステート３３２は符号化３６２を介して符号化済みシェア３４２へと符号化され、シェア３２３及びステート３３３は符号化３６３を介して符号化済みシェア３４３へと符号化される。変数ｗを表すために共に符号化されるステート及びシェアを、その変数に対応するものとして参照することにする。
【００７２】
複数の符号化済みシェアが結果であり、そのうち、符号化済みシェア３４１、３４２、及び３４３が図示されている。一実施形態では、変数ｗは暗号化デバイス２００において複数の符号化済みシェアとして表される。未符号化シェア３２１〜３２３もステート３３１〜３３３も暗号化デバイス内に存在してはならない。
【００７３】
ステートは、最初はランダムに選択され、その後、変数ｗを更新する同一のプロセスによって更新される。一実施形態では、同一の変数ｗに対応する複数のステートｓｊは、入力メッセージＭ  ３１０から複数のステートへ、Σと表される単射写像３５２が存在するように選択される（Σ（Ｍ）＝（ｓ０，．．．，ｓｎ−１）。単射写像は、Ｍ＝Ｍ’の場合にのみΣ（Ｍ）＝Σ（Ｍ’）となる特性を有する。特に、Σは全単射となるように選択され、その理由は、このより厳しい条件が単射性を含意するためである。図３は、複数のステート３３１〜３３３が入力メッセージ３００、Ｍ及び単射写像Σ、３５２にどのように依存するかを示す。たとえば、入力メッセージ３００は、入力メッセージ６１０である。入力メッセージ３００は、たとえば、外部デバイス２００から受け取られる入力メッセージ、たとえば、ブロック暗号への入力である。ステートが入力メッセージＭ、３００を符号化する場合、異なるＭは異なる符号化済み変数ｘ０，．．．，ｘｎ−１につながる。
【００７４】
写像３５２は、大部分又は全ての変数について暗号化関数の実装において明示的である必要はない。たとえば、符号化済み変数が入力メッセージとの必要な単射関係を有すると、符号化済み変数のシェア部分ｗｊに実施される演算は、単射関係を保存するステート部分に対して冗長な演算を同時に実施する。符号化済み領域で計算が行われるので、ステートへの計算はシェアへの計算から分離することができない。
【００７５】
たとえば、第１及び第２の変数ｗ１及びｗ２の両方が上記のように複数の符号化済みシェア
【数２９】
2019504343.tif 000031
及び
【数３０】
2019504343.tif 000032
として符号化されることを考える。ｗ１及びｗ２への演算ｇが第３の変数ｗ３＝ｇ（ｗ１，ｗ２）を計算すると仮定する。変数ｗ３は符号化済みシェア
【数３１】
2019504343.tif 000033
と表される。一実施形態では、
【数３２】
2019504343.tif 000034
に符号化されたステートは、
【数３３】
2019504343.tif 000035
又は
【数３４】
2019504343.tif 000036
に符号化されたステートに等しい。この場合、入力が入力メッセージＭとの必要な関係を有する場合は、出力ｗ３も同様になる。このようにして、必要な関係はその計算全体にわたって保存される。その演算は、その演算を実施するためのテーブルネットワークとして実装され、このテーブルネットワークは暗号化関数を実装するテーブルネットワークのサブネットワークである。
【００７６】
初期変数、たとえば、入力メッセージから直接得られるものは、暗号デバイス２００によって正しい符号化された形式で受け取られる。或いは、デバイス２００は、入力を符号化するように構成される符号化デバイスを備える。
【００７７】
変数ｗをステート及び／又は複数のシェアと共に符号化することにより、暗号化関数の実行中に符号化された値に衝突が生じにくくなる。したがって、この時点では衝突攻撃は不可能である。
【００７８】
実際的な一実施形態では、符号化済みシェアによる表現以外のｗの表現はない。さらに、より多くの機密変数がこのように保護される場合、保護はより効果的である。鍵及び入力メッセージの両方に依存する全ての変数は保護されることが好ましい。衝突攻撃を防止するために、鍵による演算が実施される前に、入力メッセージが符号化済みシェアとして表される必要はない。しかしながら、単射写像が存在し維持されることを保証することは、鍵が使用される前であっても、入力メッセージを複数組の符号化済みシェアとして符号化させることによって単純化される。
【００７９】
テーブルネットワークは、ホワイトボックス暗号自体から知られている。たとえば、Ｃｈｏｗらによる「Ｗｈｉｔｅ−ｂｏｘ  ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ａｎ  ＡＥＳ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」を参照されたい。テーブルネットワーク４２０の一例が図４ａに示されており、この場合、外積を計算するためのテーブルネットワークである。
【００８０】
テーブルネットワークは、１つ又は複数の入力、たとえば入力４１０を受信し、１つ又は複数の出力、たとえば出力４３０を生成する。テーブルネットワーク４２０には、複数のルックアップテーブルが示されており、図示されているのはテーブル４２１〜４２４である。テーブルは、入力４１０から直接的に、及び／又は他のテーブルの出力から入力を受け取る。テーブルは、１つの入力、２つの入力、又は３つ以上の入力を受け取る。
【００８１】
未符号化変数ｗへの計算を複数のシェアとして符号化された変数ｗへの計算に変換する便利な手法が、Ｃａｒｌｅｔらによる「Ｈｉｇｈｅｒ−Ｏｒｄｅｒ  Ｍａｓｋｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｓ−ｂｏｘｅｓ」に提供されている。この論文は、衝突攻撃も、ステートと併せた符号化も論じていない。この論文はさらにＣａｒｌｅｔと呼ばれる。Ｃａｒｌｅｔは、複数のシェアとして符号化された変数の衝突を防がない。
【００８２】
以下、たとえば関数値Ｄ（ｗ）を計算するための変数ｗへの計算が、複数のシェアに符号化された変数ｗへの計算に変換される手法が説明される。関数Ｄはデータ関数であるが、暗号化関数の計算の任意の内部ステップ、たとえば、加算、乗算などに同一の方法が使用される。シェアのＤ（ｗ）を計算するテーブルネットワークを構築する手法を示す。まず、ここではＤが単一の入力ｗを有する場合を考える。複数のステートが同様に扱われ得る。また、最初はステートを無視し、後でステートが追加され得る手法を示す。
【００８３】
ｗがｎ個のシェアｗ０，．．．，ｗｎ−１で表される場合、その結果の変数にｗと同一の保護を与えるために、Ｄ（ｗ）もｎ個のシェアによって表すようにしたい。これは以下の事実を利用することによって、任意の関数に対して可能である。
【００８４】
説明のために、まず、値Ｄ（ｗ）もｗのようにｋビットの数であると仮定する。ｋビットの数は有限のガロア体
【数３５】
2019504343.tif 000037
の要素であり、関数Ｄは
【数３６】
2019504343.tif 000038
上の関数であると考えられ得る。有限体の全ての関数は多項式であるため、
【数３７】
2019504343.tif 000039
上の任意の関数Ｄに対して、係数
【数３８】
2019504343.tif 000040
が存在し、これは任意のｗについて、
【数３９】
2019504343.tif 000041
が成立するものである。
【００８５】
また、データ関数Ｓ（ｘ）は多変量多項式
【数４０】
2019504343.tif 000042
として表され、ここで、｛Ｐν｝νは、
【数４１】
2019504343.tif 000043
上の評価関数Ｓνを表す多項式の集合を表し、｛Ｑν｝νは選択多項式、すなわち、
【数４２】
2019504343.tif 000044
上のデルタ｛δｉ｝ｉを表す多項式の集合を表す。
【００８６】
多項式Ｄ並びに多項式Ｑυ及びＰυは同様に、以下のようなシェアへの計算として表される。シェアがＸ＝（ｘ０，．．．，ｘｎ−１）及びＹ＝（ｙ０，．．．，ｙｎ−１）によって与えられるとする。簡単のため、シェアの和が未符号化変数と等しいと仮定する。Ｘ及びＹの和はシェアｘｉ＋ｙｉで符号化され得る。スカラー倍αＸはシェアαｘｉで符号化される。最後に、ＺをＸ及びＹの積とする。０≦ｉ＜ｊ≦ｎ−１について、値ｒｉ，ｊ及びｒｊ，ｉを定義する。
【００８７】
たとえば、ランダムなｋビット列を選択することにより、ｒｉ，ｊに対して、
【数４３】
2019504343.tif 000045
のランダムな要素をとる。一実施形態では、ｒｉ，ｊについての乱数は、コンパイル時に入力メッセージＭから
【数４４】
2019504343.tif 000046
へのランダム化関数Ｒｉ，ｊを選択し、ｒｉ，ｊ＝Ｒｉ，ｊ（Ｍ）を設定することによって得られる。後者は実行時に乱数発生器への依存が回避されるという利点を有する。コンパイル時と呼ばれる、テーブルネットワークが構築されるときにのみ、ランダム性のソースが必要とされる。Ｃａｒｌｅｔは実行中にランダム性に依存することに留意されたい。これは実行中の乱数源の操作までＣａｒｌｅｔを開放する。具体的には、乱数発生器は傍受され定数値に置き換えられる。
【００８８】
ｒｊ，ｉ＝（ｘｉｙｊ＋ｒｉ，ｊ）＋ｘｊｙｉをとり、ここでの計算の順序は重要であり、括弧で示されている。ここで、０≦ｉ≦ｎ−１について、
【数４５】
2019504343.tif 000047
をとる。
【００８９】
外積テーブルサブネットワークはｒｊ，ｉを計算する。これらのテーブルは２つの外積ｘｉｙｊ及びｘｊｙｉを計算する。
【００９０】
一実施形態では、ｒｉ，ｊを計算するためにランダム化関数Ｒｉ，ｊは、入力メッセージを入力とするテーブルネットワークとして実装される。これは実行中に乱数源が必要となるのを回避する。
【００９１】
シェアｚｉはこのときＸ及びＹの積を表す。加算、スカラー乗算及び乗算演算を使用して、Ｓの多項式表現はシェアへの演算として表される。次いで、シェアへの演算は、１つ又は複数のシェア及び／又は乱数を入力とするルックアップテーブルとして実装される。
【００９２】
ｒｊ，ｉを計算するための可能なテーブルネットワーク４２０が図４ａに示されている。テーブル４２１〜４２４は協力してｒｊ，ｉを計算する。テーブルネットワーク４２０への入力は、参照符号４１０に示されている。テーブルネットワーク４２０の出力は、参照符号４３０に示されている。
【００９３】
たとえば、テーブル４２１及び４２２はそれらの入力を乗算するように構成され、テーブル４２３及び４２４はそれらの入力を加算するように構成される。各テーブルが異なる符号化を使用し得ることに留意されたい。
【００９４】
図４ｂは乗算テーブルネットワーク４４０の一実施形態の一例を概略的に示す。乗算テーブルネットワーク４４０は、上記で与えられた式を使用してＺ＝（ｚ０，．．．，ｚｎ−１）を計算するように構築される。乗算テーブルネットワーク４４０は、たとえばそのデータストアの計算デバイス２００に第１の複数の符号化済みシェア（ｘｊ）として表される変数Ｘと、第２の複数の符号化済みシェア（ｙｊ）として表される第２の変数Ｙとを乗算するように構成される。乗算テーブルネットワークは、第１及び第２の複数の符号化済みシェア（ｘｊ、ｙｊ）に作用し、第１及び第２の変数の積を表す第３の複数の符号化済みシェア（ｚｊ）を取得する。ここでは、上付き添字はシェアを指し、指数ではないことに留意されたい。乗算テーブルネットワーク４４０は、暗号化関数を計算するためのテーブルネットワークの一部である。
【００９５】
乗算テーブルネットワーク４４０は、外積ｘｉｙｊを計算するための外積テーブルサブネットワークを含む。一実施形態では、外積は２つ一組、ｘｉｙｊ＋ｘｊｙで計算されるｉ。たとえば、乗算テーブルネットワーク４４０はテーブルネットワーク４２０を含む。乗算テーブルネットワーク４４０は、１つ又は複数のランダム化関数Ｒｉ，ｊを計算するためのテーブルネットワーク４５０をさらに含む。図４ｂにおいて、テーブルネットワーク４５０は入力メッセージ１１０に依存する。この依存性は破線で示されており、これはデータストアに記憶された変数などの中間物を介して依存性が得られることを示す。テーブルネットワーク４４０はその入力を取得し、その出力を計算デバイス２００のデータストアに記憶する。
【００９６】
シェアに作用するテーブルは、符号化済みシェアに作用するテーブルに変換される。符号化済みシェアｘについて、Ｅｎｃ（ｔ（ｘ），ｓ（ｘ））＝ｘとなるようにｓ及びｔを定義する。関数ｓ及びｔは、ｘからそれぞれステート及びシェアを取得する。ｔ（ｘ）に対するテーブルＴを定義する。次いで、Ｅｎｃ’（Ｔ（ｔ（ｘ）），Ｐ（ｓ（ｘ）））は、ｘのシェア部分のテーブルＴとステート部分の関数Ｐとを実装するｘのテーブルを定義する。関数Ｐは冗長であり、コンパイル時などにテーブルネットワークを作成する場合に選択される。たとえば、Ｐは恒等関数である。複数の入力に対して同様の構成が可能である。ここで使用される符号化Ｅｎｃは入力符号化とも呼ばれる。符号化Ｅｎｃ’は出力符号化と呼ばれる。テーブルの出力に使用される出力符号化が、前記出力を入力として使用する次のテーブルの入力符号化と同一である限り、テーブルの入力及び出力符号化は同一である必要はない。
【００９７】
図２ｅは、データストア２４２及びテーブルストア２４４を備える、たとえば、図２ａに関して説明されたような計算デバイス２００の一実施形態を示す。データストア２４２は、計算デバイス２００が作用する変数を記憶するように構成される。具体的には、データストア２４２は、複数の符号化済みシェアなどの符号化済み変数を記憶する。テーブルストア２４４は、選択メカニズム２２０及び評価メカニズム２３０を実装するための１つ又は複数のテーブルネットワークを記憶するように構成される。データストア２４２及びテーブルストア２４４は電子メモリである。それらは同一のメモリの２つの部分である。テーブルストア２４４は不揮発性ストレージである。データストア２４２は揮発性ストレージである。
【００９８】
計算デバイス２００は、テーブルストア２４４の複数のルックアップテーブルをデータストア２４２に表現された変数に適用することによって、データ関数をブロック暗号の一部などとして入力メッセージなどに適用するように構成される制御ユニット２４３を備える。たとえば、テーブルストア２４４は、テーブルがどの順番でどの変数に適用されるかを示す命令をさらに含む。
【００９９】
計算デバイス２００はネットワークインタフェース２５０を備える。ネットワークインタフェース２５０は、コンピュータネットワークを介して符号化されたデータを受信するように構成される。たとえば、計算デバイス２００は、暗号化されたデータ、たとえば、暗号化されたコンテンツを受信し、これは暗号化デバイス２００によって復号される。ネットワークインタフェース２５０を介して受信された入力は、たとえば上述したように、符号化済みシェアとして表される。これは、符号化がデバイス２００の内部で行われるので、必須ではない。
【０１００】
典型的には、デバイス２００は、デバイス２００に記憶された適切なソフトウェアを実行するマイクロプロセッサ（別個に図示せず）を備え、たとえば、そのソフトウェアは対応するメモリ、たとえばＲＡＭなどの揮発性メモリ、又はフラッシュなどの不揮発性メモリ（別個に図示せず）にダウンロード及び／又は記憶される。或いは、デバイス２００は、たとえばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）として、プログラマブルロジックに全体的又は部分的に実装される。デバイス２００は、いわゆる特定用途向け集積回路（ＡＳＩＣ）、すなわち、それらの特定の用途向けにカスタマイズされた集積回路（ＩＣ）として、全体的又は部分的に実装される。たとえば、回路は、たとえば、Ｖｅｒｉｌｏｇ、ＶＨＤＬなどのハードウェア記述言語を使用して、ＣＭＯＳで実装される。
【０１０１】
一実施形態では、デバイス２００は、選択回路、評価回路、及び結合回路を備える。デバイス２００は追加の回路、たとえば、選択変数のグループ用の選択回路などを備えてもよい。回路は、本明細書に記載された対応するユニット及びメカニズムを実装する。回路はプロセッサ回路及び記憶回路であり、プロセッサ回路は記憶回路内で電子的に表される命令を実行する。回路もＦＰＧＡ、ＡＳＩＣなどである。
【０１０２】
以下、選択ビット及び評価ビットへの上記の区分に続くＤＥＳのＳボックスのコードサイズへの影響が論じられる。Ｇｏｕｂｉｎらによる「Ｈｉｇｈｅｒ−Ｏｒｄｅｒ  Ｍａｓｋｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｓ−Ｂｏｘｅｓ」に開示され、さらにＧｏｕｂｉｎと呼ばれる方法、及び、Ｃｏｒｏｎらによる「Ｆａｓｔ  ｅｖａｌｕａｔｉｏｎ  ｏｆ  ｐｏｌｙｎｏｍｉａｌｓ  ｏｖｅｒ  ｂｉｎａｒｙ  ｆｉｎｉｔｅ  ｆｉｅｌｄｓ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｓｉｄｅ−ｃｈａｎｎｅｌ  ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ」に開示され、さらにＣｏｒｏｎと呼ばれる方法との比較が行われる。
【０１０３】
表１に３つの方法、すなわち、
【数４６】
2019504343.tif 000048
上のＧｏｕｂｉｎの単純なＣｙｃｌｏｔｏｍｉｃの方法、
【数４７】
2019504343.tif 000049
上のＣｏｒｏｎのＣＲＶの方法、及び、
【数４８】
2019504343.tif 000050
上の、２つの選択ビットを使用した一実施形態による解決策をリスト化している。ここで、ｋは変数を表すために使用されるシェアの数を表す。
【０１０４】
【表１】
2019504343.tif 000051
【０１０５】
表２において、ＤＥＳに適用された場合の３つの方法に使用されるバイト数がカウントされ、ここでｋ＝１６であり、各ｎビットのシェアには４ビットのステートが付随し、すなわち、
【数４９】
2019504343.tif 000052
上の各変数はビットサイズｎ＋４の１６個のシェアによって表される。したがって、加算及び乗算用のテーブルのサイズは（ｎ＋４）ビットの２２（ｎ＋４）個のエントリを有する。テーブル参照ごとに異なる符号化に基づいて異なるテーブルが使用されるＤＥＳ実装と、テーブル及び符号化が再利用される実装との両方の結果を与える。ここでは、Ｇｏｕｂｉｎ及びＣｏｒｏｎの手法ではｎ＝６であるが、６ビットの入力を２つの選択ビットと４つの評価ビットとに分割する一実施形態によればｎ＝４である。
【０１０６】
【表２】
2019504343.tif 000053
【０１０７】
一実施形態による解決策は、他の解決策に比べて１０％未満のメモリしか必要としないことに留意されたい。一番下の行の結果は上記の議論から得られ、以下では、一般的な理論がどのようにＤＥＳに適用され得るかについて詳述される。
【０１０８】
データ暗号化標準は、６ビット入力を４ビット出力に写像する８つのＳボックス（Ｓ１，．．．，Ｓ８）を有する。以下、各ＤＥＳのＳボックスを評価するための
【数５０】
2019504343.tif 000054
上の算術回路を作成する手法を示す。そして、この算術回路は、上述のシェア演算によって評価することができる。νがサイズ６−４＝２ビットを有することに留意されたい。したがって、
【数５１】
2019504343.tif 000055
の単一の元で表すことができ、［ν］と表される。
【数５２】
2019504343.tif 000056
上の異なる値の数は、２２＝４である。パディング後、これらは、
［０］＝（０，０，０，０）
［１］＝（０，０，０，１）
［２］＝（０，０，１，０）
［３］＝（０，０，１，１）
となる。
【数５３】
2019504343.tif 000057
上の４つの選択多項式Ｑｉは、以下のように計算される。
【数５４】
2019504343.tif 000058
上のＱ０、Ｑ１、Ｑ２、Ｑ３を、
Ｑ０＝ＬａｇｒａｎｇｅＩｎｔｅｒｐｏｌａｔｅ（｛［０］，［１］｝，｛［１］，［０］｝，｛［２］，［０］｝，｛［３］，［０］｝）
Ｑ１＝ＬａｇｒａｎｇｅＩｎｔｅｒｐｏｌａｔｅ（｛［０］，［０］｝，｛［１］，［１］｝，｛［２］，［０］｝，｛［３］，［０］｝）
Ｑ２＝ＬａｇｒａｎｇｅＩｎｔｅｒｐｏｌａｔｅ（｛［０］，［０］｝，｛［１］，［０］｝，｛［２］，［１］｝，｛［３］，［０］｝）
Ｑ３＝ＬａｇｒａｎｇｅＩｎｔｅｒｐｏｌａｔｅ（｛［０］，［０］｝，｛［１］，［０］｝，｛［２］，［０］｝，｛［３］，［１］｝）
によって計算する。
【０１０９】
そして、各ＳボックスＳｉについて、νを定義するための選択変数として最初及び最後の入力ビットを選択し、すなわち、入力ｘ＝ｘ０，．．．，ｘ５について、ν＝ｘ０，ｘ５を定義する。次いで、評価多項式
【数５５】
2019504343.tif 000059
を以下のように計算する。
ｆｏｒ  ν∈｛０，１，２，３｝  ｄｏ
Ｚ＝Φ
ｆｏｒ
【数５６】
2019504343.tif 000060
ｄｏ
Ｚ＝Ｚ∪｛ｘ，（Ｓｉ）ν（ｘ）｝
ｅｎｄ  ｆｏｒ
【数５７】
2019504343.tif 000061
ｅｎｄ  ｆｏｒ
ｒｅｔｕｒｎ
【数５８】
2019504343.tif 000062
【０１１０】
最後に、Ｓｉ（ｘ）を安全に計算するために、式
【数５９】
2019504343.tif 000063
【０１１１】
が評価され、ここで、各多項式がシェアに対して評価される。ここで、ｌ＝｛ｌ１，．．．，ｌｋ｝はｘ０，ｘ５を表し、ｒ＝｛ｒ１，．．．，ｒｋ｝はｘ１，ｘ２，ｘ３，ｘ４を表し、ｓ＝｛ｓ１，．．．，ｓｋ｝は結果Ｓｉ（ｘ）を表す。
【０１１２】
この解決策は、Ｃｙｃｌｏｔｏｍｉｃの方法を使用して
【数６０】
2019504343.tif 000064
に必要なｒの全てのべき乗を計算するための
【数６１】
2019504343.tif 000065
上での４回の乗算と、次数３の多項式Ｑ０，Ｑ１，Ｑ２，Ｑ３を評価するために必要なｌのべき乗を計算するための１回の乗算とを必要とする。そして、積
【数６２】
2019504343.tif 000066
を計算するために、４回の乗算が必要である。結論として、この解決策は、
【数６３】
2019504343.tif 000067
上での９回の乗算を必要とする。多項式
【数６４】
2019504343.tif 000068
はそれぞれ１５回の加算を必要とし、多項式Ｑｊはそれぞれ３回の加算を必要とする。したがって、我々の解決策は４＊１５＋４＊３＋３＝７５回の加算を必要とする。
【０１１３】
図５ａは、計算方法５００のフローチャートを概略的に示す。計算方法５００は、ｎ個の入力変数をｍ個の出力変数に写像するデータ関数（Ｓ）を評価し、データ関数が選択関数及び評価関数を含む計算として計算方法において構成され、入力変数が１つ又は複数の選択変数及び１つ又は複数の評価変数に区分され、選択変数（υ）の特定の値の組合せごとに、対応する選択関数（Ｑυ）及び評価関数（Ｐυ）が定義される。計算方法５００は、
−  １つ又は複数の選択変数を受け取ることと、
−  受け取られた選択変数について選択関数を評価することであって、選択関数が選択変数を入力として受け取り、選択関数の出力が、選択関数において受け取られた選択変数が、選択関数に対応する特定の値の組合せに等しいか否かを示す、評価することと
を含む、選択部分５１０と、
−  １つ又は複数の評価変数を受け取ることと、
−  受け取られた評価変数について評価関数を評価することであって、評価関数が評価変数を入力として受け取り、評価関数の出力が、評価変数と、評価関数に対応する選択変数の特定の値の組合せとの和集合を入力とするデータ関数の出力を表す、評価することと
を含む、評価部分５２０と、
選択メカニズム及び評価メカニズムの出力を、入力変数に対するデータ関数の出力に結合する結合部分５３０と
を有する。
【０１１４】
計算方法５５０のさらなる実施形態は、
−  複数の符号化済みシェアとして符号化されることが好ましい入力変数を受け取ること５６０と、
−  受け取られた入力変数の中の実際に受け取られた選択変数を入力として、選択変数の値の組合せごとに選択多項式を評価すること５７０と、
−  受け取られた入力変数の中の実際に受け取られた評価変数を入力として、選択変数の値の組合せごとに評価多項式を評価すること５８０と、
−  たとえば、選択多項式の結果と、対応する評価多項式の結果とを乗算し、乗算の結果を加算することによって、選択多項式及び評価多項式の結合を計算すること５９０と
を有する。
【０１１５】
評価５７０及び５８０並びに計算５９０は、符号化済み変数に演算を行うテーブルネットワークによって実施される。
【０１１６】
当業者には明らかであるように、方法５００及び５５０を実行する多くの異なる手法が可能である。たとえば、ステップの順序は変更され得て、又はいくつかのステップは並行して実行される。さらに、ステップの間に、他の方法のステップが挿入される。挿入されたステップは、本明細書に記載されるような方法の改良を表し、又は方法と無関係である。たとえば、ステップ５７０及び５８０は、少なくとも部分的に並列に実行される。さらに、所与のステップは、次のステップが開始される前に完全に終了していない。
【０１１７】
本発明による方法は、プロセッサシステムに方法５００及び／又は５５０を実施させる命令を含むソフトウェアを使用して実行される。ソフトウェアは、システムの特定のサブエンティティによってとられるステップのみを含む。ソフトウェアは、ハードディスク、フロッピー、メモリ、光ディスクなどの適切な記憶媒体に記憶される。ソフトウェアは信号としてワイヤに沿って、若しくは無線で、又はインターネットなどのデータネットワークを使用して送信される。ソフトウェアは、ダウンロード及び／又はサーバ上でのリモート使用が可能にされる。本発明による方法は、方法を実施するためにフィールドプログラマブルゲートアレイ（ＦＰＧＡ）などのプログラマブルロジックを構成するようになされるビットストリームを使用して実行される。
【０１１８】
本発明が、本発明を実施するように適合されたコンピュータプログラム、特に、キャリア上又は内のコンピュータプログラムにも拡張されることは理解されよう。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、及びオブジェクトコード、たとえば部分的にコンパイルされた形式、又は本発明による方法の実施での使用に適した任意の他の形式のものである。コンピュータプログラム製品に関する一実施形態は、記載された方法のうちの少なくとも１つの処理ステップのそれぞれに対応するコンピュータ実行可能命令を含む。これらの命令はサブルーチンに細分され、及び／又は静的若しくは動的にリンクされる１つ又は複数のファイルに記憶される。コンピュータプログラム製品に関する別の実施形態は、記載されたシステム及び／又は製品のうちの少なくとも１つの手段のそれぞれに対応するコンピュータ実行可能命令を含む。
【０１１９】
図７ａはコンピュータプログラム１０２０を含む書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示し、コンピュータプログラム１０２０は、プロセッサシステムに一実施形態による計算の方法を実施させるための命令を含む。コンピュータプログラム１０２０は、コンピュータ可読媒体１０００上に物理的なマークとして、又はコンピュータ可読媒体１０００の磁化によって具現化される。しかしながら、任意の他の適切な実施形態も考えられる。さらに、コンピュータ可読媒体１０００はここでは光ディスクとして示されているが、コンピュータ可読媒体１０００は、ハードディスク、ソリッドステートメモリ、フラッシュメモリなどの任意の適切なコンピュータ可読媒体であり、記録不可能又は記録可能であることは理解されよう。コンピュータプログラム１０２０は、プロセッサシステムに前記計算の方法を実施させるための命令を含む。
【０１２０】
図７ｂは一実施形態によるプロセッサシステム１１４０の概略図を示す。プロセッサシステムは１つ又は複数の集積回路１１１０を備える。１つ又は複数の集積回路１１１０のアーキテクチャは図７ｂに概略的に示されている。回路１１１０は、一実施形態による方法を実行し、及び／又はそのモジュール若しくはユニットを実装するためのコンピュータプログラムコンポーネントを動作させるための、ＣＰＵなどの処理ユニット１１２０を備える。回路１１１０は、プログラミングコード、データなどを記憶するためのメモリ１１２２を備える。メモリ１１２２の一部は読み出し専用である。回路１１１０は通信素子１１２６、たとえば、アンテナ、コネクタ又はその両方などを備える。回路１１１０は、本方法で定義された処理の一部又は全部を実施するための専用集積回路１１２４を備える。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４及び通信素子１１２６は相互接続１１３０、たとえばバスを介して互いに接続される。プロセッサシステム１１１０は、アンテナ及び／又はコネクタを使用して、それぞれ接触及び／又は非接触通信用に構成される。
【０１２１】
上記の実施形態は本発明を限定するものではなく例示するものであり、当業者は多くの代替的実施形態を考案できることに留意されたい。
【０１２２】
特許請求の範囲において、括弧内に置かれた任意の参照符号は、特許請求の範囲を限定するものとして解釈されるべきではない。「備える」という動詞及びその活用形の使用は、請求項に記述された以外の要素又はステップの存在を排除するものではない。要素に先行する冠詞「ａ」又は「ａｎ」は、複数のそのような要素の存在を排除するものではない。本発明は、いくつかの個別の素子を含むハードウェアによって、及び適切にプログラムされたコンピュータによって実装される。いくつかの手段を列挙したデバイスの請求項において、これらの手段のいくつかは、同一のハードウェア項目によって具現化される。特定の対策が相異なる従属請求項に列挙されているという単なる事実は、これらの対策の組合せが有利に使用できないことを示すものではない。
【０１２３】
特許請求の範囲において、括弧内の参照は、実施形態の図面における参照符号又は実施形態の式を参照して、請求項の明瞭性を高めている。これらの参照は請求項を限定するものとして解釈されるべきではない。
【図１】
2019504343.tif 000069
【図２ａ】
2019504343.tif 000070
【図２ｂ】
2019504343.tif 000071
【図２ｃ】
2019504343.tif 000072
【図２ｄ】
2019504343.tif 000073
【図２ｅ】
2019504343.tif 000074
【図３】
2019504343.tif 000075
【図４ａ】
2019504343.tif 000076
【図４ｂ】
2019504343.tif 000077
【図５ａ】
2019504343.tif 000078
【図５ｂ】
2019504343.tif 000079
【図６ａ】
2019504343.tif 000080
【図６ｂ】
2019504343.tif 000081
【図７ａ】
2019504343.tif 000082
【図７ｂ】
2019504343.tif 000083
【国際調査報告】
2019504343.tif 000084
2019504343.tif 000085
2019504343.tif 000086