On the quantum security of high-dimensional RSA protocol

Abstract

Abstract The idea of extending the classical RSA protocol using algebraic number fields was introduced by Takagi and Naito (Construction of RSA cryptosystem over the algebraic field using ideal theory and investigation of its security. Electron Commun Japan Part III Fund Electr Sci. 2000;83:19–29). Recently, Zheng et al. proposed the use of the ring of algebraic integers of an algebraic number field and the lattice theory to present a high-dimensional form of RSA. The authors claim that their proposal is post-quantum and is significant both from the theoretical and practical point of view. In this article, we prove that the security of Zheng et al.’s scheme is still based on the factorization problem, and we present a practical quantum attack on this proposed scheme, our attack is a quantum polynomial time algorithm that employs Shor’s algorithm as a subroutine.