International Association for Cryptologic Research

International Association
for Cryptologic Research


Michael J. Freedman


Optimal Signcryption from Any Trapdoor Permutation
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.
Parallel Signcryption with OAEP, PSS-R, and other Feistel Paddings
Yevgeniy Dodis Michael J. Freedman Shabsi Walfish
We present a new, elegant composition method for joint signature and encryption, also referred to as signcryption. The new method, which we call *Padding-based Parallel Signcryption* (PbPS), builds an efficient signcryption scheme from any family of trapdoor permutations, such as RSA. Each user U generates a single public/secret key pair f_U/f^{-1}_U used for both sending and receiving the data. To signcrypt a message m to a recipient with key f_{rcv}, a sender with key f_{snd} efficiently transforms m into a pair {w|s}, and simply sends { f_{rcv}(w) | f^{-1}_{snd}(s) }. PbPS enjoys many attractive properties: simplicity, efficiency, generality, parallelism of ``encrypting''/``signing'', optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, long message and associated data support, and, finally, complete compatibility with the PKCS#1 infrastructure. The pairs {w|s} sufficient for the security of PbPS are called *universal two-padding schemes*. Using one round of the Feistel transform, we give a very general construction of such schemes. Interestingly, we notice that all popular padding schemes with message recovery used for plain signature or encryption, such as OAEP, OAEP+, PSS-R, and ``scramble all, encrypt small'', naturally consist of two pieces {w|s}. Quite remarkably, we show that all such pairs become special cases of our construction. As a result, we find a natural generalization of all conventional padding schemes, and show that any such padding can be used for signcryption with PbPS. However, none of such paddings gives optimal message bandwidth. For that purpose and of independent interest, we define a new ``hybrid'' between PSS-R and OAEP, which we call *Probabilistic Signature-Encryption Padding* (PSEP). We recommend using PbPS with PSEP to achieve the most flexible and secure signcryption scheme up-to-date. To justify this point, we provide a detailed practical comparison of PbPS/PSEP with other previously-proposed signcryption candidates.