Exponentiation calculation apparatus and method for calculating square root in finite extension field

A computing device for cryptographic processing that calculates an exponent (q^l+q^ l′) (^ denotes an exponent, and q denotes an order of a base field Fq) of an element in a 2r-th degree extension field, the computing device comprising:

• an accept unit configured to accept 2r elements in the 2r-th degree extension field, the elements being the vector representation;
• a multiplying unit configured to perform multiplication operations on the base field Fq using the accepted elements and obtain a multiplication value, one of the multiplication operations being performed in adherence to a calculation rule determined by a first condition, and the other one of the multiplication operations being determined by a second condition, the first and second conditions being conditions under which the element in the finite field to be placed in an algebraic torus, the first condition using a characteristic in which the element of the 2r-th degree extension field is an element of an algebraic torus T2r(Fq), and the second condition using a characteristic in which the element of the 2r-th degree extension field is an element of the algebraic torus T2(Fq^r);
• an adding and subtracting unit configured to perform an addition and subtraction operation using the obtained multiplication value and the accepted elements, and obtain a calculation result of the exponent (q^l±q^l′) of the element, the addition and subtraction operation being performed in adherence to the calculation rule;
• and
• an output unit configured to output the obtained calculation result, wherein
• the first condition is a condition in which the element of the 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2r(q) (.PHI.n(x) is a n-th cyclotomic polynomial) and the second condition is a condition in which an element of a 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2(q^r).

A method of computing a square executed by a computing device for cryptographic processing that includes an accept unit, a multiplying unit, an adding and subtracting unit, and an output unit, and calculates a square of an element in a finite field, the finite field being a 2r-th degree extension field Fq^{2r} (^ denotes an exponent, and r denotes a prime number), the method comprising:

• accepting by the accept unit, a plurality of elements in the finite field, the elements being the vector representation;
• obtaining a multiplication value by the multiplying unit, by performing multiplication operations on a base field using the accepted elements, one of the multiplication operations being determined by a first condition, and the other one of the multiplication operations being determined by a second condition, the first and second conditions being conditions under which the element in the finite field to be placed in an algebraic torus, the first condition using a characteristic in which the element of the 2r-th degree extension field is an element of an algebraic torus T2r(Fq), and the second condition using a characteristic in which the element of the 2r-th degree extension field is an element of the algebraic torus T2(Fq^r);
• obtaining a calculation result of the square of the elements by the adding and subtracting unit, by performing an addition and subtraction operation using the obtained multiplication value and the accepted elements, the addition and subtraction operation being determined by the first and second conditions;
• and
• outputting the obtained calculation result by the output unit, wherein
• the first condition is a condition in which the element of the 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2r(q) (.PHI.n(x) is a n-th cyclotomic polynomial) and the second condition is a condition in which an element of a 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2(q^r) (q denoting a characteristic of an extension field).

A computer program product having a computer-readable medium including programmed instructions, wherein when executed by a computer provided in a computing device for cryptographic processing that includes an accept unit, a multiplying unit, an adding and subtracting unit, and an output unit, and calculates a square of an element in a finite field, the finite field being a 2r-th degree extension field Fq^{2r} (^denotes an exponent, and r denotes a prime number), the instructions cause the computer to perform:

• accepting a plurality of elements in the finite field, the elements being the vector representation;
• obtaining a multiplication value by performing multiplication operations on a base field using the accepted elements, one of the multiplication operations being determined by a first condition, and the other one of the multiplication operations being determined by a second condition, the first and second conditions being conditions under which the element in the finite field to be placed in an algebraic torus, the first condition using a characteristic in which the element of the 2r-th degree extension field is an element of an algebraic torus T2r(Fq), and the second condition using a characteristic in which the element of the 2r-th degree extension field is an element of the algebraic torus T2(Fq^r);
• obtaining a calculation result of a square of the element by performing an addition and subtraction operation using the obtained multiplication value and the accepted elements, the addition and subtraction operation being determined by the first and second conditions;
• and
• outputting the obtained calculation result, wherein
• the first condition is a condition in which the element of the 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2r(q) (.PHI.n(x) is a n-th cyclotomic polynomial) and the second condition is a condition in which an element of a 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2(q^r) (q denoting a characteristic of an extension field).