International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Optimal Signcryption from Any Trapdoor Permutation

Yevgeniy Dodis
Michael J. Freedman
Stanislaw Jarecki
Shabsi Walfish
Search ePrint
Search Google
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.
  title={Optimal Signcryption from Any Trapdoor Permutation},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Signcryption, universal padding schemes, Feistel Transform, extractable commitments},
  note={ 12446 received 28 Jan 2004, last revised 28 Jan 2004},
  author={Yevgeniy Dodis and Michael J. Freedman and Stanislaw Jarecki and Shabsi Walfish},