On the algebraic structure of $E_p^{(m)}$ and applications to cryptography

In this paper we show that the $\mathbb{Z}\mathrm{/}{p}^m\mathbb{Z}$-module structure of the ring $E_p^{(m)}$ is isomorphic to a $\mathbb{Z}\mathrm{/}{p}^m\mathbb{Z}$-submodule of the matrix ring over $\mathbb{Z}\mathrm{/}{p}^m\mathbb{Z}$. Using this intrinsic structure of $E_p^{(m)}$, solving a linear system over $E_p^{(m)}$ becomes computationally equivalent to solving a linear system over $\mathbb Z/p^{m}\mathbb Z$. As an application we break the protocol based on the Diffie-Hellman Decomposition problem and ElGamal Decomposition problem over $E_p^{(m)}$. Our algorithm terminates in a provable running time of $O(m^6)$ $\mathbb{Z}\mathrm{/}{p}^m\mathbb{Z}$-operations.