« 米国特許6286022(有限体の基底変換)要約 | トップページ | 米国特許6286022(有限体の基底変換)独立クレーム »

米国特許6286022(有限体の基底変換)発明の背景


本件は、楕円曲線暗号等で用いられる有限体の基底変換計算の効率化に関する。

米国特許 No.6,286,022 (Kaliski, Jr. et al. September 4, 2001) の「発明の背景」の訳文。


FIELD OF THE INVENTION

The present invention relates generally to techniques for converting signals of a finite field having one basis to signals of a finite field having another basis, and more particularly to finite field basis conversion techniques which involve a dual basis.

BACKGROUND OF THE INVENTION

As described in U.S. application Ser. No. 08/851,045, filed in the name of inventors Burton S. Kaliski Jr. and Yiqun Lisa Yin on May 5, 1997 and entitled "Methods and Apparatus for Efficient Finite Field Basis Conversion," and which is incorporated by reference herein, conversion between different choices of basis for a finite field is an important problem in today's computer systems, particularly for cryptographic operations. While it is possible to convert between two choices of basis by matrix multiplication, the matrix may be too large for some applications, hence the motivation for more storage-efficient techniques.

Elements of a finite field can be represented in a variety of ways, depending on the choice of basis for the representation. Let GF(q.sup.m) be the finite field, and let GF(q) be the ground field over which it is defined, where q is a prime or a prime power. The characteristic of the field is p where q=p.sup.r for some r.gtoreq.1. For even-characteristic fields, p=2. The degree of the field is m; its order is q.sup.m. A basis for the finite field is a set of m elements .omega..sub.0, . . . , .omega..sub.m-1 .epsilon.GF(q.sup.m) such that every element of the finite field can be represented uniquely as a linear combination of basis elements:

##EQU1##

where B[0], . . . , B[m-1] .epsilon. E GF(q) are the coefficients.

::本来の米国特許公報では、上記の ##EQU1## 相当部分に有限体の任意の要素が、基底の線型結合で表わされることを示す式が書かれている。

Two common types of basis are a polynomial basis and a normal basis. In a polynomial basis, the basis elements are successive powers of an element .gamma., called the generator:

.omega..sub.i =.gamma..sup.i.

A polynomial .function. of degree m, called the minimal polynomial of .gamma., relates the successive powers:

.gamma..sup.m +.function..sub.m-1.gamma..sup.m-1 +.function..sub.m-2.gamma..sup.m-2 + . . . +.function..sub.1.gamma.+.function..sub.0 =0.

In a normal basis, the basis elements are successive exponentiations of an element .gamma., again called the generator:

.omega..sub.i =.gamma..sup.q.sup..sup.i .

Another common type of basis is a dual basis. Let .omega..sub.0, . . . , .omega..sub.m-1 be a basis and let h be a nonzero linear function from GF(q.sup.m) to GF(q), i.e., a function such that for all .epsilon., .phi.,

h(.epsilon.+.phi.)=h(.epsilon.)+h(.phi.).

The dual basis of the basis .omega..sub.0, . . . , .omega..sub.m-1 with respect to h is the basis .xi..sub.0, . . . , .xi..sub.m-1 such that for all i,j,

##EQU2##

::本来の米国特許公報では、上記の ##EQU2## 相当部分に ωi と ξi との h に関する双対性を示す式が書かれている。

The dual basis is uniquely defined, and duality is syrnnetric: the dual basis with respect to h of the basis .xi..sub.0, . . . , .xi..sub.-1 is the basis .omega..sub.0, . . . , .omega..sub.m-1. A dual basis can be defined for a polynomial basis, a normal basis, or any other choice of basis, and with respect to a variety of functions (including, as an example, the function that evaluates to a particular coefficient of the representation of the field element in some basis).

::上記 ".xi..sub.-1" は --.xi..sub.m-1-- と読み替える。

The basis conversion or change-of-basis problem is to compute the representation of an element of a finite field in one basis, given its representation in another basis. The problem has two forms, which distinguish between the internal basis in which finite field operations are performed, and the external basis to and from which one is converting:

Import problem. Given an internal basis and an external basis for a finite field GF(q.sup.m) and the representation B of a field element in the external basis (the "external representation"), determine the corresponding representation A of the same field element in the internal basis (the "internal representation").

Export problem. Given an internal basis and an external basis for a finite field GF(q.sup.m) and the internal representation A of a field element, determine the corresponding external representation B of the same field element.

A conventional solution to both problems is to apply a change-of-basis matrix relating the two a bases. However, as the matrix is potentially quite large, and as the operations involved are not necessarily implementable with operations in either basis, the matrix-based conversion process may be inefficient in many important applications.

Another approach to conversion is to compute with a dual basis. Consider the problem of converting to the basis .omega..sub.0, . . . , .omega..sub.m-1, and let .xi..sub.0, . . . , .xi..sub.m-1 be its dual basis with respect to some linear function h. Then by the definition of the dual basis and the linearity of h, it follows that for all i,

B[]=h(.epsilon..xi..sub.i).

::上記の式の左辺で "B[]" を --B[i]-- と読み替える。

One can therefore convert by multiplying by elements of the dual basis and evaluating the function h, another straightforward and effective solution, which is efficient provided that the elements of the dual basis .xi..sub.0, . . . , .xi..sub.m-1 can be generated efficiently and that the function h can be computed efficiently. But this approach is again limited by a number of difficulties. First, the approach requires the elements of the dual basis, which must either be stored in the form of m.sup.2 coefficients, or computed. Second, it requires the computation of the function h, which may or may not be efficient. More practical choices of h have been suggested, such as a particular coefficient of the representation in some basis. See, for example, S. T. J. Fenn, M. Benaissa, and D. Taylor, "Finite Field Inversion Over the Dual Basis," IEEE Transactions on VLSI, 4(1):134-137, March 1996, which is incorporated by reference herein. But even with a more practical h, there still remains the problem of determining the dual basis efficiently. Moreover, the Fenn et al. method is efficient only when m is very small, and no general efficient conversion algorithm is given.

A number of other references describe finite field basis conversion operations involving dual basis. For example, U.S. Pat. No. 4,994,995, issued Feb. 19, 1991 to R. W. Anderson, R. L. Gee, T. L. Nguyen, and M. A. Hassner, entitled "Bit-Serial Division Method and Apparatus," describes hardware for a converter which converts an element in GF(2.sup.m) in a polynomial basis representation to a scalar multiple of its dual basis representation, where the scalar is an element of the field. The scalar is chosen so that the scalar multiple of the dual has many of the same elements as the polynomial basis. The hardware consists of AND gates, XOR gates, and a table for computing the trace function. Again, no general conversion algorithm is suggested. I. S. Hsu, T. K. Truong, L. J. Deutsch, and I. S. Reed, "A Comparison of VLSI Architecture of Finite Field Multipliers using Dual, Normal, or Standard Bases," IEEE Transactions on Computers, 37(6):735-739, June 1988, discloses conventional techniques for converting between polynomial and dual bases. D. R. Stinson, "On Bit-Serial Multiplication and Dual Bases in GF(2.sup.m)," IEEE Transactions on Information Theory, 37(6):1733-1737, November 1991, describes change-of-basis matrices between polynomial and dual bases. Given it polynomial basis such that the change-of-basis matrix M from the dual basis to some scalar (c.epsilon. GF(2.sup.m)) times the polynomial basis has as few "1" entries as possible, efficient bit-serial multiplication is possible. Given the minimal polynomial of .alpha., a generator of the polynomial basis, the Stinson reference gives simple formulae computing a scalar c and the weight of the matrix M. Although the above-cited references disclose numerous conventional techniques for converting between a polynomial basis and its dual basis, these techniques are generally inefficient in terms of memory, and may also be inefficient in terms of computation time.

The above-cited U.S. application Ser. No. 08/851,045 introduced the "shift-extract" technique of basis conversion, and also provided several storage-efficient and computation-efficient algorithms based on that technique for converting to and from a polynomial or normal basis. The conversion algorithms described therein overcome many of the problems associated with the previously-described conventional approaches. However, a need remains for further improvements in finite field basis conversion, particularly with regard to techniques involving dual basis.

It is therefore an object of the present invention to provide efficient finite field basis conversion techniques involving dual basis which do not require an excessively large amount of storage or an excessively large number of operations, and which take advantage of the built-in efficiency of finite field operations in one basis, rather than implementing new operations such as matrix multiplications.


発明の分野
本発明は、概括的には、或る基底を有する有限体の信号を、他の基底を有する有限体の信号に変換する技法に関し、特に、双対基底に関する有限体基底変換技法に関する。


発明の背景
Burton S. Kaliski Jr. 及び Yiqun Lisa Yin によって発明されたとして、1997年5月5日に出願された米国特許出願番号 08/851,045 "Methods and Apparatus for Efficient Finite Field Basis Conversion" (「効率的な有限体基底変換方法及び装置」) -- ここで参照することで、その内容が本明細書に編入されたものとする -- に記載されている如く、別々に選定された有限体基底間の変換は、現代のコンピュータ・システム、特に暗号演算のためのコンピュータ・システムにとり、重要な課題である。行列の乗算によるなら、選定された2つの基底間の変換は可能だとは言え、応用によっては行列は大規模になりすぎることがあるため、記憶効率が優れた技法が望まれていた。

有限体の要素は、選定される基底に応じて、様々に表現される。GF(qm) をそうした有限体、GF(q) をその基礎体とし(ただし、q は、素数又は素数の冪乗である)、体の標数を p とすると、q=pr かつ r≧1 なる r が存在する。標数が偶数の体では、p=2 となる。体の次数は m であり、位数は、qm である。有限体の基底とは、m 個の要素 ω0, . . . , ωm-1 ∈ GF(qm) からなる集合であって、有限体の全ての要素が、B[0], . . . , B[m-1] ∈ GF(q) を係数とする基底要素の線型結合

  ε =∑i=0m-1B[i]ωi

として一意に表わせるようなもののことである。


訳注::現在の cocolog は、数式の表現能力が貧弱で、上記も、総和記号が旨く表わせなかった。その意とするところは、B[i]ωi の i=0 から i=m-1 までの総和である。mimeTeX と云う CGI を使うと、html 文書においても TeX もどきの数式表現ができるらしいが、cocolog ではサポートされていないようだ。ちなみに「はてなダイアリー」では使えるとのこと。また、どのような実装によっているかは不明だが、Wikipedia でも、TeX による数式表示が可能である。

基底として良く知られているのは、多項式基底と正規基底の2種類である。多項式基底では、基底の要素は、生成元と呼ばれる或る要素 γ の逐次冪乗

   ωii

からなる。

前記の一連の冪乗を以下のように関連付ける γ の最小多項式と呼ばれる次数 m の多項式 f がある:

   γm + fm-1γm-1 + fm-2γm-2 + . . . +f1γ1 + f0 = 0

正規基底では、基底の要素は、やはり生成元と呼ばれる要素 γ の逐次指数乗

   ωiqi

からなる。

基底として、これらの他に良く知られているものとしては、双対基底がある。これを説明するために、まず ω0, . . . , ωm-1 を或る基底とし、h を、GF(qm) から GF(q) への零写像でない線型関数であるとする。つまり、すべての ε 及び φ に対して、

   h(ε+φ)=h(ε)+h(φ)

が成り立つものとする。

基底 ω0, . . . , ωm-1 の h に関する双対基底とは、全ての i, j に対して

   h(ωiξj) = 1 (i=j の時); 0 (i=j でない時)

を満たすような ξ0, . . . , ξm-1 のことである。

::本来の米国特許公報では、ωi と ξi との h に関する双対性を示す式は、場合分けを、大きな左ブレースを用いて表わしているが、現在の cocolog では、それが不可能なようなので、上記のように「= 1 (i=j の時); 0 (i=j でない時)」とした。この問題も、cocolog が mimeTeX (又は、TeX そのもの)をサポートすれば、解決されるはず。

双対基底は一意に定まる。また、双対性は対称的である。つまり、h に関する ξ0, . . . , ξm-1 の双対基底は、ω0, . . . , ωm-1 である。双対基底は、多項式基底にも、正規基底にも、その他の如何なる基底に対しても、そして、(例えば、体要素の或る基底における表現の特定の係数を評価する関数と云ったような)様々な関数に関して、定めることができる。

基底変換、つまり基底の変更とは、有限体の或る要素の或る基底に対する表現を、他の基底に対する表現から計算することである。有限体の演算が行なわれる内部基底と、変換先・変換元の外部基底とを区別すると、この課題は、2通りの形式で表わされる:

内部化: 有限体 GF(qm) の内部基底及び外部基底が与えられ、更に或る体要素の外部基底による表現 B (「外部表現」)が与えられた際に、前記要素の内部基底による対応表現 A (「内部表現」)を決定すること。

外部化: 有限体 GF(qm) の内部基底及び外部基底が与えられ、更に或る要素の内部表現 A が与えられた際に、前記体要素の対応外部表現 B を決定すること。

二つの課題に対する従来の解決策は、双方の基底に関する基底変換行列を適用することであった。しかし、この行列は非常に大規模になることがあり、また、必要となる演算が、基底のどちら側でも演算として実行に適するとは限らないため、行列に基づく変換方法は、多くの重要な応用において効率的でないことがあった。

変換を行う他の手法としては、双対基底でもって計算すると云うものがあった。基底 ω0, . . . , ωm-1 への変換を行う場合、或る線型関数 h に関するその双対基底を ξ0, . . . , ξm-1 とするなら、双対基底の定義及び h の線型性により、全ての i に対して、次の式が成り立つ。

   B[i]=h(εξi)

つまり、双対基底の要素を乗算し、関数 h を評価すると変換が行なえる訣だから、直接的で有効な解決策であり、双対基底要素 ξ0, . . . , ξm-1 が効率的に生成され、関数 h が効率的に計算できるなら、効率も良いものとなる。しかし、この手法にも、幾つかの制限がある。第1に、この手法では、双対基底の要素を m2 個の係数の形式で記憶しておくか、計算するかする必要がある。第2に、関数 h の計算が必要だが、これは効率的なことも非効率的なこともありうる。ある基底における表現の特定の係数と云うような、ヨリ実際的な h の選定も提案されている。例えば、S. T. J. Fenn, M. Benaissa 及び D. Taylor による "Finite Field Inversion Over the Dual Basis「双対基底上の有限体逆元決定」" (IEEE Transactions on VLSI, 4(1):134-137, 1996年3月) を見られたい(ここで参照することで、その内容が本明細書に編入されたものとする)。しかし、ヨリ実際的な関数 h によっても、双対基底を効率的に決定すると云う課題が残っている。更に「Fenn 他」の方法は、m が非常に小さい時にのみ効率的に過ぎず、包括的かつ効率的な変換アルゴリズムは知られていなかった。

双対基底を用いる有限体基底変換演算に就いて記載する文献は、ほかにも幾つかある。例えば、R. W. Anderson, R. L. Gee, T. L. Nguyen 及び M. A. Hassner による米国特許 4,994,995 "Bit-Serial Division Method and Apparatus「ビットシリアル除算方法及び装置」"(1991年2月19日)には、GF(2m) の要素の、多項式基底による表現を、その双対基底表現のスカラー倍(ただし、このスカラーは体の要素)に変換する変換器が記載されている。このスカラーは、双対をこのスカラー倍したものが、多項式基底と同一の要素を多く含むよう選定されている。この変換器は、AND ゲート群、XOR ゲート群、及びトレース関数を計算するための表からなる。やはり包括的ではない変換アルゴリズムであるが、I. S. Hsu, T. K. Truong, L. J. Deutsch 及び I. S. Reed による"A Comparison of VLSI Architecture of Finite Field Multipliers using Dual, Normal, or Standard Bases 「双対、正規又は標準基底を用いる有限体乗算器の VLSI アーキテクチャの比較」"(IEEE Transactions on Computers, 37(6):735-739, 1988年6月)では、多項式基底と双対基底との間を変換する従来技術が開示されている。D. R. Stinson による "On Bit-Serial Multiplication and Dual Bases in GF(2m)「GF(2m) におけるビットシリアル乗法と双対基底に就いて」" (IEEE Transactions on Information Theory, 37(6):1733-1737, 1991年11月)には、多項式基底と双対基底との間の基底変換行列に就いて記載されている。双対基底から多項式基底のスカラー(c ∈ GF(2m))倍への基底変換行列 M ができる限り少ない "1" 要素を有するような多項式基底に就いては、効率的なビットシリアル乗算が可能である。Stinson は、多項式基底の生成元 α の最小多項式が分っている場合に、スカラー c 及び行列 M の重みを計算する単純な公式を示している。上記の文献は、多項式基底とその双対基底との間を変換する様々な従来技術を開示しているが、こうした技術は、メモリーの観点からは概して非効率的であり、また計算時間の観点からも非効率的でありうる。

上記の米国特許出願番号 08/851,045 では、基底変換での「シフト・取り出し」技法が導入されて、その技法に基づく多項式基底又は正規基底への、又は多項式基底又は正規基底からの変換を行うことで記憶に就いても計算に就いても効率的なアルゴリズムが幾つか示されている。そこに記載されている変換アルゴリズムは、前記の従来手法に伴う問題点の多くを解消するものである。しかし、特に双対基底を用いる技法に関しては、有限体基底変換に対する一層の改善が必要であった。

従って、本発明の目的は、行列乗算のような演算を別途実装せずに、一つの基底における有限体演算の本来的な効率性を活用するることで、過度に大容量の記憶や過度に多数の演算を必要としない、双対基底を用いる有限体基底変換技術を提供することにある。

|
|

« 米国特許6286022(有限体の基底変換)要約 | トップページ | 米国特許6286022(有限体の基底変換)独立クレーム »

数学」カテゴリの記事

知的財産」カテゴリの記事

翻訳」カテゴリの記事

英語/English」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/40172/4833961

この記事へのトラックバック一覧です: 米国特許6286022(有限体の基底変換)発明の背景:

« 米国特許6286022(有限体の基底変換)要約 | トップページ | 米国特許6286022(有限体の基底変換)独立クレーム »