TY - GEN
T1 - New semantically secure public-key cryptosystems from the rsa-primitive
AU - Sakurai, Kouichi
AU - Takagi, Tsuyoshi
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - We analyze the security of the simplified Paillier (S-Paillier) cryptosystem, which was proposed by Catalano et al. We prove that the one-wayness of the S-Paillier scheme is as intractable as the standard RSA problem. We also prove that an adversary, which breaks the semantic security, can compute the least significant bits of the nonce. This observation is interesting, because the least significant bit of the nonce is the hard core bit of the encryption function. Moreover, we proposed a novel semantically secure cryptosystem, based on the one-way function fe,nMSBZ(l) (r) = (r−MSBl(r))emod n, where (e, n) is the RSA public-key and r −MSBl(r) means that the l most significant bits of r are zeroed. We proved that the one-wayness of the proposed scheme is as intractable as the standard RSA problem. An adversary, which breaks the semantic security of the proposed scheme, can break the least significant bits of the nonce. These security results of the proposed scheme are similar to those of the S-Paillier cryptosystem. However, the proposed scheme is more efficient than the S-Paillier cryptosystem.
AB - We analyze the security of the simplified Paillier (S-Paillier) cryptosystem, which was proposed by Catalano et al. We prove that the one-wayness of the S-Paillier scheme is as intractable as the standard RSA problem. We also prove that an adversary, which breaks the semantic security, can compute the least significant bits of the nonce. This observation is interesting, because the least significant bit of the nonce is the hard core bit of the encryption function. Moreover, we proposed a novel semantically secure cryptosystem, based on the one-way function fe,nMSBZ(l) (r) = (r−MSBl(r))emod n, where (e, n) is the RSA public-key and r −MSBl(r) means that the l most significant bits of r are zeroed. We proved that the one-wayness of the proposed scheme is as intractable as the standard RSA problem. An adversary, which breaks the semantic security of the proposed scheme, can break the least significant bits of the nonce. These security results of the proposed scheme are similar to those of the S-Paillier cryptosystem. However, the proposed scheme is more efficient than the S-Paillier cryptosystem.
UR - http://www.scopus.com/inward/record.url?scp=84958964396&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958964396&partnerID=8YFLogxK
U2 - 10.1007/3-540-45664-3_1
DO - 10.1007/3-540-45664-3_1
M3 - Conference contribution
AN - SCOPUS:84958964396
SN - 3540431683
SN - 9783540431688
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 16
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Naccache, David
A2 - Paillier, Pascal
PB - Springer Verlag
T2 - 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002
Y2 - 12 February 2002 through 14 February 2002
ER -