Cryptology ePrint Archive: Report 2004/020

Optimal Signcryption from Any Trapdoor Permutation

Yevgeniy Dodis and Michael J. Freedman and Stanislaw Jarecki and Shabsi Walfish

Abstract: 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.

Category / Keywords: public-key cryptography / Signcryption, universal padding schemes, Feistel Transform, extractable commitments

Date: received 28 Jan 2004, last revised 28 Jan 2004

Contact author: padding at scs cs nyu edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040201:185417 (All versions of this report)

Discussion forum: Show discussion | Start new discussion