Cryptology ePrint Archive: Report 2020/245

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

Short URL: ia.cr/2020/245

[ Cryptology ePrint archive ]