the key-pair (SDKU ,VEKU ) for user U, where » tion).

r Simultaneous Attacks. Since the user U utilizes

is the security parameter, SDKU is the sign-

its secret key SDKU to both send and receive the

ing/decryption key that is kept private, and VEKU

data, it is reasonable to allow the adversary A

is the veri¬cation/encryption key that is made

oracle access to both the signcryption and the

public. The randomized signcryption algorithm

designcryption oracle for user U, irrespective of

SC for user U implicitly takes as input the user™s

whether A is attacking privacy or authenticity

secret key SDKU , and explicitly takes as input the

of U.

r

message m and the identity of the recipient ID R,

Two- vs. Multi-user Setting. In the simplistic

in order to compute and output the signcryptext

two-user setting, where there are only two users

on . For simplicity, we consider this identity ID R,

S and R in the network, the explicit identities

to be a public key VEK R of the recipient R, al-

become redundant. This considerably simpli-

though ID™s could generally include more convo-

¬es the design of secure signcryption schemes

luted information (as long as users can easily ob-

(see below), while providing a very useful inter-

tain VEK from ID). Thus, we write SCSDKU (M, ID R)

mediate step towards general, multi-user con-

as SCSDKU (m, VEK R), or simply SCU (m, VEK R).

structions (which are often obtained by adding

Similarly, user U™s deterministic designcryption

a simple twist to the basic two-user construc-

algorithm DSC implicitly takes the user™s private

tion). Intuitively, the security in the two-user

SDKU and explicitly takes as input the signcryp-

text ˜ and the senders™ identity ID S. Again, we model already ensures that there are no weak-

assume ID S = VEK R and write DSCSDKU ( , VEK S), nesses in the way the message is encapsulated

or simply DSCU ( , VEK S). The algorithm outputs inside the signcryptext, but does not ensure that

some message m, or ⊥ if the signcryption does not the message is bound to the identities of the

˜

sender and/or recipient. In particular, it might

verify or decrypt successfully. Correctness of prop-

still allow the adversary a large class of so called

erty ensures that for any users S, R, and message

m, we have DSC R(SC S (m, VEK R), VEK S) = m. identity fraud attacks, where the adversary can

“mess up” correct user identities without affect-

We also remark that it is often useful to add

ing the hidden message.

r

another optional parameter to both SC and DSC

Public NonRepudiation? In a regular digital sig-

algorithms: a label L (also termed associated data

nature scheme, anybody can verify the valid-

[11]). This label can be viewed as a public identi-

ity of the signature, and unforgeability of the

¬er which is “inseparably bound” to the message m

signature ensures that a signer S indeed cer-

inside the signcryptext. Intuitively, designcrypt-

ti¬ed the message. Thus, we say that a sign-

ing the signcryptext of m with the wrong label

cryption scheme provides nonrepudiation if the

should be impossible, as well as changing into

˜ of the same m under a dif- recipient can extract a regular (publicly veri¬-

a valid signcryptext

able) digital signature from the corresponding

ferent label.

signcryptext. In general, however, it is a-priori

Security of Signcryption only clear that the recipient R is sure that S

sent the message. Indeed, without R™s secret

key SDK R others might not be able to verify

Security of signcryption consists of two distinct

the authenticity of the message, and it might

components: one ensuring privacy, and the other”

not be possible for R to extract a regular sig-

authenticity. On a high level, privacy is de¬ned

nature of m. Thus, signcryption does not neces-

somewhat analogously to the privacy of an or-

sarily provide nonrepudiation. In fact, for some

dinary encryption, while authenticity”to that of

580 Signcryption

CURRENT SIGNCRYPTION SCHEMES: We now

applications we might explicitly want not to

have nonrepudiation. For example, S might be survey several signcryption schemes achieving

willing to send some con¬dential information to various levels of provable security.

R only under the condition that R cannot con-

vince others of this fact. To summarize, non- Generic Composition Schemes

repudiation is an optional feature which some

schemes support, others do not, and others ex- The two natural composition paradigms are

plicitly avoid!

r “encrypt-then-sign” (EtS) and “sign-then-encrypt”

Insider vs. Outsider Security. In fact, even with (StE). More speci¬cally, assume Enc is a seman-

R™s secret key SDK R it might be unclear to an tically secure encryption against chosen cipher-

observer whether S indeed sent the message text attack, and Sig is an existentially unforgeable

m to R, as opposed to R “making it up” with signature (with message recovery) against chosen

the help of SDK R. This forms the main basis for message attack. Each user U has a key for for Sig

distinction between insider- and outsider-secure and Enc. Then the “basic” EtS from S to R outputs

signcryption. Intuitively, in an outsider-secure Sig S (Enc R(m)), while StE”Enc R(Sig S(m)). Addi-

scheme the adversary must compromise com- tionally, [2] introduced a novel generic composi-

munication between two honest users (whose tion paradigm for parallel signcryption. Namely,

keys he does not know). Insider-secure signcryp- assume we have a secure commitment scheme,

tion protects a given user U even if his partner which on input m, outputs a commitment c and

might be malicious. For example, without U™s a decommitment d (where c is both hiding and

key, one cannot forge signcryptext from U to any binding). Then “commit-then-encrypt-and-sign”

other user R, even with R™s secret key. Similarly, (CtE&S) outputs a pair Enc R(d), Sig S(c) . Intu-

= SC S(m, VEKU ) to U and

if honest S sent itively, the scheme is private as public c reveals

later exposed his key SDK S to the adversary, the no information about m (while d is encrypted), and

latter still cannot decrypt . Clearly, insider- authentic since c binds one to m. The advantage of

security is stronger than outsider-security, but the above scheme over the sequential EtS and StE

might not be needed in a given application. In variants is the fact that expensive signature and

fact, for applications supporting message repu- encryption operations are performed in parallel.

diation, one typically does not want to have In fact, by using trapdoor commitments in place

insider-security. or regular commitments, most computation in

CtE&S”including the expensive computation of

both public-key signature and encryption”can be

Supporting Long Inputs done off-line, even before the message m is known!

It was shown by [2] that all three basic com-

Sometimes, it is easier to design natural sign- position paradigms yield an insider-secure sign-

cryption schemes supporting short inputs. Below cryption in the two-user model. Moreover, EtS is

we give a general method how to create sign- outsider-secure even if Enc is secure only against

cryption SC supporting arbitrarily long inputs the chosen plaintext attack, and StE is outsider-

from SC which only supports ¬xed-length (and secure even if Sig is only secure against no mes-

much shorter) inputs. The method was suggested sage attack. Clearly, all three paradigms are in-

by [8] and uses a new primitive called conceal- secure in the multiuser model, since no effort is

ment. A concealment is a publicly known ran- made to bind the message m to the identities of

domized transformation, which, on input m, out- the sender/recipient. For example, intercepting a

puts a hider h and a binder b. Together, h and signcryptext of the form Sig S(e) from S to R, an

b allow one to recover m, but separately, (1) the adversary A can produce SigA (e), which is a valid

hider h reveals “no information” about m, while signcryptext from A to R of the same message

(2) the binder b can be “meaningfully opened” by m, even though m is unknown to A. [2] sug-

at most one hider h. Further, we require |b| |m| gest a simple solution: when encrypting, always

(otherwise, one could trivially set b = m, h = …). append the identity of the sender to the mes-

Now, we let SC (m) = SC(b), h (and DSC is sim- sage, and when signing, of the recipient. For

ilar). It was shown in [8] that the above method example, a multi-user secure variant of EtS is

yields a secure signcryption SC . Further, a sim- Sig S(Enc R(m, VEK S), VEK R). Notice, if Enc and/or

ple construction of concealment was given: set h = Sig support labels, these identities can be part of

E„ (m), b = „, H(h) , where E is a symmetric-key the label rather than the message.

one-time secure encryption (with short key „ ) and Finally, we remark that StE and CtE&S always

H is a collision-resistant hash function (with short support nonrepudiation, while StE might or might

output). not.

Signcryption 581

m m m