On the algebraic structure of $E_p^{(m)}$ and applications to cryptography
This work addresses a specific problem in cryptography by providing an efficient attack on decomposition-based protocols, which is incremental as it builds on known algebraic structures to improve computational methods.
The paper tackles the problem of solving linear systems over the ring $E_p^{(m)}$ by showing its algebraic structure is isomorphic to a submodule of matrices over $\mathbb Z/p^{m}\mathbb Z$, making such computations equivalent to solving linear systems over $\mathbb Z/p^{m}\mathbb Z$. As a result, it breaks cryptographic protocols based on the Diffie-Hellman and ElGamal Decomposition problems over $E_p^{(m)}$ with a provable running time of $O(m^{6})$ operations.
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.