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