(57)【要約】デジタル情報を変換する工程を含む、暗号操作を実行する方法が開示される。デジタルオペレータは、多数のエレメントのセットから選択される要素を有することが提供される。要素は、複数のファクタに拡張され、各ファクタは低いハミングウエイトを有する。デジタル情報は、デジタルオペレータを用いて変換される。コンピュータ読み出し可能媒体は、本方法のための命令を実施する。デジタル情報を変換する工程を含む暗号操作を実行する方法は、デジタル情報を提供する工程と、多くのエレメントのセットから選択された要素を有するデジタルオペレータを提供する工程と、複数のファクタに要素を拡張する工程であって、各ファクタは低いハミングウエイトを有する、工程と、該デジタルオペレータを用いてデジタル情報を変換する工程とを包含する。【特許請求の範囲】
【請求項１】
デジタル情報を変換する工程を含む暗号操作を実行する方法であって、該方法は、
デジタル情報を提供する工程と、
多くのエレメントのセットから選択された要素を有するデジタルオペレータを提供する工程と、
複数のファクタに要素を拡張する工程であって、各ファクタは低いハミングウエイトを有する、工程と、
該デジタルオペレータを用いて該デジタル情報を変換する工程と
を包含する、方法。
【請求項２】
前記暗号操作は、キー生成、暗号化、復号化、デジタル署名の生成、デジタル署名の照合、デジタル認証の生成、デジタル認証の確認、識別、擬似ランダム数の生成、およびハッシュ関数の計算からなる群から選択される、請求項１に記載の方法。
【請求項３】
前記ハミングウエイトは約３０よりも小さい、請求項１に記載の方法。
【請求項４】
前記ハミングウエイトは約２０よりも小さい、請求項１に記載の方法。
【請求項５】
前記ハミングウエイトは約１５よりも小さい、請求項１に記載の方法。
【請求項６】
前記変換する工程は、倍数を計算する工程を含む方法であって、該方法は、
環Ｒを選択する工程と、
Ｒ−加群Ｍを選択する工程と、
ｒ１がＲ１のエレメントであり、ｒ２がＲ２のエレメントであり、．．．、ｒｋがＲｋのエレメントであるという特性を用いてＲの２つ以上のサブセットＲ１、Ｒ２、．．．、Ｒｋはを選択する工程と、
ｒ＊ｍを計算する工程であって、ｒ１＊ｒ２＊．．．ｒｋとしてｒを拡張することによってｒはＲになり、ｍはＭになり、ｋは整数であり、該量ｒ１＊（ｒ２＊．．．（ｒｋ＊ｍ）を計算する、工程と
をさらに包含する、請求項１に記載の方法。
【請求項７】
前記暗号操作は、キー生成、暗号化、復号化、デジタル署名の生成、デジタル署名の照合、デジタル認証の生成、デジタル認証の確認、識別、擬似ランダム数の生成、およびハッシュ関数の計算からなる群から選択される、請求項６に記載の方法。
【請求項８】
各ｒｋは、約１５より小さいハミングウエイトを有する、請求項６に記載の方法。
【請求項９】
各ｒｋは、約１０より小さいハミングウエイトを有する、請求項６に記載の方法。
【請求項１０】
前記サブセットＲｉは、式ａ１ｔｅ（１）＋ａ２ｔｅ（２）＋．．．＋ａｎｔｅ（ｎ）のエレメントからなるＲのサブセットであり、ｎは整数である、請求項６に記載の方法。
【請求項１１】
各前記エレメントａ１、．．．、ａｎは、前記セット｛０，１｝から選択される、請求項１０に記載の方法。
【請求項１２】
各前記エレメントａ１、．．．、ａｎは、前記セット｛−１，０，１｝から選択される、請求項１０に記載の方法。
【請求項１３】
前記サブセットＲｉは、ＲのサブセットＡから取られた係数ａ１、．．．、ａｋを有するＲのエレメントｔ１、．．．、ｔｋの多項式からなるＲのサブセットである、請求項６に記載の方法。
【請求項１４】
各前記係数ａ１、．．．、ａｋは、前記セット｛０，１｝から選択される、請求項１３に記載の方法。
【請求項１５】
各前記係数ａ１、．．．、ａｋは、前記セット｛−１，０，１｝から選択される、請求項１３に記載の方法。
【請求項１６】
前記環Ｒは整数の環であり、前記Ｒ−加群Ｍは、ｐｍエレメントを有するフィールドＧＦ（ｐｍ）の非ゼロエレメントの群であり、前記サブセットＲ１、．．．、Ｒｋは、式ａ１ｐｅ（１）＋ａ２ｐｅ（２）＋．．．＋ａｎｐｅ（ｎ）の整数からなり、ここでｎはｍより小さい整数であり、ａ１、．．．、ａｎは前記セット｛０，１｝のエレメントである、請求項６に記載の方法。
【請求項１７】
前記環Ｒは整数の環であり、前記Ｒ−加群Ｍは、ｐｍエレメントを有するフィールドＧＦ（ｐｍ）の非ゼロエレメントの群であり、前記サブセットＲ１、．．．、Ｒｋは、式ａ１ｐｅ（１）＋ａ２ｐｅ（２）＋．．．＋ａｎｐｅ（ｎ）の整数からなり、ここでｎはｍより小さい整数であり、ａ１、．．．、ａｎは整数Ａの小さいセットのエレメントである、請求項６に記載の方法。
【請求項１８】
前記環Ｒは、有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群の自己準同形環である、請求項６に記載の方法。
【請求項１９】
前記加群Ｍは、有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群である、請求項６に記載の方法。
【請求項２０】
前記環Ｒは、特徴ｐの有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群の自己準同形環であり、前記加群Ｍは点Ｅ（ＧＦ（ｑ））の群であり、前記エレメントｔは、ｐのべき乗のフロベニウスマップである、請求項１０に記載の方法。
【請求項２１】
前記環Ｒは、特徴ｐの有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群の自己準同形環であり、前記加群Ｍは点Ｅ（ＧＦ（ｑ））の群であり、前記エレメントｔは、マップを有する点である、請求項１０に記載の方法。
【請求項２２】
前記環Ｒは、多項式法のイデアルＡ［Ｘ］／Ｉの環であり、Ａは環であり、ＩはＡ［Ｘ］のイデアルであり、ここでサブセットＲ１、．．．、Ｒｋは、少数の非ゼロ項を有する多項式のセットである、請求項６に記載の方法。
【請求項２３】
前記イデアルＩは、多項式ＸＮ−１によって生成されたイデアルである、請求項２２に記載の方法。
【請求項２４】
前記環Ａは、整数モジューロのｑの有限の環Ｚ／ｑＺであり、ｑは正の整数である、請求項２２に記載の方法。
【請求項２５】
前記環Ｒは、イデアルＡ［Ｘ］／Ｉを法とする多項式の環であり、Ａは環であり、ＩはＡ［Ｘ］のイデアルであり、前記エレメントｔはＲの多項式Ｘである、請求項１０に記載の方法。
【請求項２６】
前記イデアルＩは、前記多項式ＸＮ−１によって生成されたイデアルである、請求項２５に記載の方法。
【請求項２７】
前記環Ａは整数モジューロのｑの有限環Ｚ／ｑＺである、請求項２５に記載の方法。
【請求項２８】
コンピュータ読み出し可能媒体は、デジタル情報を変換する工程を含む暗号操作を実行するための方法のための命令を含むコンピュータ読み出し可能媒体であって、該方法は、
デジタル情報を提供する工程と、
多数のエレメントのセットから選択される要素を有するデジタルオペレータを提供する工程と、
複数のファクタに該要素を拡張する工程であって、各ファクタは低いハミングウエイトを有する、工程と、
該デジタルオペレータを用いて該デジタル情報を変換する工程と
を包含する、コンピュータ読み出し可能媒体。
【請求項２９】
環Ｒを選択する工程と、
Ｒ−加群Ｍを選択する工程と、
ｒ１がＲ１のエレメントであり、ｒ２がＲ２のエレメントであり、．．．、ｒｋがＲｋのエレメントであるという特性を用いてＲの２つ以上のサブセットＲ１、Ｒ２、．．．、Ｒｋはを選択する工程と、
ｒ＊ｍを計算する工程であって、ｒ１＊ｒ２＊．．．ｒｋとしてｒを拡張することによってｒはＲになり、ｋは整数であり、該量ｒ１＊（ｒ２＊．．．（ｒｋ＊ｍ）を計算する、工程と
をさらに包含する方法のための命令を含む、請求項２８に記載のコンピュータ読み出し可能媒体。
【請求項３０】
前記サブセットＲｉは、式ａ１ｔｅ（１）＋ａ２ｔｅ（２）＋．．．＋ａｎｔｅ（ｎ）のエレメントからなるＲのサブセットであり、ｎは整数である、方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３１】
前記サブセットＲｉは、ＲのサブセットＡから得られた係数ａ１、．．．、ａｋを有するＲのエレメントｔ１、．．．、ｔｋの多項式からなるＲのサブセットである、方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３２】
前記環Ｒは整数の環であり、前記Ｒ−加群は、ｐｍエレメントを有するフィールドＧＦ（ｐｍ）の非ゼロエレメントの群であり、前記サブセットＲ１、．．．、Ｒｋは、式ａ１ｐｅ（１）＋ａ２ｐｅ（２）＋．．．＋ａｎｐｅ（ｎ）の整数からなり、ここでｎはｍより小さい整数であり、ａ１、．．．、ａｎは前記セット｛０，１｝のエレメントである、方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３３】
前記環Ｒは整数の環であり、前記Ｒ−加群Ｍは、ｐｍエレメントを有するフィールドＧＦ（ｐｍ）の非ゼロエレメントの群であり、前記サブセットＲ１、．．．、Ｒｋは、式ａ１ｐｅ（１）＋ａ２ｐｅ（２）＋．．．＋ａｎｐｅ（ｎ）の整数からなり、ここでｎはｍより小さい整数であり、ａ１、．．．、ａｎは整数Ａの小さいセットのエレメントである、方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３４】
前記環Ｒは、有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群の自己準同形環である方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３５】
前記加群Ｍは、有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群である方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３６】
前記環Ｒは、特徴ｐの有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群の自己準同形環であり、前記加群Ｍは点Ｅ（ＧＦ（ｑ））の群であり、前記エレメントｔは、ｐのべき乗のフロベニウスマップである、方法のための命令を含む、請求項３０に記載のコンピュータ読み出し可能媒体。
【請求項３７】
前記環Ｒは、特徴ｐの有限のフィールドＧＦ（ｑ）を介して楕円カーブＥの点Ｅ（ＧＦ（ｑ））の群の自己準同形環であり、前記加群Ｍは点Ｅ（ＧＦ（ｑ））の群であり、前記エレメントｔは、マップを有する点である、方法のための命令を含む、請求項３０に記載のコンピュータ読み出し可能媒体。
【請求項３８】
前記環Ｒは、イデアルＡ［Ｘ］／Ｉを法とする多項式の環であり、Ａは環であり、ＩはＡ［Ｘ］のイデアルであり、ここでサブセットＲ１、．．．、Ｒｋは、少数の非ゼロ項を有する多項式のセットである、方法のための命令を含む、請求項２９に記載のコンピュータ読み出し可能媒体。
【請求項３９】
前記環Ｒは、多項式法のイデアルＡ［Ｘ］／Ｉの環であり、Ａは環であり、ＩはＡ［Ｘ］のイデアルであり、前記エレメントｔはＲの多項式Ｘである、方法のための命令を含む、請求項３０に記載のコンピュータ読み出し可能媒体。
【発明の詳細な説明】
【０００１】
（関連出願の相互参照）
この特許出願は、２０００年８月２９日に出願された米国仮出願第６０／２２８，５７２号からの優先権を主張する。
【０００２】
（発明の分野）
本発明は、概して、例えば、キー生成、暗号化、復号化、確認、識別、およびデジタル署名等の暗号目的に有用な数量のべき乗および乗算を効率良く計算する方法および装置に関する。
【０００３】
（発明の背景）
現代の暗号化方法は、相当数の基本的な数学操作（加算、減算、乗算、除算、剰余、桁送り、および論理的な「ａｎｄ」、「ｏｒ」および「ｘｏｒ」等）を必要とする。これら方法の多くは、正の値の大きなセットからランダムに選択された値ｋのべき乗Ａｋ（個々にｋ＊Ａを乗算する）の計算を必要とする。
【０００４】
これまで、種々の方法が、条件として指定された値であるｋに対してべき乗Ａｋ（個々にｋ＊Ａを乗算する）を計算するために提案され、実行されている（Ｈ．Ｃｏｈｅｎの「Ａ　Ｃｏｕｒｓｅ　ｉｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｎｕｍｂｅｒ　Ｔｈｅｏｒｙ」，ＧＴＭ１３８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９３（Ｓｅｃｔｉｏｎ１．２））、（Ｄ．Ｇｏｒｄｏｎの「Ａ　ｓｕｒｖｅｙ　ｏｆ　ｆａｓｔ　ｅｘｐｏｎｅｎｔｉａｔｉｏｎ　ｍｅｔｈｏｄｓ」，Ｊｏｕｒｎａｌ　ｏｆ　Ａｌｇｏｒｉｔｈｍｓ２７（１９９８），１２９−１４６），（Ｄ．Ｋｎｕｔｈの「Ｔｈｅ　Ａｒｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ」，Ｖｏｌｕｍｅ２，Ｓｅｍｉｎｕｍｅｒｉｃａｌ　Ａｌｇｏｒｉｔｈｍｓ，３ｒｄ　ｅｄ．，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，１９９８（Ｓｅｃｔｉｏｎ６．４．３）），（Ａ．Ｊ．Ｍｅｎｅｚｅｎらの「Ｈａｎｄｂｏｏｋ　ｏｆ　Ａｐｐｌｉｅｄ　Ｃｒｙｐｔｏｇｒａｐｈｙ」，ＣＲＣ　Ｐｒｅｓｓ，１９９７（Ｓｅｃｔｉｏｎ１４．６）
用いられている迅速な計算方法の一つの種類は、ｋを２のべき乗の合計として書き込み、計算を乗算およびスクウェアリング（それぞれ、加算および二倍化）に低減することである。
【０００５】
用いられている迅速な計算方法の第二の種類は、ｋをプラスおよびマイナスの２のべき乗の合計として書き込み、乗算、反転、および二乗計算（それぞれ、加算、減算、およびスクウェアリング（ｓｑｕａｒｉｎｇ））に計算を低減することである。
【０００６】
用いられている迅速な計算方法の第三の種類は、ｋを２のべき乗の小さい乗算の合計として書き込み、乗算、小さいべき乗、およびスクウェアリング（それぞれ、加算、減算、小さい乗算、および二倍化）に計算を低減することである。
【０００７】
用いられている迅速な計算方法の第四の種類は、ｋを特別の乗算ｔのべき乗の合計（ここで、ｔは、ｔ乗への上昇（それぞれｔによって乗算する）が、乗算（それぞれ、加算または減算）に比較してほとんど時間を要しないプロパティを有する）として書き込むことである。この方法の特定の例は、有限領域（ｆｉｎｉｔｅ　ｆｉｅｌｄ）ＧＦ（ｐ）を介して規定される楕円曲線Ｅ上のポイントＥ（ＧＦ（ｐｍ））の群に関するｐ乗フロベニウスマップのべき乗の合計としてｋを書き込むことである。
【０００８】
用いられている迅速な計算方法の第五の種類（ファクタ法（Ｋｎｕｔｈの「ｓｕｐｒａ」，Ｓｅｃｔｉｏｎ４．６．３，４６３ページおよびｅｘｅｒｃｉｓｅ３）と呼ばれる）は、所与の整数ｋを、前述の方法の一つを用いてそれ自体書き込まれるファクタの積として書き込むことである。
【０００９】
これらの方法のすべては、ｋの全てまたは大抵の値に対するべき乗Ａｋ（または乗算ｋ＊Ａ）の道理に合った迅速な計算を可能にするが、多くのユーザーは、許容できる値の十分な大きさのセットから得られるｋによるべき乗Ａｋ（または乗算ｋ＊Ａ）のさらにより迅速な計算ができる方法を有することが望ましいことを見出す。
【００１０】
（発明の要旨）
多くの暗号操作において、グループまたは環内のエレメントのランダムなべき乗または乗算を用いる。本発明は、デジタル情報を変換するための方法、システムおよび装置を提供する。このデジタル情報は、ある種の重要な状況におけるべき乗および乗算を計算するために早い方法を用いる。この状況は、例えば、ガロア域Ｆ２ｎにおけるべき乗、Ｋｏｂｌｉｔｚ楕円曲線上の乗算、ＮＴＲＵ重畳多項式環内の乗算その他を含む。本発明によると、例えば、指数または乗算は、ある早い操作のべき乗の合計として展開される。これは、例えば、キー生成、暗号化、復号化、デジタル署名の作成、デジタル署名の照合、デジタル認証の作成、デジタル認証の確認、識別、擬似ランダムな数の生成およびハッシュ関数の計算その他を含む多くの暗号操作、特に、ランダムな指数または乗算が利用される場合の操作に有用である。
【００１１】
したがって、本発明は、エレメントの大きなセットから選択された要素を有するデジタルオペレータで操作することによってデジタル情報を変換するステップであって、この要素は低いハミングウエイト（Ｈｕｍｍｉｎｇ　ｗｅｉｇｈｔ）を有する、ステップを含む暗号操作を行うための方法、システムおよび装置を提供する。典型的には、要素は、約３０未満、好適には、約２９未満、より好適には、約１５未満、最も好適には、約１０未満のハミングウエイトを有するように選択される。好適には、デジタルオペレータは、複数のファクタを有する要素を含み、各ファクタは、低いハミングウエイトを有する。本発明による一つ以上の要素を有するデジタルオペレータを用いることによって、変換するステップは、従来技術のエレメントを用いる変換するステップと比較して増加された速度で行われ得る。本発明による要素は、ファクタの積として形成され、ファクタのそれぞれは、ある種の早い操作のべき乗の合計として展開された場合に（例えば、ｃｐｕ、マイクロプロセッサまたはコンピュータ等の適切な計算デバイスによって行われるときに）低いハミングウエイトを有する。
【００１２】
本発明により、べき乗Ａｋ（または乗算ｋ＊Ａ）は、可能なエレメントのより大きなセットから選択されたｋにより非常に迅速に計算され得る。本発明の方法による計算は、典型的には、現在の使用に最も広く用いられる方法よりも相当早い。
【００１３】
本発明の一実施形態において、指数要素（または乗算されたエレメントを有する要素）のためのコンピュータ技術は、本方法の指数計算（または乗算計算）のスピードをあげるために、特別に選択されたエレメントの積を用いる。べき乗Ａｋ（１）ｋ（２）…ｋ（ｒ）（または乗算ｋ（１）ｋ（２）…ｋ（ｒ）＊Ａ）を計算するコンピュータの複雑さは、べき乗Ａ１ｋ（１），…，Ａｒｋ（ｒ）（または乗算ｋ（１）＊Ａ１，…，ｋ（ｒ）＊Ａｒ）を計算するコンピュータ上の複雑さの合計に比例するが、可能なべき乗（または乗算）の数は、ｋ（１），…，ｋ（ｒ）に対する許容された値の数の積にほぼ等しい。コンピュータ上の複雑さが個々のコンピュータ上の複雑さの合計に比例して増加するが、可能な値であるＡｋ（それぞれｋ＊Ａ）のセットのサイズは、ｋ（１），…，ｋ（ｒ）に対する許容された値の数の積に比例して増加するという事実は、なぜ本発明が向上されたコンピュータ上の方法を提供するかを説明するために助けとなる。本方法は、べき乗Ａｔ（または乗算ｔ＊Ａ）が迅速に計算され得るエレメントがある状況に特に効果的である。好適には、ｋ（１），…，ｋ（ｒ）は、エレメントｔにおいて低いハミングウエイトの多項式であるように選択される。
【００１４】
本発明は、さらに、本発明の上記方法を行うための命令を含むコンピュータ読み出し可能な媒体を提供する。
【００１５】
（定義）
以下の定義が、本発明を記載するという目的のために用いられる。コンピュータ読み出し可能な媒体は、コンピュータによって読み出され得るデータまたはコンピュータによって読み出され得るデータを搬送する搬送波信号によって読み出され得るデータを含む製品の任意のものを意味することが理解される。このようなコンピュータ読み出し可能な媒体は、フロッピー（Ｒ）ディスク、フレキシブルディスク、ハードディスク、オープンリール式テープ、カートリッジテープ、カセットテープまたはカード等の磁気メディアか、ＣＤ−ＲＯＭおよび書き込み可能なコンパクトディスク等の光メディアか、ディスク、テープまたはカード形状内の磁気光学メディアか、パンチングされたカードおよび紙テープ等の紙媒体か、または無線周波数信号および赤外信号を含みネットワーク、ワイヤレスネットワークまたはモデムを通じて受信された搬送波信号を含む。
【００１６】
本明細書において用いられる用語「大きなセット（ｌａｒｇｅ　ｓｅｔ）」は、所定の時間または操作の所定の最少数未満内で、誰かがチェックすることを防止するために十分大きいエレメントのセットを意味し、そのエレメントのセットは、暗号操作中に用いられるセットにおいてランダムに選択されたエレメントを発見する。時間が長くなる程、または、選択されたエレメントを発見するために要求される操作の最少数が大きくなる程、暗号操作はより安全になる。
【００１７】
（発明の詳細な説明）
ランダムなべき乗Ａｋまたはランダムな乗算ｋ＊Ａを必要とする多くの暗号化方法がある。ここで、ｋは環Ｒのエレメントであり、ＡはＲ−加群Ｍのエレメントである。このようなランダムなべき乗または乗算を要求する例示的な方法は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎキー交換（米国特許第４，２００，７７０号）、（Ｍｅｎｅｚｅｓの「ｓｕｐｒａ」、ｓｅｃｔｉｏｎ１２．６．１）、ＥｌＧａｍａｌ公共キー暗号作成法（Ｍｅｎｅｚｅｓの［ｓｕｐｒａ」、ｓｅｃｔｉｏｎ８．４）、デジタル署名標準（ＤＳＳ）（米国特許第５，２３１，６６８号）、（Ｍｅｎｅｚｅｓの「ｓｕｐｒａ」、ｓｅｃｔｉｏｎ１１．５．１），ＮＴＲＵ（Ｒ）公共キー暗号化（米国特許第６，０８１，５９７号）、（Ｊ．Ｈｏｆｆｓｔｅｉｎらの「ＮＴＲＵ：Ａ　ｎｅｗ　ｈｉｇｈ　ｓｐｅｅｄ　ｐｕｂｌｉｃ　ｋｅｙ　ｃｒｙｐｔｏｓｙｓｔｅｍ，ｉｎ　Ａｌｇｏｒｉｔｈｍｉｃ　Ｎｕｍｂｅｒ　Ｔｈｅｏｒｙ（ＡＮＴＳ　ＩＩＩ）」，Ｐｏｒｔｌａｎｄ，ＯＲ，Ｊｕｎｅ　１９９８，Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　１４２３（Ｊ．Ｐ．Ｂｕｈｌｅｒ，ｅｄ）、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，Ｂｅｒｌｉｎ，１９９８，２６７−２８８）、およびＮＴＲＵ（Ｒ）署名スキーム（ＮＳＳ）（Ｊ．Ｈｏｆｆｓｔｅｉｎらの「ＮＳＳ：Ｔｈｅ　ＮＴＲＵ　Ｓｉｇｎａｔｕｒｅ　Ｓｃｈｅｍｅ，Ｐｒｏｃ．ＥＵＲＯＣＲＹＰＴ２００１，Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１）。
【００１８】
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ、ＥｌＧａｍａｌ、およびＤＢＢの一つの変数は、整数の環Ｒ＝Ｚおよび有限域の０でないエレメントのＲ−加群Ｍ＝ＧＦ（ｐｍ）＊を用いる。Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ、ＥｌＧａｍａｌ、およびＤＳＳの第２の変数は、交換可能な変数Ａの自己準同形環Ｒ＝Ｅｎｄ（Ａ）および有限域上で規定されるＡ上の点のＲ−加群Ｍ＝Ａ（ＧＦ（ｐｍ））を用いる。この変数の例は、有限域ＧＦ（ｐ）上で規定される楕円曲線Ａ＝ＥおよびＺを含む自己準同形環およびＥ（ＧＦ（ｐｍ）上のｐのべき乗フロベニウスマップである。ＮＴＲＵ公共キー暗号化およびＮＴＲＵ署名スキームは、イデアルＩを法とした環Ｂにおける係数を有する多項式の環Ｒ＝Ｂ〔Ｘ〕／ＩおよびＲ加群Ｍ＝Ｒを用いる。ＮＴＲＵの例は、重畳環Ｒ＝（Ｚ／ｑＺ）［Ｘ］／（ＸＮ−１）を用いる。
【００１９】
本発明の方法は、数量ｋを式
ｋ＝ｋ（１）＊ｋ（１）＊．．．＊ｋ（ｒ）
の環Ｒのエレメントのセットから選択するステップを含む。ここで、べき乗Ａｋ（ｉ）（または乗算ｋ（ｉ）＊Ａ）の計算は、Ｒ−加群ＭのすべてのエレメントＡに対して計算が速く、べき乗Ａｋ（または乗算ｋ＊Ａ）をステップ
Ａ１＝Ａｋ（１）、Ａ２＝Ａｋ（２）、．．．、Ａｋ＝Ａｒ＝Ａｒ−１ｋ（ｒ）のシーケンスとして計算することである（それぞれ、ステップの配列としてＡ１＝ｋ（１）＊Ａ、Ａ２＝ｋ（２）＊Ａ１、．．．、Ａｒ＝ｋ（ｒ）Ａｒ−１である）。
【００２０】
本発明の一実施形態において、環Ｒは、エレメントｔを含み、その結果、べき乗Ａｔ（それぞれ乗算ｔ＊Ａ）の計算は、Ｒ−加群ＭのすべてのエレメントＡに対して計算が速い。このことの例は、下記を含む。
【００２１】
（１）有限域Ｍ＝ＧＦ（ｐｍ）＊の乗算群およびｐ番目のべき乗、ｔ（ｘ）＝ｘｐへの上昇に対応するエレメントｔ＝ｐ
（２）有限域ＧＦ（ｐ）上で規定される楕円曲線Ｅ、Ｅの点Ｍ＝Ｅ（ＧＦ（ｐｍ））の群、およびｔ（ｘ，ｙ）＝（ｘｐ、ｙｐ）によって規定されるｐ番目のべき乗フロベニウスエレメントであるエレメントｔ
（３）重畳多項式Ｒ＝Ｍ＝（Ｚ／ｑＺ）［Ｘ］／（ＸＮ−１）の環および環Ｒ，ｔ（ｆ（Ｘ））＝Ｘ＊ｆ（Ｘ）におけるＸによる乗算に対応するエレメントｔ＝Ｘ
環Ｒがこのようなエレメントｔを含む例において、エレメントｋ（ｉ）は、好適には、ｔにおける下記の多項式であるように選択される。
ａ０＋ａ１＊ｔ＋ａ２＊ｔ２＋．．．＋ａｎ＊ｔｎ
ここで、係数ａ０，・・・，ａｎは、制限されたセットから選択される。ａ０，．．．ａｎに対する例示の選択は、セット｛０，１｝および｛−１，０，１｝である。後者は、主として反転（または否定）が計算的にＭ状態の速い操作である場合に有用である。
【００２２】
本発明の効果は、多項式
ＨＷ（ａ０＋ａ１＊ｔ＋ａ２＊ｔ２＋．．．＋ａｎ＊ｔｎ）＝非ゼロのａｉの番号
のハミングウエイトによって測定され得る。
Ａｔ（またはｔ＊Ａ）の計算は、ごくわずかな時間を要するため、ｋ（ｉ）＝ａ０＋ａ１＊ｔ＋・・・＋ａｎ＊ｔｎに対してＡｋ（ｉ）（またはｋ（ｉ）＊Ａ）を計算するための時間は、大体、それぞれ、
ＴｉｍｅＴｏＣｏｍｐｕｔｅ（Ａｋ（ｉ））≒ＨＷ（ｋ（ｉ））乗算
ＴｉｍｅＴｏＣｏｍｐｕｔｅ（ｋ（ｉ）＊Ａ）≒ＨＷ（ｋ（ｉ））加算
のようになる。このため、式ｋ＝ｋ（１）＊ｋ（２）＊・・・＊ｋ（ｒ）内のｋを選択する方法は、Ａｋ（またはｋ＊Ａ）の計算を可能にし、大体それぞれ
ＴｉｍｅＴｏＣｏｍｐｕｔｅ（Ａｋ）≒ＨＷ（ｋ（１））＋．．．＋ＨＷ（ｋ（ｒ））＋ｒ−１乗算
ＴｉｍｅＴｏＣｏｍｐｕｔｅ（ｋ＊Ａ）≒ＨＷ（ｋ（１））＋．．．＋ＨＷ（ｋ（ｒ））＋ｒ−１加算
のようになる。このため、Ａｋ（また、ｋ＊Ａ）を計算するための計算上の効果は、数量ｋ（１），．．．，ｋ（ｒ）のハミングウエイトの合計にほぼ比例する。
【００２３】
多項式の係数ａ０，．．．，ａｎが例示のセット｛０，１｝から選択される場合および数量ｋ（１），．．．，ｋ（ｒ）がハミングウエイトｄ１，．．．，ｄｒを有するように選択される場合、それぞれ、ｒ個の要素からなる（ｋ（１），．．．，ｋ（ｒ））の数は、
Ｃ（ｎ＋１，ｄ１）＊Ｃ（ｎ＋１，ｄ２）＊．．．＊Ｃ（ｎ＋１，ｄｒ）
のようになる。ここで、Ｃ（ｎ，ｄ）＝ｎ！／ｄ！＊（ｎ−ｄ）！は、組み合わせの記号である。このため、ｒ個の要素からなる（ｋ（１），．．．，ｋ（ｒ））の数は、各ｋ（ｉ）に対する個々の値の数の積である。さらに、多くの例示的な状況において、経験は、積Ｃ（ｎ＋１，ｄ１）＊．．．＊Ｃ（ｎ＋１，ｄｒ）が環Ｒにおけるエレメントの数より小さくなるように選択される場合、大抵の積ｋ（１）＊．．．＊ｋ（ｒ）が明瞭であることを示す。したがって、ランダムなべき乗Ａｋ（または、乗算ｋ＊Ａ）は、Ｒの大きいサブセットにおけるすべてのｋに対して効果的に計算され得る。サブセットの特定のサイズは、パラメータｒおよびｄ１，．．．，ｄｒ等のパラメータの適切な選択によって調整され得る。
【００２４】
記載された実施形態の一般化は、いくつかのエレメントｔ１，．．．ｔｚを含む環Ｒであり、その結果、べき乗Ａｔ（または乗算ｔ＊Ａ）の計算は、各ｔ＝ｔ１，．．．，ｔｚに対しておよびＲ−加群ＭのすべてのエレメントＡに対して計算上速く、エレメントｋ（ｉ）は、ｔ１，．．．，ｔｚにおける多項式になるように選択される。記載された実施形態の別の一般化は、エレメント
ｋ＝ｋ１（１）＊．．．＊ｋ１（ｒ１）＋ｋ２（１）＊．．．＊ｋ２（ｒ２）＋．．．＋ｋｗ（１）＊．．．＊ｋｗ（ｒｗ）
の選択である。これは、以前に記載されたソートｋ（ｉ）のエレメントｋｊ（ｉ）の積の合計である。さらなる一般化が当業者にすぐに明らかになる。
【００２５】
本発明による速度が増加された暗号化技術のさらなる詳細が以下の例において記載される。
【００２６】
群または環のエレメントのランダムなべき乗または乗算を用いる多くの暗号化構成がある。簡単で、かつ完全には遠いリストは、以下を含む。
【００２７】
１．Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ
有限域Ｆにおけるエレメントｇをとり、Ｆにおけるランダムなべき乗ｇｋ計算する。ここで、ｋは整数である。
【００２８】
２．楕円曲線ＤＨ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ
有限域上の楕円曲線上の点の群Ｅ（Ｆ）における点Ｐをとり、ランダムな乗算ｋＰを計算する。ここで、ｋは整数または群Ｅ（Ｆ）のより一般的な自己準同形であり得る。
【００２９】
３．ＤＳＳおよびＥＣＤＳＳ
デジタル署名標準（有限域または楕円曲線を用いる）は、アルゴリズムの記号部分においてランダムなべき乗ｇｋまたは乗算ｋＰを必要とする。確認プロセスは、さらに、特定のｋの値に対してであるが、ランダムな値に対してではない、べき乗または乗算を必要とする。
【００３０】
４．古典的ＥｌＧａｍａｌ　公共キー暗号化
ＥｌＧａｍａｌキー生成は、秘密のキーを形成する、固定されたベースαおよびランダムに選択された指数ｊを有するべき乗β＝αｊの計算を必要とする。暗号化は、二つのべき乗αｋおよびβｋの計算をランダムに選択された指数ｋに必要とする。複号化は、べき乗γｊの計算を必要とする。
【００３１】
５．楕円曲線ＥｌＧａｍａｌおよび変数
キー生成は、秘密のキーを形成する、Ｅ（Ｐ）における固定された点Ｐおよびランダムに選択された乗算ｊを有する乗算Ｑ＝ｊＰの計算を必要とする。暗号化は、二つの乗算ｋＰおよびｋＱの計算をランダムに選択された乗算ｋに必要とする。復号化は、乗算ｊＲの計算を必要とする。再度、ｋは整数または群Ｅ（Ｆ）のより一般的な自己準同形であり得る。
【００３２】
６．ＮＴＲＵ公共キー暗号化システム
プライベートキーは、先端を切った多項式モジューロｑの環Ｒｑ＝（Ｚ／ｑＺ）［Ｘ］／（ＸＮ−１）におけるランダムな多項式ｆ（Ｘ）を含む。符号化は、環Ｒにおける積ｒ（Ｘ）ｈ（Ｘ）の計算を必要とする。ここで、ｈ（Ｘ）（公共キー）は固定され、ｒ（Ｘ）はランダムである。復号化は、環Ｒにおける積ｆ（Ｘ）ｅ（Ｘ）の計算を必要とする。ここで、ｅ（Ｘ）は、暗号文である。
【００３３】
本発明の一実施形態によると、多くの状況においてランダムな乗算が、前述の方法より迅速に計算されることが可能な一般的な方法が記載されている。普遍的に応用することはできないが、それは、ガロア域Ｆ２ｎ上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ、Ｋｏｂｌｉｔｚ曲線上の楕円曲線暗号化、およびＮＴＲＵ暗号化を含む、上記リストにおけるアルゴリズムの多くに用いられ得る。本発明によると、ランダムな指数または乗算は、ファクタの積として形成され、ファクタのそれぞれは、ある速い操作のべき乗の合計として展開された場合に低いハミングウエイトを有する。
【００３４】
簡単に、本発明によると、ランダムな乗算は、項の積として書き込まれ、項のそれぞれは、簡単に計算される項の合計である。これらの乗算は、小さいハミングウエイト積（ＳＨＷＰ）と呼ばれる。なぜなら、積における各項は、簡単に計算される操作に比較して低いハミングウエイトを有するからである。
【００３５】
（低いハミングウエイト指数）
低いハミングウエイト指数の使用は、ＲＳＡ指数関数（Ｃ．Ｈ．Ｌｉｍらの「Ｓｐａｒｓａ　ＲＳＡ　ｋｅｙｓ　ａｎｄ　ｔｈｅｉｒ　ｇｅｎｅｒａｔｉｏｎ，ｐｒｅｐｒｉｎｔ，２０００）および離散対数アルゴリズム（Ｄ．Ｃｏｐｐｅｒｓｍｉｔｈらの「Ｏｎ　ｔｈｅ　Ｍｉｎｉｍｕｍ　Ｄｉｓｔａｎｃｅ　ｏｆ　Ｓｏｍｅ　Ｑｕａｄｒａｔｉｃ　Ｒｅｓｉｄｕｅ　Ｃｏｄｅｓ，ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，ｖｏｌ．ＩＴ−３０，Ｎｏ．２，Ｍａｒｃｈ　１９８４，４０７−４１１；Ｄ．Ｒ．Ｓｔｉｎｓｏｎの「Ｓｏｍｅ　ｂａｂｙ−ｓｔｅｐ　ｇｉａｎｔ−ｓｔｅｐ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅ　ｌｏｗ　Ｈａｍｍｉｎｇ　ｗｅｉｇｈｔ　ｄｉｓｃｒｅｔｅ　ｌｏｇａｒｉｔｈｍ　ｐｒｏｂｌｅｍ，Ｍａｔｈｅｍａｔｉｃｓ　ｏｆ　Ｃｏｍｐｕｔａｔｉｏｎ，ｔｏ　ｂｅ　ｐｕｂｌｉｓｈｅｄ」）の両方において研究されているが、常時、小さいハミングウエイトの単一の指数ｋを利用するコンテキストで研究されている。本発明は、非常に低いハミングウエイト指数の積ｋ＝ｋ１ｋ２・・・ｋｒを用い、積ｋのサンプルスペースはｋ１，・・・，ｋｒのためのサンプル空間の積前後である事実を利用し、一方で、αｋを計算する計算の複雑さ（ある種の状況において）は、計算αｉｋｉの計算上の複雑さの合計である。
【００３６】
ｘｋを計算するための有用なバイナリ方法は、ほぼｌｏｇ２ｋのスクウェアリングおよびＨＷ（ｋ）乗算を必要とする。ここで、
ＨＷ（ｋ）＝ｋのハミングウエイト
は、ｋのバイナリ指数における一つの数である。ｋのための加算鎖の使用は、しばしば、非常に大きな値ｋの向上を生ずるが、最適な鎖を見出すことは困難である。
【００３７】
ランダムなべき乗を、べき乗のリストを予め計算し、ランダムなサブセットの積を得、そして、中間計算を用いるリストを徐々に追加することによって計算するという考えは、Ｃ．Ｐ．Ｓｃｈｎｏｒｒによって「Ｅｆｆｉｃｉｅｎｔ　ｉｄｅｎｔｉｆｉｃａｔｉｏｎ　ａｎｄ　ｓｉｇｎａｔｕｒｅｓ　ｆｏｒ　ｓｍａｒｔ　ｃａｒｄｓ，ｉｎ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ（Ｃｒｙｐｔｏ８９），Ｓａｎｔａ　Ｂａｒｂａｒａ，ＣＡ，Ａｕｇｕｓｔ　１９８９，Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　４３５，（Ｇ．Ｂｒａｓｓａｒｄ編），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，Ｂｅｒｌｉｎ，１９８９，２３９−２５２」に記載されている。Ｓｃｈｎｏｒｒの方法は、ｄｅ　Ｒｏｏｉｊによって、Ｓｃｈｎｏｒｒ（Ｐ．ｄｅ　Ｒｏｏｉｊ，Ｏｎ　ｔｈｅ　ｓｅｃｕｒｉｔｙ　ｏｆ　ｔｈｅ　Ｓｃｈｎｏｒｒ　ｓｃｈｅｍｅ　ｕｓｉｎｇ　ｐｒｅｐｒｏｃｅｓｓｉｎｇ，ｉｎ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ（Ｅｕｒｏｃｒｙｐｔ９０），Ａａｒｈｕｓ，Ｄｅｎｍａｒｋ，Ｍａｙ　１９９０，Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ４７３（Ｉ．Ｂ．Ｄａｍｇａｒｄ編），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，Ｂｅｒｌｉｎ，１９９０，７１−８０）に提示されたパラメータレベルに分離される。
【００３８】
別の方法であるファクタ法は、Ｋｎｕｔｈ，ｓｕｐｒａ（４．６．３，４６３ページおよび練習３）によって簡単に議論される。
【００３９】
本発明は、多くの用途のためのこれらの従来技術の方法を超える向上を提供する。一実施形態において、例えば、ｋは積ｋ＝ｕｖであり、本実施形態において、ｚ＝ｘｋがｙ＝ｘｕおよびｚ＝ｙｖとして計算される。このプロセスは、繰り返され、バイナリ方法または他の加算鎖の使用とともに分散され得る。
【００４０】
本発明の別の実施形態を示すために、Ｇを数量ｘｋが計算される群にする。指数ｋを式（１）の積の合計として書き込むと仮定する。
【数１】
2004507789.tif 000002
ｘｋを積
【数２】
2004507789.tif 000003
として計算し、
【数３】
2004507789.tif 000004
を有するファクタ方法を用いて各べき乗ｘｋ（ｉ）を計算し、バイナリ法を用いることによって各べき乗ｙＫ（ｊ，ｎ）（Ｋ（ｉ，ｎ）＝Ｋｉ，ｎ）を計算する。これは、ほぼｌｏｇ２（ｋ）スクウェアリングおよびほぼ下記の式（２）を必要とする。
【数４】
2004507789.tif 000005
小さい値ｋに対して、式（２）を最小にした分解式（１）を求め得る。より大きい値ｋに対して、式（２）の道理に合った小さい値を生成するアルゴリズムを求め得る。しかしながら、それは、本発明の焦点ではない。
【００４１】
本発明の方法の目的および解析の両方は、Ｋｎｕｔｈ，ｓｕｐｒａに記載されているようなべき乗と著しく異なっている。Ｋｎｕｔｈにおける目的は、所与の指数ｋに対するｘｋを計算するための効果的な方法を記載することである。続く解析は、最も効果的な方法に対する理論的に上方および下方の境界および所与のｋを得て、リーゾナブルに効果的なｘｋを評価する手法を見出すためのアルゴリズムを与える。本発明の目的は、ｘｋが計算し易く、集合が十分に「ランダム」でかつ充分に大きいような指数ｋの集合を見出すことである。特定の指数からランダムな指数に見込まれるこの継ぎ目のない小さい変化は、実際に、基礎をなす疑問およびそれらを研究するために用いられる方法における主要なシフトを表わす。
【００４２】
本発明がＫｎｕｔｈに記載されたファクタ法と異なる第二の重要な手法がある。本発明は、「自由な」操作がある状況に向けられる。例を用いて、Ｇを群にし、ファクタ法を用いてｘｋを計算することが望まれることを仮定する。ここで、ｋ＝ｕｖである。ｘｋを計算する費用は、大体
（ｌｏｇ２（ｋ）スクウェアリング）＋（ＨＷ（ｕ）＋ＨＷ（ｖ）の乗算）
になる。ここで、簡単のため、二つのべき乗ｙ＝ｘｕおよびｚ＝ｙｖがバイナリ法を用いて計算されると仮定する。今、（有限）群ＧがオーダーＮを有すると仮定し、ｋが積モジューロＮ、例えば、ｋ＝ｕｖ（ｍｏｄＮ）として書き込まれると仮定する。ｙ＝ｘｕおよびｚ＝ｙｖが、正しい値ｚ＝ｘｋを与えるが、ここで、コスト（ｃｏｓｔ）は、大体
（ｌｏｇ２（ｕｖ）スクウェアリング）＋（ＨＷ（ｕ）＋ＨＷ（ｖ）の乗算）
のようになる。
【００４３】
スクウェアリングおよび乗算がほぼ同じ時間を利用する場合、この方法は、おそらく非常に悪い。なぜなら、積ｕｖは、非常に大きいからである。
【００４４】
他方、例えばガロア域Ｆ２ｎにおける場合のようにスクウェアリングが非常に速い場合、ｕおよびｖの大きい値は、ｕおよびｖが小さい（バイナリ）ハミングウエイトを有する限り利点があり得る。これは、例えば、暗号化の利益の三つの状況、すなわち、ガロア域Ｆ２ｎにおけるべき乗、Ｋｏｂｌｉｔｚ楕円曲線上の乗算、およびＮＴＲＵ重畳環Ｆｑ［Ｘ］／（ＸＮ−１）における乗算において示される。これらの特定の状況は、以下に詳細に記載される。また、以下に記載されるのは、小さいハミングウエイト積のランダムさを取り巻くいくつかの問題である。当業者は、多くの他の用途においてこの発明を実現し、利用し得る。
【００４５】
（ガロア域Ｆ２ｎのランダムべき乗）
任意の群では、べき乗αｋを計算する標準的な方法は、ｋのバイナリ拡張を使用することである。これは、αｋの計算を、ほぼｌｏｇ２（ｋ）スクウェアリング（ｓｑｕａｒｉｎｇ）およびＨＷ（ｋ）の倍数に低減し、平均してＨＷ（ｋ）は、ほぼ１／２ｌｏｇ２（ｋ）に等しい（ｋの符号化されたバイナリ拡張を使用することは、反転を犠牲にして倍数の数を低減する）。
【００４６】
バイナリべき乗アルゴリズムを任意の群に適用するが、本発明によって使用されるＦ２ｎの特徴は、スクウェアリングが乗算と比較して実質的に自由であるという事実である。従って、ｋが１〜２ｎ−１の間隔においてランダムに選択される場合，αｋの計算が、必要とされるほぼｎ／２回の乗算によって支配される。
【００４７】
上述のように、固定された基数αおよびいくつかのランダムに選択された指数ｋに対してαｋを計算することを必要とする多くの暗号状態が存在する。一般的には、要求は、完全な検索（またはより詳細には、Ｐｏｌｌａｒｄ’ｓ　ｒｈｏ法等の平方根検索）がｋを決定するために利用不可能である十分に多数のセットから選択されることである。従って、固定されたバイナリハミングウエイト
【数５】
2004507789.tif 000006
を用いて式
【数６】
2004507789.tif 000007
を有するようにｋを選択すると仮定する。次いで、ｋの検索空間の大きさは、Ｃ（ｎ，ｄ）である。典型的には、２１６０個の要素を有する検索空間を望む。なぜなら、典型的には、実行時間は、この空間の大きさの平方根に比例する。
【数７】
2004507789.tif 000008
にちょうど比例するこの空間を効率的に検索するＣｏｐｐｅｒｓｍｉｔｈ’ｓ　ｂａｂｙ−ｓｔｅｐ　ｇｉａｎｔ−ｓｔｅｐ　アルゴリズムの記述は、Ｓｔｉｎｓｏｎ、ｓｕｐｒａ、を参照のこと。
【００４８】
暗号目的のために、ｎの典型的な値はｎ≒１０００であり、この値は、ふるいの実行時間およびＦ２ｎにわたって、離散対数問題を解決するためのインデックス計算法によって決定される。次いで、ｄ＝２５とすることにより、Ｃ（１０００，２５）≒２１６５の大きさの検索空間を与え、αｋの計算は２４回の乗算を必要とする。
【００４９】
本発明による方法は、非常に低いバイナリハミングウエイトを有する項の積であるｋを選択することである（より詳細には、このような積の合計を使用し得る）。上述の値ｎ≒１０００で示すと、ｋは以下の式
ｋ＝ｋ（１）ｋ（２）ｋ（３）
を有し、ｋ（１）は、６のバイナリハミングウエイトを有し、ｋ（２）およびｋ（３）は、それぞれ７のバイナリハミングウエイトを有する。次いで、ｋに対する検索空間（３つのファクタに対する検索空間の積である）は、（Ｃ（１０００，６）Ｃ（１０００，７）Ｃ（１０００，７））≒２１６５の位数（ｏｒｄｅｒ）を有し、
αｋ＝（（αｋ（１））ｋ（２））ｋ（３）
の計算は、５＋６＋６＝１７回の乗算のみを要する。これは、約２９％の節約を示す。
【００５０】
好ましくは、少なくとも約２１６０の位数の検索空間が必要とされる。なぜなら、標準平方根検索によるアタック（ａｔｔａｃｋ）が時間をＯ（２８０）に低減する（Ｓｔｉｎｓｏｎ　ｓｕｐｒａ）。しかし、ｋがいくつかの低いハミングウエイト多項式の積である場合、どのようにして全空間上の平方根アタックを構築するか明らかではない。したがって、ｋ＝ｋ（１）ｋ（２）ｋ（３）である場合、第１の２つの項を検索（推定）し得、次いで、第３の項に対する平方根アタックを使用する。ｋについてαｋ＝βを解く第２のアプローチは、ｋ（３）を他の側に移動することである。従って、ｉを、積ｋ（１）ｋ（２）の全ての空間を通過させるようにし、ｊを、全てのｋ（３）値の空間を通過させるようにし、αｉおよび
【数８】
2004507789.tif 000009
の値のテーブルを作成する。ｊ−１は、ｊｍｏｄ２ｎ−１の逆数である。次いで、実行時間は、２つのテーブルの大きさの合計に比例する。
【００５１】
上記で与えられた例では、この例により（Ｃ（１０００，６）Ｃ（１０００，７））＋Ｃ（１０００，７）≒２１０７．７に比例する実行時間が得られる。しかし、この検索方法を考慮すると、ｋ（１）およびｋ（２）よりもかなり大きいｋ（３）を作成することが好ましい。従って、ハミングウエイト２、２、１１のそれぞれを有するようにｋ（１）、ｋ（２）、ｋ（３）を選択する場合、第１の平方根アタックは時間Ｏ（２８０．０）を有し、第２の平方根アタックは、時間Ｏ（２８４．３）を有するが、αｋの計算は１２回の乗算のみを要する。
【００５２】
上述の議論は式±ｐｅ（１）±・・・±ｐｅ（ｒ）の乗算器を用いてｐｎの要素を有するフィールドに同様に適用され得る。
【００５３】
（Ｋｏｂｌｉｔｚ楕円曲線に関するランダム倍数）
Ｅ／Ｆ２ｍを、２ｍ個の要素を有するフィールドにわたって規定された楕円曲線にして、Ｐ∈Ｅ（Ｆ２ｍ）を曲線上の点にする。多くの暗号構成は、倍数ＮＰの計算を要する。Ｎは２ｍに匹敵する大きさを有する。バイナリ形態でＮを記載すると、Ｎ０，．．．，Ｎｍ∈｛０，１｝として、
Ｎ＝Ｎ０＋２Ｎ１＋４Ｎ２＋・・・＋２ｉＮｉ＋・・・＋２ｍＮｍ
であり、ＮＰの計算は、ほぼＮ／２のダブリング（ｄｏｕｂｌｉｎｇ）および、Ｎ／２個の点の加算に低減される。既に上述したように、さらなる節約が、セット｛−１，０，１｝において，Ｎ０，．．．，Ｎｍを選択することによって得られ得，追加の数をほぼＮ／３に低減する。不幸にも、楕円曲線において点を２倍にすることは、２つの異なる点を加えることよりも計算がより困難になる。
【００５４】
所定の楕円曲線に対して、ダブリングを実質的に自由なフロベニウスマップで置き換えることによって必要な計算を著しく低減する。Ｅ／Ｆ２を「Ｋｏｂｌｉｔｚ曲線」すなわち、２つの要素を有するフィールドにわたって規定された通常の楕円曲線にする。従って、Ｅは、２つの曲線の内の１つである。
ａ∈Ｆ２として、Ｅ：ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋１
以下の式
τ：Ｅ（Ｆ２ｍ）→Ｅ（Ｆ２ｍ）；　　τ（ｘ，ｙ）＝（ｘ２，ｙ２）
をＥ上のフロベニウスマップにする。τ（Ｑ）の計算は、点の加算またはＥのダブリングと比較してほとんど時間がかからない。任意の整数Ｎを線形の組み合わせとして記述することが可能である。
Ｎ０，．．．，Ｎｍ∈｛−１，０，１｝として、
Ｎ＝Ｎ０＋τＮ１＋τ２Ｎ２＋・・・＋τｉＮｉ＋・・・＋τｍＮｍ
次いで、ＮＰの計算は、Ｅ（Ｆ２ｍ）においてｍ／３の加算に実質的に低減される（Ｎｉの約ｍ／３がゼロではない）。さらに、多くの暗号用途に対して、Ｐの整数倍を使用する実際の理由が存在しない。すなわち、倍数ＮＰを簡単に使用し得る。Ｎは上述のように、τのべき乗のランダムな線形の組み合わせである。例えば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換が十分完全に作用する。Ｄ．Ｈａｎｋｅｒｓｏｎらによる、Ｃｒｙｐｔｏｇｒａｐｈｉｃ　Ｈａｒｄｗａｒｅ　ａｎｄ　Ｅｍｂｅｄｄｅｄ　Ｓｙｓｔｅｍｓ（ＣＨＥＳ　２０００）、
【数９】
2004507789.tif 000010
およびＣ．Ｐａａｒ（編）、Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ（出版された）における「Ｓｏｆｔｗａｒｅ　ｉｍｐｌｅｍｅｍｔａｔｉｏｎ　ｏｆ　ｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ　ｃｒｙｐｔｏｇｒａｐｈｙ　ｏｖｅｒ　ｂｉｎａｒｙ　ｆｉｅｌｄｓ」と、Ｋｏｂｌｉｔｚ曲線に関する基本的な材料および計算方法について、Ｊ．Ｓｏｌｉｎａｓによる、Ｅｆｆｉｃｉｅｎｔ　ａｒｉｔｈｍｅｔｉｃ　ｏｎ　Ｋｏｂｌｉｔｚ　ｃｕｒｖｅｓ、Ｄｅｓｉｇｎｓ、Ｃｏｄｅｓ、ａｎｄ　Ｃｒｙｐｔｏｇｒａｐｈｙ　１９　（２０００）、１９５−２４９とを参照のこと。
【００５５】
要約すると、Ｆ２ｍにわたって、Ｋｏｂｌｉｔｚ曲線上の点のランダム符号化されたτ倍数の計算は、約ｍ／３の楕円曲線の加算を必要とする。本発明は、楕円曲線の追加の数を著しく低減する方法を提供する。上述のように、本発明に従って、τの低いハミングウエイトの線形の組み合わせの積となるように選択する。
【００５６】
具体的には、関心のある暗号の特定のフィールドが示される。ｍ＝１６３とすると、フィールドＦ２１６３で作用させる。式
【数１０】
2004507789.tif 000011
を有するようにＮを選択する（通常、各ファクタからτのべき乗を使用するため式（４）で各ファクタを考慮し得る。この式を用いることは、オーバーカウントを妨げる）。
【００５７】
第１に、Ｑ＝ＮＰとすると、困難の程度をチェックし、Ｎの検索またはＮ’Ｐ＝Ｑを満たすいくつかの他の整数Ｎ’の検索を実行する。Ｎ’についての平方根検索（例えば、Ｐｏｌｌａｒｄ　ｒｈｏ）は、（２１６３）１／２ステップの位数を得る。Ｎの特別な式を利用する第２の検索は、Ｑ＝ＮＰを
（Ｎ（３））−１Ｑ＝Ｎ（１）Ｎ（２）Ｐ
として記載することであり、２つの側のテーブルの値を比較する。この検索についての時間および空間要求は、２つのテーブルの内のより長い方の長さである。この例では、Ｎ（ｉ）’のそれぞれは、２６Ｃ（１６２，６）≒２４０．４の大きさの空間から得られ、Ｎ（１）Ｎ（２）Ｐの値のテーブルがＯ（２８０）の要素を有する。最終的に、Ｎ（１）およびＮ（２）の値の推定を試み、Ｎ（３）に対する平方根検索を実行するが、これは、さらにより大きな検索空間を与える。
【００５８】
上記式からＮを得ることの利点は明らかである。倍数の計算は、
ＮＰ＝Ｎ（１）Ｎ（２）Ｎ（３）Ｐ
６＋６＋６＝１８の楕円曲線の加算のみを要する（減算は、実質的に加算と同一である）。さらに、フロベニウスマップτのべき乗の多くの用途を必要とするが、これらは、点加算と比較してほとんど時間がかからず、この粗い解析において無視され得る。従って、冒頭で述べた方法によって必要とされる約１６３／３≒５４の加算ではなく、有用な暗号倍数ＮＰが、本発明の方法と共に１８回の加算を用いて計算され得ることが理解され得る。従って、本発明は３倍の速度増加を生み出す。
【００５９】
Ｎの全てに関するミートインザミドル（ｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅ）アタックは起こりそうにないが、このようなアタックが存在する場合であっても、上述のハミングウエイト（６，６，６）をウエイト（８，９，９）に交換するのに十分であり、２１６３．９の位数のＮ（１）Ｎ（２）Ｎ（３）の３種類のセットを入手する。ここで、ＮＰの計算は、２６回の加算を要求し、約２．１倍の速度増加を生み出す。実際には、この状況では、ウエイト（４，５，７，８）を有する４つの項Ｎ＝Ｎ（１）Ｎ（２）Ｎ（３）Ｎ（４）の積を使用するよりもはるかに速い。次いで、全検索空間は、大きさ
２４Ｃ（１６２，４）・２５Ｃ（１６２，５）・２７Ｃ（１６２，７）・２８Ｃ（１６２，８）≒２１６０．４８
を有し、ＮＰの計算は、約２．２６倍の速度増加に対する２４回の加算のみを要求する。
【００６０】
あるいは、小さいハミングウエイト項の積の合計であるＮを得る。例えば、４つの項を有するＮ＝Ｎ（１）Ｎ（２）＋Ｎ（３）Ｎ（４）の積は、小さいハミングウエイトを有する。もちろん、これは、Ｑ−ｂＰの値を有するａＰの値を一致させることによってＮの二等分に対する平方根アタックを可能にする。
【００６１】
あるいは、Ｎは、τの多項式ではなく、実際の整数であり得る。次いで、共役項を含み得る。例えば、形態
【数１１】
2004507789.tif 000012
は、整数を表し、１≦ｉ＜ｍ／２に対して、
【数１２】
2004507789.tif 000013
の値のテーブルを計算しかつ格納することは単純な事項である。
【００６２】
（ＮＴＲＵ公開鍵暗号システム）
ＮＴＲＵ公開鍵暗合システムは、環Ｒ＝（Ｚ／ｑｚ）［Ｘ］／（ＸＮ−１）において切り捨てられた多項式を使用する。暗号プロセスは、小さい係数を有する固定された公開鍵多項式ｈ（Ｘ）およびランダムに選択された多項式ｒ（Ｘ）に対する積ｒ（Ｘ）ｈ（Ｘ）の計算を含む。同様に、暗号プロセスは、ｆ（ｘ）ｅ（Ｘ）の積を含む。ここで、ｅ（Ｘ）は暗号文であり、秘密鍵ｆ（Ｘ）は、小さい係数を有する多項式である。さらなる詳細に対しては、Ｈｏｆｆｓｔｅｉｎ（１９９８），ｓｕｐｒａを参照のこと。
【００６３】
一般的に、環Ｒの計算ａ（Ｘ）ｂ（Ｘ）は、係数ａおよびｂのベクトルの畳み込み積である。この畳み込みを計算する未処理の（ｎａｉｖｅ）アルゴリズムは、Ｎ２ステップであり、各ステップは、加算および乗算である（ａ（Ｘ）が｛−１，０，１｝にランダムに分配された係数を有する場合、この計算は、約２Ｎ／３ステップを必要とし、ここで、ステップは、単に加算または減算である）。Ｋａｒａｔｓｕｂａ乗算またはＦＦＴ技術等の他の方法（利用可能な場合）は、このステップをＯ（ＮｌｏｇＮ）ステップに低減し得るが、ｂｉｇ−Ｏ定数は適度に大きい。
【００６４】
従って、本発明によれば、ｈ（Ｘ）の小さいランダム倍数は、積
ｒ（１）（Ｘ）ｒ（２）（Ｘ）・・・ｒ（ｔ）（Ｘ）ｈ（Ｘ）
として計算され得る。ここで、各ｒ（ｉ）（Ｘ）は、数個のゼロでない項のみを有する。次いで、必要な計算の量は、ゼロでない項の数の合計に比例する一方で、サンプル空間のサイズは、ｒ（ｉ）に対するサンプル空間の積にほぼ等しい。
【００６５】
例えば、Ｎ＝２５１として、
ｒ（Ｘ）＝ｒ（１）（Ｘ）ｒ（２）（Ｘ）
を得る。ここで、ｒ（１）およびｒ（２）は、正確に８つのゼロでない係数を有する多項式であり、４つの１および４つの−１である。過剰の重複を避けるために、好ましくは、ｒ（ｊ）（０）＝１であり、そして上記４つの１の内の３つのみがランダムに配置される。次いで、このようなｒ（Ｘ）多項式の数が、ほぼＣ（２５０，３）Ｃ（２４７，４）・Ｃ（２５０，３）Ｃ（２４７，４）・１／２≒２９５．９４である。ｒ（１）（Ｘ）を推定し、次いでｒ（２）（Ｘ）の平方根検索を使用する場合、これは、約
【数１３】
2004507789.tif 000014
の長さの検索アルゴリズムを生成する。積ｒ（Ｘ）ｈ（Ｘ）の計算が、ほぼ１６Ｎ加算および減算に低減される。ｒ（Ｘ）自体が６４のゼロでない係数を有することを留意し、ｒ（Ｘ）ｈ（Ｘ）の直接の計算は、基本演算のほぼ４倍を必要とする。
【００６６】
同様な構成がＮＴＲＵ秘密鍵ｆ（Ｘ）に対して使用され得、復号に対する同様な計算のスピードアップを生じる。
【００６７】
（小さいハミングウエイトの積のランダム性）
当業者に公知のランダム性を測定する多くの方法がある。具体的には、ＢＮ（Ｄ）＝｛Ｄの多項式を有するＮ−１次のバイナリ多項式｝とする。すなわち、ＢＮ（Ｄ）の要素は、ａｉ∈｛０，１｝および
【数１４】
2004507789.tif 000015
として、以下の多項式
ａ０＋ａ１Ｘ＋ａ２Ｘ＋・・・＋ａＮ−１ＸＮ−１
である。上述のように、多項式は、畳み込み規則ＸＮ＝１を用いて乗算される。
【００６８】
多項式の積は、Ｘのべき乗によって乗算することによる係数の自然回転（ｎａｔｕｒａｌ　ｒｏｔａｔｉｏｎ）を受ける。言い換えると、任意の積が以下のように書き直される。
ａ（Ｘ）＊ｂ（Ｘ）＝（Ｘｋ＊ａ（Ｘ））＊（ＸＮ−ｋ＊ｂ（Ｘ））
このような回転は、ランダムにはほど遠く、好ましくは同一の空間内で阻止される。従って、以下の式
Ｂ＊Ｎ（Ｄ）＝｛ａ（Ｘ）＝ａ０＋ａ１Ｘ＋ａ２Ｘ＋・・・＋ａＮ−１ＸＮ−１∈ＢＮ（Ｄ）：ａ０＝１｝
を、その係数がゼロでない多項式からなるＢＮ（Ｄ）のサブセットであるとする。
【００６９】
ランダムバイナリ多項式Ｂ＊Ｎ（Ｄ）の空間と積の空間とを比較する。
Ｐ＊Ｎ（ｄ１，ｄ２）＝｛ｃ（Ｘ）＝ａ（Ｘ）＊ｂ（Ｘ）：ａ（Ｘ）∈Ｂ＊Ｎ（ｄ１）ｂ（Ｘ）∈Ｂ＊Ｎ（ｄ２），ｃ（Ｘ）∈Ｂ＊Ｎ（ｄ１ｄ２）｝
多項式ａ（Ｘ）およびｂ（Ｘ）のみを考慮し、その積ａ（Ｘ）＊ｂ（Ｘ）がバイナリであることに留意されたい。実際には、これは、ランダムで（ａ，ｂ）の対を生成すること、これらを乗算すること、そして適切な式でなければ、この積を捨てることを必要とし得る。
【００７０】
どのようにして、積Ｐ＊Ｎ（ｄ１，ｄ２）のセットと真のランダムセットＢ＊Ｎ（ｄ１，ｄ２）とを比較することができるのか。一般的には、前者のセットは後者のセットよりもはるかに小さく、Ｂ＊Ｎ（ｄ１，ｄ２）の各要素は、Ｐ＊Ｎ（ｄ１，ｄ２）の要素によって、同様にヒットされる可能性はない。実験的には、Ｐ＊Ｎ（ｄ１，ｄ２）の要素は、一般的に積として一意に定まる表現を有する。好ましくは、ハミングウエイト差を使用して、Ｐ＊Ｎ（ｄ１，ｄ２）の要素が、空間Ｂ＊Ｎ（ｄ１，ｄ２）にランダムに分配される程度を決定する。任意の２つの多項式ａ（Ｘ）およびｂ（Ｘ）に対して、そのハミングウエイト差は、以下の式によって定義され得る。
ＨＷＤ（ａ，ｂ）＝＃｛ｉ：ａｉ≠ｂｉ｝
Ｂ＊Ｎ（Ｄ）においてランダムに選択された対がハミングウエイト差を与える可能性を計算することは容易である。より詳細には、任意の固定されたａ∈Ｂ＊Ｎ（Ｄ）に対して、既知の一定の係数が無視される場合、Ｄ−１個の１およびＮ−Ｄ個のゼロが存在する。ｂ∈ＢＮＤが、ａの内の１の個数と共通する１の個数ｋを有すると仮定する。次いで、ＨＷＤ（ａ，ｂ）は、ｂの内のゼロの個数によってヒットされたａの内の１の個数からＤ−１−ｋを取得し、ａの内のゼロの個数をヒットするｂの内の１の個数からＤ−１−ｋを取得し、それによりＨＷＤ（ａ，ｂ）＝２（Ｄ−１−ｋ）となる。従って、常にハミングウエイト差が偶数であり、ａおよびｂの１の個数Ｄ−１−ｈが一致する場合、２＊ｈに等しい。固定されたａ∈Ｂ＊Ｎ（Ｄ）に対して、多項式の全体の数によって起こり得る複数の方法を分割することによって、ランダムに選択されたｂ∈Ｂ＊Ｎ（Ｄ）が、ａからのハミングウエイト距離２＊ｈである確率は、以下の式によって与えられる。
【数１５】
2004507789.tif 000016
ランダムに選択されたｂ∈Ｐ＊Ｎ（ｄ１，ｄ２）に対して同様に可能性を正確に計算することはより困難であるため、コンピュータシミュレーションが使用された。１０，０００個の多項式が以下のセットからランダムに選択された。
Ｂ＝Ｂ＊２５１（６４）かつＰ＝Ｐ＊２５１（８，８）
Ｂ×Ｂ、Ｂ×Ｐ、およびＰ×Ｐのセットのそれぞれから選択された１０８対（ａ，ｂ）の全てに対して、ハミングウエイト差ＨＷＤ（ａ，ｂ）の分布を計算する。この結果を、式（５）から理論的に予想される値と共に表１に列挙する。研究された様々な状態において、ＨＷＤ（ａ，ｂ）の識別可能な差がないことが表から明らかである。
【表１】
2004507789.tif 000017
（小さいハミングウエイト積の一般式）
上述の構成全てが、２つの特性を有する環Ｒ、Ｒ−加群Ｍ、およびサブセットＳ⊂Ｒに関して極めて一般的に定義され得る。この２つの特性は、（ｉ）セットＳが十分大きい（ｉｉ）ｒ∈Ｓおよびｍ∈Ｍに対する積ｒ・ｍの計算は、「計算が容易である」。これらの性質は、ある程度互いに拮抗する。なぜなら、おそらく、セットＳが大きくなると、ｒ∈Ｓに対する積ｒ・ｍを計算することが平均してより困難になる。
【００７１】
セットＳを構成する１つの方法は、より小さいサブセットＳ１，．．．，Ｓｔ⊂Ｒを選択することである。
Ｓ＝｛ｒ１・・・ｒｔ：ｒ１∈Ｓ１，．．．，ｒｔ∈Ｓｔ｝
適切な仮説の下で、セットＳの大きさは、ほぼＳ１，．．．，Ｓｔの大きさの積である。各Ｓｉは、性質（ｉｉ）を有する。
【００７２】
１つの特定の要素τ∈Ｒが存在し、積τ・ｍが、各ｍ∈Ｍに対して計算することが容易である。次いで、好ましくはＳｉがτの低いハミングウエイト多項式から選択される。次いで、好ましくは、Ｓｉは、いくつかの固定されたｄ＝ｄｉ（または固定されたＤｉに対していくつかのランダムｄ≦Ｄｉに対して）に対して、以下の形態ｒの全ての要素からなる。
τｊ１＋τｊ２＋・・・＋τｊｄ
もちろん、逆性（ｉｎｖｅｒｓｅ）−ｍを計算することが容易である場合、以下の式を用いて大きさＳｉを増加させることができる。
±τｊ１±τｊ２±・・・±τｊｄ
同様に、いくつかの計算することが容易な要素τ１，．．．，τｕ∈Ｒがある場合、ｕの「変数」τ１，．．．，τｕにおいて、低いハミングウエイト多項式を入手し、さらに特定のセットＳｉの大きさを増加させる。
【００７３】
この一般式を上述の例に関連付けると、以下のように記される
１．Ｆ２ｎにおけるべき乗について
環はＲ＝Ｚであり、Ｒ−加群は、乗法群（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ　ｇｒｏｕｐ）Ｍ＝（Ｆ２ｎ）＊であり、特定のマップτは、ダブリング（すなわち、スクウェアリング）マップτ（α）＝α２である。
【００７４】
２．Ｋｏｂｌｉｔｚ曲線上の倍数について
環は、Ｒ＝Ｅｎｄ（Ｅ（Ｆ２ｍ））（すなわち、Ｅ（Ｆ２ｍ）から自身までの自己準同形の環）であり、Ｒ−加群は、Ｍ＝Ｅ（Ｆ２ｍ）であり、特定のマップτは、フロベニウスマップ
τ（ｘ，ｙ）＝（ｘ２，ｙ２）
である。
【００７５】
３．ＮＴＲＵ暗号システムについて
環は、Ｒ＝Ｚ［Ｘ］／（ＸＮ−１）であり、Ｒ−加群は、Ｍ＝Ｒ（すなわち、Ｒは、乗算を介して自身上に作用する）であり、特定のマップτは、Ｘとの乗算マップτ（ｆ（Ｘ））＝Ｘｆ（Ｘ）である。
これは、どのようにして小さいハミングウエイト積がこれらの特定の状況に適用するかを示し、さらに、本発明の広範囲な適用を示す。
【００７６】
Ｓがマップの像である、Ｓのサイズは、
Ｓ１×Ｓ２×・・・×Ｓｔ→Ｒ，（ｒ１，ｒ２，．．．ｒｔ）→ｒ１ｒ２・・・ｒｔ
以下のように特に定量化され得る。実際には、Ｓ⊂Ｔの性質およびＳ１×・・・×Ｓｔのランダムｔ−タプル（ｒ１，．．．，ｒｔ）が各要素Ｔをヒットする等しい機会を有するように見える性質を有すると共に、本来のセットＳ⊂Ｔを説明することは通常困難である（注記：Ｔはこの性質を有するが、通常、少なくとも１つは実験的な証明を獲得し得る）。セットＳｉの大きさに対してＮｉ＝│Ｓｉ│およびセットＴの大きさに対してＭ＝｜Ｔ│とする。次いで、基本的な確率理論を用いて、当業者は、ＴのＮ１Ｎ２・・・Ｎｔ要素置換によってランダムに選択された場合、異なる要素の予測された数を推定し得る。
【００７７】
本発明は好適な実施形態によって詳細に説明されてきた。しかし、本明細書を考慮することにより、当業者が本発明の精神および範囲において改変および／または改良を行うことができることが理解される。本発明の技術は、従来技術に対して著しく改良された計算効率を提供する。上述のこの技術は例示的であり、例示的な実施形態の特定の群に本発明を限定するものとしてみなされるべきではないことが強調されるべきである。
【００７８】
本明細書中に列挙された全参考文献の開示は、本明細書中で参考として援用する。さらに、Ｄ．Ｇｏｒｄｏｎ，Ａ　ｓｕｒｖｅｙ　ｏｆ　ｆａｓｔ　ｅｘｐｏｎｅｎｔｉａｔｉｏｎ　ｍｅｔｈｏｄｓ，Ｊｏｕｒｎａｌ　ｏｆ　Ａｌｇｏｒｉｔｈｍｓ　２７　（１９９８），１２９−１４６およびＤ．Ｓｔｉｎｓｏｎ，Ｃｒｙｐｔｏｇｒａｐｈｙ：Ｔｈｅｏｒｙ　ａｎｄ　Ｐｒａｃｔｉｃｅ，ＣＲＣ　Ｐｒｅｓｓ，１９９７の出版物の開示もまた本明細書中で参考として援用する。
【国際公開パンフレット】
2004507789.tif 000018
2004507789.tif 000019
2004507789.tif 000020
2004507789.tif 000021
2004507789.tif 000022
2004507789.tif 000023
2004507789.tif 000024
2004507789.tif 000025
2004507789.tif 000026
2004507789.tif 000027
2004507789.tif 000028
2004507789.tif 000029
2004507789.tif 000030
2004507789.tif 000031
2004507789.tif 000032
2004507789.tif 000033
2004507789.tif 000034
2004507789.tif 000035
2004507789.tif 000036
2004507789.tif 000037
2004507789.tif 000038
2004507789.tif 000039
2004507789.tif 000040
2004507789.tif 000041
2004507789.tif 000042
2004507789.tif 000043
2004507789.tif 000044
2004507789.tif 000045
2004507789.tif 000046
2004507789.tif 000047
2004507789.tif 000048
2004507789.tif 000049
2004507789.tif 000050
【国際調査報告】
2004507789.tif 000051
2004507789.tif 000052