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
Abstract
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 p1$, 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 GoldwasserMicali cryptosystem, where $e$ is an integer only containing small prime factors. Compared to another extension of the GoldwasserMicali 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 GoldwasserMicali cryptosystem, our proposal is provable INDCPA 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Contact author(s)

52164500025 @ stu ecnu edu cn
52184501023 @ stu ecnu edu cn  History
 20200524: last of 10 revisions
 20200225: received
 See all versions
 Short URL
 https://ia.cr/2020/245
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/245, 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{https://eprint.iacr.org/2020/245}}, url = {https://eprint.iacr.org/2020/245} }