done here as O” /n2 O” is very similar to Z/n2 Z .

5 Conclusion

We have proposed two generic constructions that generalize many probabilistic

cryptosystems already proposed. This process helps to capture the ideas behind

these schemes. In particular, we have seen that the e¬cient homomorphic cryp-

tosystem proposed in the group of norm 1 elements of a quadratic ¬eld is very

similar to the Paillier scheme and can serve to construct an IND-CCA2 secure

system in the standard model, which is a rare object. We hope that these generic

constructions will help to propose new probabilistic cryptosystems. One possible

domain of application could be class groups of quadratic orders such as those

used in the NICE cryptosystem (cf. [PT00]).

Two Generic Constructions of Probabilistic Cryptosystems 107

References

[Ben88] Benaloh, J.C.: Veri¬able Secret-Ballot Elections. PhD thesis, Yale Uni-

versity (1988)

+

[BFP 01] Baudron, O., Fouque, P., Pointcheval, D., Poupard, G., Stern, J.: Practi-

cal multi-candidate election system. In: Proc. of PODC 2001 (2001)

[Cas07] Castagnos, G.: An e¬cient probabilistic public-key cryptosystem over

quadratic ¬elds quotients. Finite Fields Appl. 13(3), 563“576 (2007)

[CGH+ 01] Catalano, D., Gennaro, R., Howgrave-Graham, N., Nguyen, P.Q.: Pail-

lier™s cryptosystem revisited. In: Proceedings of the 8th ACM Conference

on Computer and Communications Security, pp. 206“214 (2001)

[CNS02] Catalano, D., Nguyen, P.Q., Stern, J.: The Hardness of Hensel Lift-

ing: The Case of RSA and Discrete Logarithm. In: Zheng, Y. (ed.)

ASIACRYPT 2002. LNCS, vol. 2501, pp. 299“310. Springer, Heidelberg

(2002)

[CS02] Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive

chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.)

EUROCRYPT 2002. LNCS, vol. 2332, pp. 45“64. Springer, Heidelberg

(2002)

[Dem94] Demytko, N.: A New Elliptic Curve Based Analogue of RSA. In: Helle-

seth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 40“49. Springer,

Heidelberg (1994)

[DJ01] Damg˚ ard, I., Jurik, M.J.: A Generalisation, a Simpli¬cation and some

Applications of Paillier™s Probabilistic Public-Key System. In: Kim, K.-c.

(ed.) PKC 2001. LNCS, vol. 1992. Springer, Heidelberg (2001)

[FO99] Fujisaki, E., Okamoto, T.: How to Enhance the Security of Public-Key

Encryption at Minimum Cost. In: Imai, H., Zheng, Y. (eds.) PKC 1999.

LNCS, vol. 1560, pp. 53“68. Springer, Heidelberg (1999)

[Gal02] Galbraith, S.D.: Elliptic Curve Paillier Schemes. Journal of Cryptol-

ogy 15(2), 129“138 (2002)

[GM84] Goldwasser, S., Micali, S.: Probabilistic Encryption. J. Comput. Syst.

Sci. 28, 270“299 (1984)

[GMMV03] Galindo, D., Mart´ S., Morillo, P., Villar, J.L.: An E¬cient Semantically

±n,

Secure Elliptic Curve Cryptosystem Based on KMOV. In: Proc. of WCC

2003, pp. 213“221 (2003)

[Jur03] Jurik, M.: Extensions to the Paillier Cryptosystem with Applications to

Cryptological Protocols. PhD thesis, Aarhus University (2003)

[KMOV92] Koyama, K., Maurer, U.M., Okamoto, T., Vanstone, S.A.: New Public-

Key Schemes Based on Elliptic Curves over the Ring Zn . In: Feigenbaum,

J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 252“266. Springer, Heidel-

berg (1992)

[Lip05] Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Commu-

nication. In: Zhou, J., L´pez, J., Deng, R.H., Bao, F. (eds.) ISC 2005.

o

LNCS, vol. 3650, pp. 314“328. Springer, Heidelberg (2005)

[NS98] Naccache, D., Stern, J.: A New Public Key Cryptosystem Based on Higher

Residues. In: Proceedings of the Third ACM Conference on Computer and

Communications Security, pp. 59“66 (1998)

[NSNK06] Nguyen, L., Safavi-Naini, R., Kurosawa, K.: Veri¬able shu¬„es: a formal

model and a Paillier-based three-round construction with provable secu-

rity. Int. J. Inf. Secur. 5(4), 241“255 (2006)

108 G. Castagnos

[OU98] Okamoto, T., Uchiyama, S.: A New Public Key Cryptosystem as Secure

as Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403,

pp. 308“318. Springer, Heidelberg (1998)

[Pai99] Paillier, P.: Public-Key Cryptosystems Based on Composite Degree

Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS,

vol. 1592, pp. 223“238. Springer, Heidelberg (1999)

[PT00] Paulus, S., Takagi, T.: A new public-key cryptosystem over quadratic

orders with quadratic decryption time. Journal of Cryptology 13, 263“

272 (2000)

[SL93] Smith, P., Lennon, M.J.J.: LUC: A New Public Key System. In: Proc.

of the Ninth IFIP Int. Symp. on Computer Security (1993), pp. 103“117

(1993)

Cramer-Shoup Satis¬es a Stronger Plaintext

Awareness under a Weaker Assumption

Isamu Teranishi1 and Wakaha Ogata2

1

NEC Corporation,

1753, Shimonumabe, Nakahara-Ku, Kawasaki, Kanagawa, 211-8666, Japan

teranisi@ah.jp.nec.com

2

Tokyo Institute of Technology,

2-12-1 Ookayama, Meguro-ku Tokyo, 152-8550, Japan

wakaha@mot.titech.ac.jp

Abstract. In the seminal paper of Eurocrypt 2006, Dent de¬ned a new

assumption, simulatability, and showed that the well-known Cramer-

Shoup public-key encryption scheme satis¬ed the weakest version of the

plaintext awareness, the computational plaintext awareness, under the

simulatability assumption, the DDH assumption, the DHK assumption,

and the collision resistance of the hash function. However, a tricky aspect

of the computational plaintext awareness was later shown. Moreover,

the de¬nition of the simulatability is elaborated. In this paper, we show

that the Cramer-Shoup scheme satis¬es a stronger variant of the plain-

text awareness, the statistical plaintext awareness, under a weaker and

simpler assumption than the simulatability. In particular, we show the

statistical PA2-ness of the Cramer-Shoup scheme under computational

assumptions.

Keywords: Statistical Plaintext Awareness, Standard Model, Cramer-

Shoup Scheme.

1 Introduction

1.1 Background

Plaintext Awareness (PA2) [BR94,BDPR98,HLM03,BP04,D06,TO06,BD08] is

one of the most fundamental notions about Public-Key Encryption schemes

(PKEs). Intuitively, a PA2 secure PKE is a scheme such that an adversary

cannot generate a ciphertext “without knowing” the corresponding plaintext.

More precisely, a PKE is called PA2 secure, if there exists an extractor which

can extract the plaintext from the ciphertext generated by the adversary.

Although PA2-ness was ¬rst de¬ned in the random oracle model

[BR94,BDPR98], Bellare and Palacio [BP04] succeeded in de¬ning PA2-

ness in the standard model. They gave three variants of standard model

PA2-ness: perfect/statistical/computational PA2-ness, depending on whether

the extracted plaintext was perfectly/statistically/computationally indistin-

guishable from the decryption. The PA2-nesses are important even in the

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 109“125, 2008.

c Springer-Verlag Berlin Heidelberg 2008

110 I. Teranishi and W. Ogata

standard model, because they can bring some insight into or an alternative

perception of the design of existing PKEs, as said by Bellare and Palacio [BP04].

In the seminal paper [D06], Dent provided a su¬cient condition for compu-

tational PA2-ness and showed the computational PA2-ness of the well-known

Cramer-Shoup scheme [CS98] by using it.

Theorem 1 (Cramer-Shoup is Computationally PA2 Secure[D06]).

The Cramer-Shoup scheme is computationally PA2 secure, if the underlying

group satis¬es the simulatability [D06], the DHK assumption [D91,BP04] and

the DDH assumption, and also if the hash function is collision resistant.

Here, the simulatability is an assumption which Dent newly introduced in [D06].

The intuitive meaning of it is as follows: there exist polytime computable func-

tions ± : {0, 1} ’ G and β : G ’ {0, 1} such that ± —¦ β and β —¦ ± are

computationally indistinguishable from the identity maps. The intuitive mean-

ing of the DHK assumption is as follows: “If an adversary A(g, h) outputs (u, v)

such that (g, h, u, v) is a DDH-tuple, then A knows r satisfying (u, v) = (g r , hr ).”