Versatile padding schemes for joint signature and encryption

We propose several highly-practical and optimized constructions for joint signature and encryption primitives often referred to as signcryption. All our signcryption schemes, built directly from trapdoor permutations such as RSA, 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 and, finally, complete compatibility with the PKCS#1 infrastructure. Similar to the design of plain RSA-based signature and encryption schemes, such as RSA-FDH and RSA-OAEP, our signcryption schemes are constructed by designing appropriate padding schemes suitable for use with trapdoor permutations. We build a general and flexible framework for the design and analysis of secure Feistel-based padding schemes, as well as three composition paradigms for using such paddings to build optimized signcryption schemes. To unify many secure padding options offered as special cases of our framework, we construct a single versatile padding scheme PSEP which, by simply adjusting the parameters, can work optimally with any of the three composition paradigms for either signature, encryption, or signcryption. We illustrate the utility of our signcryption schemes by applying them to build a secure key-exchange protocol, with performance results showing 3x-5x speed-up compared to standard protocols.