Patent ID: 8374342

Claim:
A processing device comprising: a processor configured to: compute a scalar multiplication [s]P of a rational point P of an additive group E(F p ) including rational points on an elliptic curve where a characteristic p, an order r, and a trace t of a Frobenius endomorphism at an embedding degree k=12 using an integer variable χ are given by: p (χ)=36χ 4 −36χ 3 +24χ 2 −6χ+1, r (χ)=36χ 4 −36χ 3 +18χ 2 −6χ+1 =p (χ)+1 −t (χ), t (χ)=6χ 2 +1; compute the scalar multiplication [s]P as: [ s]P =([ s 4 +s 5 ]φ′ 2 +[s 2 −s 5 ]) P, using a Frobenius map φ′ 2 given by: [ p 2 ]P=φ′ 2 ( P ) assuming that a twist degree d is 6 and a positive integer e is 2 where k=d×e to give: [6χ 2 −4χ+1 ]P =[(−2χ+1) p 2 ]P=[− 2χ+1]φ′ 2 ( P ); compute a ν-adic expansion of the scalar s using 6χ 2 −4χ+1=ν to give: s=s 1 ν+s 2 , s 2 <ν, and s ≡(−2χ+1) s 1 p 2 +s 2 mod r; compute a ν-adic expansion of the (−2χ+1)s 1 part to give: s ≡( s 3 ν+s 4 ) p 2 +s 2 ≡s 5 p 4 +s 4 p 2 +s 2 mod r where p 4 ≡p 2 −1 mod r, and using s ≡( s 4 +s 5 ) p 2 +( s 2 −s 5 )mod r: calculate a group signature based on the computed scalar multiplication [s]P, the computed v-adic expansion of the scalar s using 6χ 2 −4χ+1=ν, and the computed a ν-adic expansion of the (−2χ+1)s 1 ; use the calculated group signature in an authentication process; a storage device configured to store the value of the scalar s; and wherein the storage device is further configured to store the coefficients s 1 , s 2 , s 3 , s 4 , and s 5 , respectively; wherein a value obtained by computing ν-adic expansion of the scalar s is stored in the storage device; wherein a value obtained by computing ν-adic expansion of (−2χ+1)s 1 is stored in the storage device; and wherein the value of (−2χ+1)s 3 is stored in the storage device.