Isogeny calculation device, isogeny calculation method, and computer program product

Abstract

According to one embodiment, an isogeny calculation device includes a memory and an isogeny calculator. The memory stores, as a pre-calculated value, an intermediate value, among a plurality of intermediate values used for isogeny calculation, which is determined from an elliptic point T obtained by repeatedly performing L-point multiplication (where L is a positive integer) and M-isogeny (where M is a positive integer) on an elliptic point S serving as a kernel of the isogeny. The isogeny calculator identifies the elliptic point T serving as the kernel of the M-isogeny according to lower e digits (where e is a positive integer) of an L-adic representation of a secret key sk that determines the elliptic point S, reads the pre-calculated value determined from the elliptic point T from the memory, and performs at least one of calculations of the L-point multiplication and the M-isogeny using the pre-calculated value read from the memory.