Paper 2004/020

Optimal Signcryption from Any Trapdoor Permutation

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


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Signcryptionuniversal padding schemesFeistel Transformextractable commitments
Contact author(s)
padding @ scs cs nyu edu
2004-02-01: received
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Michael J.  Freedman and Stanislaw Jarecki and Shabsi Walfish},
      title = {Optimal Signcryption from Any Trapdoor Permutation},
      howpublished = {Cryptology ePrint Archive, Paper 2004/020},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.