Versatile padding schemes for joint signature and encryption

ABSTRACT

We propose several highly-practical and optimized constructions for joint signature and encryption primitives often referred to as <i>signcryption</i>. All our signcryption schemes, built directly from trapdoor permutations such as RSA, 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 and, finally, complete compatibility with the PKCS#1 infrastructure.

Similar to the design of plain RSA-based signature and encryption schemes, such as RSA-FDH and RSA-OAEP, our signcryption schemes are constructed by designing appropriate <i>padding schemes</i> suitable for use with trapdoor permutations. We build a general and flexible <i>framework</i> for the design and analysis of secure <i>Feistel-based</i> padding schemes, as well as three composition paradigms for using such paddings to build optimized signcryption schemes. To unify many secure padding options offered as special cases of our framework, we construct a single <i>versatile</i> padding scheme PSEP which, by simply adjusting the parameters, can work optimally with any of the three composition paradigms for either signature, encryption, or signcryption.

We illustrate the utility of our signcryption schemes by applying them to build a secure key-exchange protocol, with performance results showing 3x-5x speed-up compared to standard protocols.

REFERENCES

• 1: Jee Hea An , Yevgeniy Dodis , Tal Rabin, On the Security of Joint Signature and Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.83-107, May 02, 2002
• 2: Joonsang Baek , Ron Steinfeld , Yuliang Zheng, Formal Proofs for the Security of Signcryption, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.80-98, February 12-14, 2002
• 3: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 4: BELLARE, M., AND ROGAWAY, P. Optimal asymmetric encryption. In Advances in Cryptology--EUROCRYPT 94 (Perugia, Italy, May 1994).
• 5: BELLARE, M., AND ROGAWAY, P. The exact security of digital signatures: How to sign with RSA and Rabin. In Advances in Cryptology--EUROCRYPT 96 (Saragossa, Spain, May 1996).
• 6: Jean-Sébastien Coron , Marc Joye , David Naccache , Pascal Paillier, Universal Padding Schemes for RSA, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.226-241, August 18-22, 2002
• 7: Don Davis, Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.65-78, June 25-30, 2001
• 8: DODIS, Y., AND AN, J. H. Concealment and its applications to authenticated encryption. In Advances in Cryptology--EUROCRYPT 2003 (Warsaw, Poland, May 2003).
• 9: DODIS, Y., FREEDMAN, M. J., JARECKI, S., AND WALFISH, S. Optimal signcryption from any trapdoor permutation. Cryptology ePrint Archive, Report 2004/020, 2004.
• 10: DODIS, Y., AND REYZIN, L. On the power of claw-free permutations. In Proc. 3rd Conference on Security in Communication Networks (Amalfi, Italy, 2002).
• 11: Eiichiro Fujisaki , Tatsuaki Okamoto , David Pointcheval , Jacques Stern, RSA-OAEP Is Secure under the RSA Assumption, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.260-274, August 19-23, 2001
• 12: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 13: Stuart Haber , Benny Pinkas, Securely combining public-key cryptosystems, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502013]
• 14: HE, W., AND WU, T. Cryptanalysis and improvement of petersen-michels signcryption schemes. IEEE Computers and Digital Communications 146, 2 (1999), 123--124.
• 15: Markus Jakobsson , Julien P. Stern , Moti Yung, Scramble All, Encrypt Small, Proceedings of the 6th International Workshop on Fast Software Encryption, p.95-111, March 24-26, 1999
• 16: KOBARA, K., AND IMAI, H. OAEP++ : A very simple way to apply OAEP to deterministic OW-CPA primitives. Cryptology ePrint Archive, Report 2002/130, 2002.
• 17: KOMANO, Y., AND OHTA, K. Efficient universal padding techniques for multiplicative trapdoor one-way permutation. In Advances in Cryptology--CRYPTO 2003 (Santa Barbara, California, Aug. 2003).
• 18: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 19: MAO, W., AND MALONE-LEE, J. Two birds one stone: Signcryption using RSA. In Progress in Cryptology -- CT-RSA 2003 (San Francisco, California, Apr. 2003).
• 20: PETERSEN, H., AND MICHELS, M. Cryptanalysis and improvement of signcryption schemes. IEEE Computers and Digital Communications 145, 2 (1998), 140--151.
• 21: PIEPRZYK, J., AND POINTCHEVAL, D. Parallel authentication and public-key encryption. In Proc. 8th ACISP (Wollongong, Australia, July 2003).
• 22: Phillip Rogaway, Authenticated-encryption with associated-data, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586125]
• 23: RSA LABORATORIES. PKCS #1: RSA Encryption Standard. Version 1.5. Nov. 1993.
• 24: SHOUP, V. On formal models for secure key exchange. Cryptology ePrint Archive, Report 1999/012, 1999.
• 25: Victor Shoup, OAEP Reconsidered, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.239-259, August 19-23, 2001
• 26: Yuliang Zheng, Digital Signcryption or How to Achieve Cost(Signature & Encryption) << Cost(Signature) + Cost(Encryption), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.165-179, August 17-21, 1997
• 27: Yuliang Zheng , Hideki Imai, How to construct efficient signcryption schemes on elliptic curves, Information Processing Letters, v.68 n.5, p.227-233, Dec. 1998 [doi>10.1016/S0020-0190(98)00167-7]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Security, Theory

Keywords:
extractable commitments, feistel transform, joint signature and encryption, signcryption, universal padding schemes