TY - GEN
T1 - New Assumptions and Efficient Cryptosystems from the e-th Power Residue Symbol
AU - Zhao, Xiaopeng
AU - Cao, Zhenfu
AU - Dong, Xiaolei
AU - Shao, Jun
AU - Wang, Licheng
AU - Liu, Zhusen
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - The e-th power residue symbol (Formula Presented) is a useful mathematical tool in cryptography, where (Formula Presented) is an integer, (Formula Presented) is a prime ideal in the prime factorization of (Formula Presented) with a large prime p satisfying (Formula Presented) 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 hardness 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.
AB - The e-th power residue symbol (Formula Presented) is a useful mathematical tool in cryptography, where (Formula Presented) is an integer, (Formula Presented) is a prime ideal in the prime factorization of (Formula Presented) with a large prime p satisfying (Formula Presented) 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 hardness 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.
KW - Goldwasser-Micali cryptosystem
KW - Joye-Libert cryptosystem
KW - Leakage resilient public key encryption
KW - Lossy trapdoor function
KW - Power residue symbol
UR - https://www.scopus.com/pages/publications/85089721920
U2 - 10.1007/978-3-030-55304-3_21
DO - 10.1007/978-3-030-55304-3_21
M3 - 会议稿件
AN - SCOPUS:85089721920
SN - 9783030553036
T3 - Lecture Notes in Computer Science
SP - 408
EP - 424
BT - Information Security and Privacy - 25th Australasian Conference, ACISP 2020, Proceedings
A2 - Liu, Joseph K.
A2 - Cui, Hui
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th Australasian Conference on Information Security and Privacy, ACISP 2020
Y2 - 30 November 2020 through 2 December 2020
ER -