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

Abstract

In this paper we show that the $\mathbb{Z}/p^m\mathbb{Z}$-module structure of the ring $E_p^{(m)}$ is isomorphic to a $\mathbb{Z}/p^m\mathbb{Z}$-submodule of the matrix ring over $\mathbb{Z}/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}/p^m\mathbb{Z}$-operations.

To appear in Applicable Algebra in Engineering, Communication and Computing