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

*Xiaopeng Zhao and Zhenfu Cao and Xiaolei Dong and Jun Shao and 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 p-1$, and $\zeta_e$ is an $e$-th primitive root of unity. One famous use 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 a number 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 result 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.

**Category / Keywords: **public-key cryptography / power residue symbol · Goldwasser-Micali scheme · Joye-Libert scheme · lossy trapdoor function · leakage resilient public-key encryption.

**Date: **received 23 Feb 2020, last revised 16 Mar 2020

**Contact author: **52164500025 at stu ecnu edu cn,52184501023@stu ecnu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20200316:112754 (All versions of this report)

**Short URL: **ia.cr/2020/245

[ Cryptology ePrint archive ]