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

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つの基底間の変換は可能だとは言え、応用によっては行列は大規模になりすぎることがあるため、記憶効率が優れた技法が望まれていた。

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

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

   ωi=γi

からなる。

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

   ωi=γqi

からなる。

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

が成り立つものとする。

   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 そのもの)をサポートすれば、解決されるはず。

   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 が非常に小さい時にのみ効率的に過ぎず、包括的かつ効率的な変換アルゴリズムは知られていなかった。

|
|

## コメントを書く

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

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

この記事のトラックバックURL: