A generalization of Pohlig-Hellman simplification in elliptic curve cryptography

Let E be an elliptic curve over F _p. We investigate the construction of elliptic curve cryptosystems which use a commutative subring S ⊂ End(E) strictly larger than Z. Elliptic curve cryptosystems can be constructed based on the difficulty of solving this problem. We formulate a Generalized Elliptic Curve Discrete Logarithm Problem as follows: given P ∈ E(F$pr$) and Q in the S-module generated by P, find $y$ ∈ S such that Q = $y$P. Let $4$ be the p-th power Frobenius map. We display a generalization of Pohlig-Hellman simplification to the case where S = Z[$4$] = End(E). We write S/ann P as a product of local rings. Then we show how to solve for the projection of $y$ in each local ring by solving a series of congruences modulo the annihilators of progressively smaller powers of the maximal ideal. The most interesting cases are those where the maximal ideal is not principal.