Journal of Computer Science and Technology ›› 2022, Vol. 37 ›› Issue (2): 459-467.doi: 10.1007/s11390-021-0806-1

Special Issue: Theory and Algorithms

• Theory and Algorithms • Previous Articles     Next Articles

Generalized Goldwasser and Micali's Type Cryptosystem

Ying Guo1 (郭莹), Zhen-Fu Cao2,3,4,* (曹珍富), Senior Member, IEEE, Member, CCF, and Xiao-Lei Dong2 (董晓蕾), Member, IEEE        

  1. 1Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
    2Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China
    3Cyberspace Security Research Center, Peng Cheng Laboratory, Shenzhen 518055, China
    4Institute of Intelligent Science and Technology, Tongji University, Shanghai 200092, China
  • Received:2020-07-16 Revised:2021-04-26 Accepted:2021-04-29 Online:2022-03-31 Published:2022-03-31
  • Contact: Zhen-Fu Cao E-mail:zfcao@sei.ecnu.edu.cn
  • About author:Zhen-Fu Cao is currently a distinguished professor in Shanghai Key Laboratory of Trustworthy Computing in East China Normal University, Shanghai. He received his Ph.D. degree in the Harbin Institute of Technology, Harbin, in 1999. His research interests mainly include number theory, cryptography, and information security. He is a member of CCF and a senior member of IEEE.
  • Supported by:
    The work was supported by the National Key Research and Development Program of China under Grant No. 2020YFA0712300, the National Natural Science Foundation of China under Grant No. 61632012, and the Peng Cheng Laboratory Project of Guangdong Province of China under Grant No. PCL2018KP004.

PDF (PC)

6

Supplement

1

In 1982, Goldwasser and Micali proposed the first probabilistic public key cryptosystem with indistinguishability under chosen plaintext attack security based on the quadratic residuosity assumption. Ciphertext expansion of Goldwasser's scheme is quite large, thereby the scheme is inefficient. A lot of schemes have been proposed to reduce the ciphertext expansion. Some schemes use the same encryption algorithm as Goldwasser's scheme with different parameters and keys, which we call them Goldwasser and Micali's type (GM-type) schemes. GM-type schemes can be divided into two categories according to different parameters and decryption algorithms. In this paper, we propose the first generalized GM-type scheme combining these two categories. All GM-type schemes are special cases of our generalized GM-type scheme. The ciphertext expansion of our scheme is smaller than that of any other GM-type schemes.


Key words: Goldwasser and Micali's type (GM-type) scheme; k-th power residuosity; discrete logarithm problem ;

[1] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978, 21(2): 120-126. DOI: 10.1145/359340.359342.
[2] Goldwasser S, Micali S. Probabilistic encryption. Journal of Computer & System Science, 1984, 28(2): 270-299. DOI: 10.1016/0022-0000(84)90070-9.
[3] Blum M, Goldwasser S. An efficient probabilistic public-key encryption scheme which hides all partial information. In Proc. the 1984 Workshop on the Theory and Application of Cryptographic Techniques, August 1984, pp.289-302. DOI: 10.1007/3-540-39568-7_23.
[4] Blum L, Blum M, Shub M. Comparison of two pseudo-random number generators. In Proc. the 1982 International Cryptology Conference, August 1982, pp.61-78. DOI: 10.1007/978-1-4757-0602-4_6.
[5] Kurosawa K, Katayama Y, Ogata W et al. General public key residue cryptosystems and mental poker protocols. In Proc. the 1990 Workshop on the Theory & Application of Cryptographic Techniques on Advances in Cryptology, May 1990, pp.374-388. DOI: 10.1007/3-540-46877-3_34.
[6] Benaloh J, Tuinstra D. Receipt-free secret-ballot elections (extended abstract). In Proc. the 26th Annual ACM Symposium on Theory of Computing, May 1994, pp.544-553. DOI: 10.1145/195058.195407.
[7] Park S J, Lee B Y, Won D H. A probabilistic encryption using very high residuosity and its applications. In Proc. the 1995 Global Telecommunications Conference, November 1995, pp.1179-1182. DOI: 10.1109/GLOCOM.1995.502589.
[8] Benaloh J, Fischer M J. A robust and verifiable cryptographically secure election scheme. In Proc. the 26th Symposium on Foundations of Computer Science, September 1985, pp.372-382. DOI: 10.1109/SFCS.1985.2.
[9] Naccache D, Stern J. A new public key cryptosystem based on higher residues. In Proc. the 5th ACM Conference on Computer and Communications Security, November 1998, pp.59-66. DOI: 10.1145/288090.288106.
[10] Joye M, Libert B. Efficient cryptosystems from 2k-th-th power residue symbols. In Proc. the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2013, pp.76-92. DOI: 10.1007/978-3-642-38348-9_5.
[11] Benhamouda F, Herranz J, Joye M et al. Efficient cryptosystems from 2k-th power residue symbols. Journal of Cryptology, 2017, 30(2): 519-549. DOI: 10.1007/s00145-016-9229-5.
[12] Cao Z, Dong X, Wang L et al. More efficient cryptosystems from kth-power residues. Cryptology ePrint Archire: Report 2013/569. https://eprint.iacr.org/2013/569, Jan. 2021.
[13] Zhao X, Cao Z, Dong X et al. New assumptions and efficient cryptosystems from the e-th power residue symbol. In Proc. the 25th Australasian Conference on Information Security and Privacy, November 30-December 2, 2020, pp.408-424. DOI: 10.1007/978-3-030-55304-3_21.
[14] Okamoto T, Uchiyama S. A new public-key cryptosystem as secure as factoring. In Proc. the 1998 International Conference on the Theory and Application of Cryptographic Techniques Espoo, May 31-June 4, 1998, pp.308-318. DOI: 10.1007/BFb0054135.
[15] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In Proc. the 1999 International Conference on the Theory and Application of Cryptographic Techniques, May 1999, pp.223-238. DOI: 10.1007/3-540-48910-X_16.
[16] Damgard I, Jurik M. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In Proc. the 4th International Workshop on Practice and Theory in Public Key Cryptosystems, February 2001, pp.119-136. DOI: 10.1007/3-540-44586-2_9.
[17] Obi O O, Ali F H, Stipidis E. Explicit for decryption in a generalisation of the Paillier scheme. IET Information Security, 2008, 1(4): 163-166. DOI: 10.1049/iet-ifs:20060132.
[18] Guo Y, Cao Z, Dong X. A generalization of Paillier's public-key system with fast decryption. https://eprint.iacr.org/2020/796, Jan. 2021.
[1] Tzer-Shyong Chen, Kuo-Hsuan Huang, and Yu-Fang Chung. Digital Multi-Signature Scheme Based on the Elliptic Curve Cryptosystem [J]. , 2004, 19(4): 0-0.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Li Renwei;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[2] Deng Yaping; Chen Tinghuai;. A Reliable and Fault-Tolerant Interconnection Network[J]. , 1990, 5(2): 117 -126 .
[3] Zheng Chongxun; Zhang Kenong;. Orthogonal Algorithm of Logic Probability and Syndrome-Testable Analysis[J]. , 1990, 5(2): 203 -209 .
[4] Yu Xiangdong;. Some Hard Examples for the Resolution Method[J]. , 1990, 5(3): 302 -304 .
[5] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[6] Wang Yihe; Hong Jiarong;. AECAM:An Extension Matrix Algorithm on a Cellular Automata Machine[J]. , 1992, 7(1): 88 -91 .
[7] Jin Zhi; Hu Shouren;. SCKE:Combining Logic- with Object-Oriented Paradigm[J]. , 1993, 8(1): 38 -48 .
[8] Wang Xianchang; Chen Huowang; Zhao Qinping;. On the Relationship Between TMS and Logic Programs[J]. , 1994, 9(3): 245 -251 .
[9] Luo Gang;. Generating Conformance Tests for Nondeterministic Protocol Machines[J]. , 1994, 9(4): 289 -301 .
[10] Hock C. Chan;. Translational Semantics for a Conceptual Level Query Language[J]. , 1995, 10(2): 175 -187 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved