Welcome to the resource topic for 2020/245
Title:
New Assumptions and Efficient Cryptosystems from the e-th Power Residue Symbol
Authors: Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, Jun Shao, Licheng Wang, 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 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.
ePrint: https://eprint.iacr.org/2020/245
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .