We build several highly-practical and optimized signcryption
constructions directly from trapdoor permutations, in the random oracle model. All our constructions share features such as
simplicity, efficiency, generality, near-optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, "backward" use for plain signature/encryption, long message and associated data support, the strongest-known qualitative security (so-called IND-CCA and sUF-CMA) and, finally, complete compatibility with the PKCS#1 infrastructure. While some of these features are present in previous works to various extents, we believe that our schemes improve on earlier proposals in at least several dimensions, making the overall difference quite noticeable in practice.
Concretely, we present three methods generally based on what we call
Parallel, Sequential, and eXtended sequential Padding schemes (P-Pad,
S-Pad, X-Pad). P-Pad offers parallel "signing" and "encrypting",
optimal exact security, and minimum ciphertext length twice as long as the length of a TDP , while still maintaining optimal bandwidth.
S-Pad loses parallelism and some exact security, but has minimal
ciphertext length equal to that of a TDP. Any S-Pad can also be
used as a "universal padding" scheme. X-Pad is similar to S-Pad,
but regains optimal exact security at the expense of a
marginally-longer minimum ciphertext length. Moreover, to unify
various padding options, we construct a single versatile padding
scheme PSEP (Probabilistic Signature-Encryption Padding) which, by simply adjusting the lengths of the parameters, can work optimally as either a P-Pad, S-Pad or X-Pad.