Proxy re-signatures: new definitions, algorithms, and applications

ABSTRACT

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed proxy re-signatures, in which a semi-trusted proxy acts as a translator between Alice and Bob. To translate, the proxy converts a signature from Alice into a signature from Bob on the same message. The proxy, however, does not learn any signing key and cannot sign arbitrary messages on behalf of either Alice or Bob. Since the BBS proposal, the proxy re-signature primitive has been largely ignored, but we show that it is a very useful tool for sharing web certificates, forming weak group signatures, and authenticating a network path.We begin our results by formalizing the definition of security for a proxy re-signature. We next substantiate the need for improved schemes by pointing out certain weaknesses of the original BBS proxy re-signature scheme which make it unfit for most practical applications. We then present two secure proxy re-signature schemes based on bilinear maps. Our first scheme relies on the Computational Diffie-Hellman (CDH) assumption; here the proxy can translate from Alice to Bob and vice-versa. Our second scheme relies on the CDH and 2-Discrete Logarithm (2-DL) assumptions and achieves a stronger security guarantee -- the proxy is only able to translate in one direction. Constructing such a scheme has been an open problem since proposed by BBS in 1998. Furthermore in this second scheme, even if the delegator and the proxy collude, they cannot sign on behalf of the delegatee. Both schemes are efficient and secure in the random oracle model.

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: Giuseppe Ateniese, Kevin Fu, Matthew Green, and Susan Hohenberger. Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage. In Network and Distributed System Security Symposium, pages 29--43, 2005.
• 3: Giuseppe Ateniese and Susan Hohenberger. Proxy Re-Signatures: New Definitions, Algorithms, and Applications. Cryptology ePrint Archive, 2005. http://eprint.iacr.org/2005.
• 4: Mihir Bellare , Gregory Neven, Transitive Signatures Based on Factoring and RSA, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.397-414, December 01-05, 2002
• 5: Matt Blaze, G. Bleumer, and M. Strauss. Divertible protocols and atomic proxy cryptography. In Advances in Cryptology -- EUROCRYPT '98, volume 1403 of LNCS, pages 127--144, 1998.
• 6: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 7: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 8: Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures. In Advances in Cryptology -- EUROCRYPT '03, volume 2656 of LNCS, pages 416--432, 2003.
• 9: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Journal of Cryptology, v.17 n.4, p.297-319, September 2004 [doi>10.1007/s00145-004-0314-9]
• 10: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 11: Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Advances in Cryptology --- CRYPTO 2004, volume 3152 of LNCS, pages 56--72, 2004.
• 12: Yevgeniy Dodis and Anca Ivan. Proxy cryptography revisited. In Network and Distributed System Security Symposium, February 2003.
• 13: Yevgeniy Dodis , Leonid Reyzin, Breaking and repairing optimistic fair exchange from PODC 2003, Proceedings of the 3rd ACM workshop on Digital rights management, October 27-27, 2003, Washington, DC, USA [doi>10.1145/947380.947387]
• 14: Steven D. Galbraith , Keith Harrison , David Soldera, Implementing the Tate Pairing, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.324-337, July 07-12, 2002
• 15: 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]
• 16: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 17: Ari Juels, David Molnar, and David Wagner. Security and privacy issues in e-passports. To appear in IEEE SecureComm, 2005.
• 18: M. Mambo, K. Usuda, and E. Okamoto. Proxy signatures: delegation of the power to sign messages. IEICE Trans. Fundamentals, E79-A(9), 1996.
• 19: Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502017]
• 20: Silvio Micali , Ronald L. Rivest, Transitive Signature Schemes, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.236-243, February 18-22, 2002
• 21: K. Ohta and T. Okamoto. Multisignature schemes secure against active insider attacks. IEICE Trans. Fundamentals, E82-A/1:21--31, 1999.
• 22: Tatsuaki Okamoto, A digital multisignature scheme using bijective public-key cryptosystems, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.432-441, Nov. 1988 [doi>10.1145/48012.48246]
• 23: Claus-Peter Schnorr. Efficient signature generation by smart cards. Journal of Cryptography, 4:161--174, 1991.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Keywords:
authenticating path in network, bilinear maps, proxy re-signature