Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- 52164500025 @ stu ecnu edu cn,52184501023 @ stu ecnu edu cn
- History
- 2020-05-24: last of 10 revisions
- 2020-02-25: received
- See all versions
- Short URL
- https://ia.cr/2020/245
- License
-
CC BY