PPad SPad XPad

w s w s w s

1 1

fS fS

1

fR fS

fR fR

Fig. 1. Generalized paddings as used by signcryption

Schemes from Trapdoor Permutations recipient as shown in Figure 1. Table 1 also shows

how the corresponding approaches could be used

for plain signature and encryption as well.

The generic schemes above validate the fact that

The convenience of each padding scheme de-

signcryption can be built from ordinary signature

pends on the application for which it is used. As

and encryption, but will be inef¬cient unless the

was shown in [9], P-Pad signcryption provides par-

latter are ef¬ciently implemented. In practice, ef-

allel application of “signing” fS’1 and “encrypting”

¬cient signature and encryption schemes, such as

fR, which can result in ef¬ciency improvements on

OAEP [5], OAEPP+ [13], PSS-R [6], are built from

parallel machines. However, the minimum cipher-

trapdoor permutations, such as RSA, and are ana-

text length is twice as large as compared to S-Pad,

lyzed in the random oracle model. Even with these

yet the exact security offered by S-Pad is not as

ef¬cient implementations, however, the generic

tight as that of P-Pad. Finally, X-Pad regains the

schemes will have several drawbacks. For exam-

optimal exact security of P-Pad, while maintain-

ple, users have to store two independent keys, the

ing ciphertext length nearly equal to the length

message bandwidth is suboptimal and the “ex-

of the trapdoor permutation (by achieving quite

act security” of the scheme is not as good as one

short s).

might expect. Thus, given that practical schemes

It remains to describe secure padding schemes

are anyway built from trapdoor permutations, it is

π for P-Pad, S-Pad and X-Pad. All construc-

natural to have highly optimized direct signcryp-

tions offered by [9] are quite similar. One starts

tion constructions from trapdoor permutations (in

with any extractable commitment (c, d), where c

the random oracle model).

is the commitment and d is the decommitment.

This is the approach of [9]. In their model, each

Such schemes are very easy to construct in the

user U independently picks a trapdoor permuta-

’1

random oracle model. For example, if |m| = n, for

tion fU (together with its trapdoor, denoted fU )

any 0 ¤ a ¤ n, the following scheme is an ex-

and publishes fU as its public key (see also trap-

tractable commitment: split m = m1 |m2 , where

door one-way function and substitutions and per-

|m1 | = a, |m2 | = n ’ a, and set

mutations). (Notice, only a single key is chosen,

unlike what is needed for the generic schemes.)

c = G(r ) • m1 |H(m2 |r )

Then, [9] considers the following three paradigms

d = m2 |r

termed P-Pad, S-Pad and P-Pad. Each paradigm

where G and H are random oracles (with appro-

proceeds by constructing a padding scheme pro-

duces π(m) = w|s, and then composing it with the priate input/output lengths) and r is a random

salt.

corresponding permutations of the sender and the

Table 1. Signcryption Schemes Based on Trapdoor Permutations.

Padding Type Encryption Signature Signcryption

w| fS’1 (s) fR(w)| fS’1 (s)

P-Pad (Parallel Padding) fR(w)|s

fS’1 (w|s) fR( fS’1 (w|s))

S-Pad (Sequential Padding) fR(w|s)

fS’1 (w)|s fR( fS’1 (w))|s

X-Pad (eXtended sequential Padding) fR(w)|s

582 Signcryption

To get a secure padding scheme for the P-Pad R know the key KSR. In fact, the scheme is per-

paradigm, one should then apply the Feistel fectly repudiable, since all the signcryptexts from

Transform to the resulting pair (d, c), with yet S could have been easily faked by R.

another random oracle F as the round function. To get insider-security for authenticity under

Namely, set w = c, s = F(c) • d. For example, us- the same assumption, one can instead consider

ing the extractable commitment above with a = the following scheme, originally due to [14], but

n, we get nothing else but the OAEP padding, formally analyzed by [3]. Below G and H are ran-

while a = 0 would give the PSSR padding! For dom oracles with appropriate domains, and E is

arbitrary a, [9] call the resulting hybrid be- a one-time secure symmetric-key encryption (e.g.,

tween PSSR and OAEP Probabilistic Signature- one-time pad will do). To signcrypt a message

from S to R, S chooses a random x ∈ Zq , com-

Encryption Padding (PSEP).

To get the padding π suf¬cient for either S-Pad putes Q = yR, makes a symmetric key K = H(Q),

x

sets c ← EK (m), computes the “validation tag” r =

or P-Pad, one only needs to perform one more Feis-

G(m, yA, yB, Q) and ¬nally t = x(r + xS)’1 mod q.

tel round to the construction above: w = s, s =

F (s) • w, and set π (m) = w |s . Coincidentally, the Then S outputs c, r, t as the signcryption of

resulting π also gives a very general construction m. To designcrypt c, r, t , R ¬rst recovers g x via

w = (ySgr )t , then recovers the Dif¬e“Hellman key

of the so called universal padding schemes [7].

As described, the paddings π1 and π3 above Q = w xR , the encryption key K = H(Q) and the

message m = DK (c). Before outputting m, how-

would only give insider security in the two-user

ever, it double checks if r = G(m, yA, yB, Q). While

setting. To get multi-user security, all one needs

to do is to prepend the pair (VEK S, VEK R) to all the this scheme is insider-secure for authenticity, it is

inputs to the random oracles F and F : namely, still not insider-secure.

create effectively independent F and F for ev- We also mention that the scheme supports pub-

ery sender-recipient pairing! More generally, the lic nonrepudiation. All that R has to do is to reveal

Q, m and a proof that Q = w xR (which can be done

paddings above also provide label support, if one

sticks the label L as part of the inputs to F and F . noninteractively using the Fiat-Shamir heuristics,

applied to the three-move proof that g, yR, w, Q

Finally, we remark that P-Pad, X-Pad and X-Pad

always support non-repudiation. form a DDH-tuple).

Yevgeniy Dodis

Schemes Based on Gap Dif¬e“Hellman

References

Finally, we present two very speci¬c, but ef¬-

cient schemes based on the so called Gap Dif¬e“ [1] An, Jee Hea (2001). “Authenticated encryption in

Hellman assumption. Given a cyclic group G of the public-key setting: Security notions and anal-

yses.” Cryptology ePrint Archive, Report 2001/079.

prime order q, and a generator g of G, the assump-

[2] An, Jee Hea, Yevgeniy Dodis, and Tal Rabin (2002).

tion states that the computational Dif¬e“Hellman

“On the security of joint signature and encrytion.”

problem (CDH) is computationally hard, even if

Advances in Cryptology”EUROCRYPT 2002, Ap-

one is given oracle access to the decisional Dif¬e“

ril 28“May 2, Lecture Notes in Computer Science,

Hellman (DDH) oracle. Speci¬cally, it is hard to

vol. 2332, ed. L. Knudsen. Springer-Verlag, Berlin.

compute gab from ga and gb , even if one can test Available from http://eprint.iacr.org/2002/046/

whether a tuple g x , g y , g z satis¬es z = xy mod q. [3] Baek, Joonsang, Ron Steinfeld, and Yuliang Zheng