We formally study the notion of a joint signature and encryption in the public-key setting. We refer to this primitive as signcryption, adapting the terminology of (35). We present two de£nitions for the security of signcryption depending on whether the adversary is an outsider or a legal user of the system. We then examine generic sequential composition methods of building signcryp- tion from a signature and encryption scheme. Contrary to what recent results in the symmetric setting (5, 22) might lead one to expect, we show that classical "encrypt-then-sign" (EtS) and "sign-then-encrypt" (StE) methods are both se- cure composition methods in the public-key setting. We also present a new composition method which we call "commit-then-encrypt- and-sign" (CtE&S). Unlike the generic sequential composition methods,CtE&S applies the expensive signature and encryption operations in parallel, which could imply a gain in ef£ciency over theStE andEtS schemes. We also show that the newCtE&S method elegantly combines with the recent "hash-sign-switch" tech- nique of (30), leading to ef£cient on-line/off-line signcryption. Finally and of independent interest, we discuss the de£nitional inadequacy of the standard notion of chosen ciphertext (CCA2) security. We suggest a natural and very slight relaxation of CCA2-security, which we call generalized CCA2- security (gCCA2). We show that gCCA2-security suf£ces for all known uses of CCA2-secure encryption, while no longer suffering from the de£nitional short- comings of the latter.