Paper 2020/245

New Assumptions and Efficient Cryptosystems from the $e$-th Power Residue Symbol

Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, Jun Shao, Licheng Wang, and Zhusen Liu


The $e$-th power residue symbol $\left(\frac{\alpha}{\mathfrak{p}}\right)_e$ is a useful mathematical tool in cryptography, where $\alpha$ is an integer, $\mathfrak{p}$ is a prime ideal in the prime factorization of $p\mathbb{Z}[\zeta_e]$ with a large prime $p$ satisfying $e \mid p-1$, and $\zeta_e$ is an $e$-th primitive root of unity. One famous case of the $e$-th power symbol is the first semantic secure public key cryptosystem due to Goldwasser and Micali (at STOC 1982). In this paper, we revisit the $e$-th power residue symbol and its applications. In particular, we prove that computing the $e$-th power residue symbol is equivalent to solving the discrete logarithm problem. By this result, we give a natural extension of the Goldwasser-Micali cryptosystem, where $e$ is an integer only containing small prime factors. Compared to another extension of the Goldwasser-Micali cryptosystem due to Joye and Libert (at EUROCRYPT 2013), our proposal is more efficient in terms of bandwidth utilization and decryption cost. With a new complexity assumption naturally extended from the one used in the Goldwasser-Micali cryptosystem, our proposal is provable IND-CPA secure. Furthermore, we show that our results on the $e$-th power residue symbol can also be used to construct lossy trapdoor functions and circular and leakage resilient public key encryptions with more efficiency and better bandwidth utilization.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
52164500025 @ stu ecnu edu cn
52184501023 @ stu ecnu edu cn
2020-05-24: last of 10 revisions
2020-02-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaopeng Zhao and Zhenfu Cao and Xiaolei Dong and Jun Shao and Licheng Wang and Zhusen Liu},
      title = {New Assumptions and Efficient Cryptosystems from the $e$-th Power Residue Symbol},
      howpublished = {Cryptology ePrint Archive, Paper 2020/245},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.