On the security of a modified paillier public-key primitive

Kouichi Sakurai, Tsuyoshi Takagi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


Choi et al. proposed the modified Paillier cryptosystem (M-Paillier cryptosystem). They use a special public-key g ∈ ZZ/nZZ such that gϕ(n) = 1+n mod n2, where n is the RSA modulus. The distribution of the public key g is different from that of the original one. In this paper, we study the security of the usage of the public key. Firstly, we prove that the one-wayness of the M-Paillier cryptosystem is as intractable as factoring the modulus n, if the public key g can be generated only by the public modulus n. Secondly, we prove that the oracle that can generate the public-key factors the modulus n. Thus the public keys cannot be generated without knowing the factoring of n. The Paillier cryptosystem can use the public key g = 1+n, which is generated only from the public modulus n. Thirdly, we propose a chosen ciphertext attack against the M-Paillier cryptosystem. Our attack can factor the modulus n by only one query to the decryption oracle. This type of total breaking attack has not been reported for the original Paillier cryptosystem. Finally, we discuss the relationship between the M-Paillier cryptosystem and the Okamoto-Uchiyama scheme.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 7th Australasian Conference, ACISP 2002, Proceedings
EditorsLynn Batten, Jennifer Seberry
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540438610, 9783540438618
Publication statusPublished - 2002
Event7th Australasian Conference on Information Security and Privacy, ACISP 2002 - Melbourne, Australia
Duration: Jul 3 2002Jul 5 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other7th Australasian Conference on Information Security and Privacy, ACISP 2002

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the security of a modified paillier public-key primitive'. Together they form a unique fingerprint.

Cite this