US 8,145,697 B2 · System and method for efficient basis conversion

Abstract

This invention describes a method for evaluating a polynomial in an extension field Fqm, wherein the method comprises the steps of partitioning the polynomial into a plurality of parts, each part is comprised of smaller polynomials using a q-th power operation in a field of characteristic q; and computing for each part components of qth powers from components of smaller powers. A further embodiment of the invention provides for a method of converting a field element represented in terms of a first basis to its representation in a second basis, comprising the steps of partitioning a polynomial, being a polynomial in the second basis, into a plurality of parts, wherein each part is comprised of smaller polynomials using a qth power operation in a field of characteristic q; evaluating the polynomial at a root thereof by computing for each part components of qth powers from components of smaller powers; and evaluating the field element at the root of the polynomial.

Claims42

Dependent claims

A non-transitory computer readable medium comprising computer executable instructions for a processor in a device converting an element of a finite field of characteristic q in a cryptographic system from a representation in a first basis defined by a first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, wherein said representation in said second basis is to be used in a cryptographic scheme, said computer readable medium comprising instructions for:

a) obtaining said element from said cryptographic system;
b) representing said element of said finite field in said first basis as a polynomial a(x);
c) determining a root r of said second irreducible polynomial;
and
d) evaluating said polynomial a(x) at said root r to obtain a representation a(r) of a(x) in said second basis for use in said cryptographic scheme;
said evaluation being characterised by the steps of:
i) partitioning said polynomial a(x) into a plurality of component polynomials, such that said polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q;
ii) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r;
and
iii) computing the value of a(r) from said values of said component polynomials at said root r, using operations of multiplication by r and exponentiation by q.

7 more elements

A cryptographic system for converting an element of a finite field of characteristic q from a representation in a first basis defined by a first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, wherein said representation in said second basis is to be used in a cryptographic scheme, said cryptographic system comprising:

a device comprising an accumulator, and a processor for converting said element from said first basis to said second basis using said accumulator;
and
computer executable instructions that when executed by said processor, configure said processor for:
a) obtaining said element from said cryptographic system;
b) representing said element of said finite field in said first basis as a polynomial a(x);
c) determining a root r of said second irreducible polynomial;
and
d) evaluating said polynomial a(x) at said root r to obtain a representation a(r) of a(x) in said second basis for use in said cryptographic scheme;
said evaluation being characterised by the steps of:
i)a partitioning said polynomial a(x) into a plurality of component polynomials, such that said polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q;
ii) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r;
and
iii) computing the value of a(r) from said values of said component polynomials at said root r, using operations of multiplication by r and exponentiation by q.

10 more elements

A non-transitory computer readable medium for evaluating a first irreducible polynomial a(x) at a root r to obtain a representation a(r) in a second basis, said computer readable medium to be used in a cryptographic scheme by a device having a processor and an accumulator for converting an element of a finite field of characteristic q stored in a cryptographic system from a representation in a first basis defined by said first irreducible polynomial to a representation in said second basis defined by a second irreducible polynomial, said computer readable medium comprising instructions for:

a) obtaining said first irreducible polynomial a(x) and said root r of said second irreducible polynomial from said cryptographic system, said first irreducible polynomial representing said element of said finite field in said first basis;
b) partitioning said first irreducible polynomial a(x) into a plurality of component polynomials, such that said first irreducible polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q, said first irreducible polynomial a(x) representing an element of a finite field of characteristic g in a first basis;
c) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r;
d) computing the value of a second irreducible polynomial a(r) in a second basis from the values of said component polynomials at said root r using operations of multiplication by r and exponentiation by q and;
e) providing said second irreducible polynomial a(r) to said cryptographic scheme.

2 more elements

A cryptographic system for evaluating a first irreducible polynomial a(x) at a root r to obtain a representation a(r) in a second basis, said cryptographic system configured for participating in a cryptographic scheme for converting an element of a finite field of characteristic q from a representation in a first basis defined by said first irreducible polynomial to a representation in said second basis defined by a second irreducible polynomial, said cryptographic system comprising:

a device comprising an accumulator for operating on said finite field of characteristic q;
said first irreducible polynomial a(x), and said root r of said second irreducible polynomial, and a processor for obtaining said first irreducible polynomial a(x) and said root r of said second irreducible polynomial and for evaluating said first irreducible polynomial a(x) at said root r using said accumulator;
and
computer executable instructions that when executed by said processor, configure said processor for:
a) obtaining said first irreducible polynomial a(x) and said root r of said second irreducible polynomial, said first irreducible polynomial representing said element of said finite field in said first basis;
b) partitioning said first irreducible polynomial a(x) into a plurality of component polynomials, such that said first irreducible polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q, said first irreducible polynomial a(x) representing an element of a finite field of characteristic q in a first basis;
c) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r;
d) computing the value of a second irreducible polynomial a(r) in a second basis from the values of said component polynomials at said root r using operations of multiplication by r and exponentiation by q and;
e) providing said second irreducible polynomial a(r) to said cryptographic scheme.

6 more elements

Dependencies are inferred from the claim text.

System and method for efficient basis conversion

Life of this patent

System and method for efficient basis conversion

Life of this patent

Abstract

Claims42