Multi-use unidirectional proxy re-signatures

ABSTRACT

In 1998, Blaze, Bleumer, and Strauss suggested a cryptographic primitive termed proxy re-signature in which a proxy transforms a signature computed under Alice's secret key into one from Bob on the same message. The proxy is only semi-trusted in that it cannot learn any signing key or sign arbitrary messages on behalf of Alice or Bob. At CCS 2005, Ateniese and Hohenberger revisited this primitive by providing appropriate security definitions and efficient constructions in the random oracle model. Nonetheless, they left open the problem of constructing a multi-use unidirectional scheme where the proxy is only able to translate in one direction and signatures can be re-translated several times. This paper provides the first steps towards efficiently solving this problem, suggested for the first time 10 years ago, and presents the first multi-hop unidirectional proxy re-signature schemes. Although our proposals feature a linear signature size in the number of translations, they are the first multi-use realizations of the primitive that satisfy the requirements of the Ateniese-Hohenberger security model. The first scheme is secure in the random oracle model. Using the same underlying idea, it readily extends into a secure construction in the standard model (i.e. the security proof of which avoids resorting to the random oracle idealization). Both schemes are computationally efficient but require newly defined Diffie-Hellman-like assumptions in bilinear groups.

REFERENCES

• 1: M. Abe, S. Fehr. Perfect NIZK with Adaptive Soundness. In TCC, pp. 118--136, 2007.
• 2: 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
• 3: G. Ateniese, K. Fu, M. Green, S. Hohenberger. Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage. In NDSS, 2005.
• 4: Giuseppe Ateniese , Kevin Fu , Matthew Green , Susan Hohenberger, Improved proxy re-encryption schemes with applications to secure distributed storage, ACM Transactions on Information and System Security (TISSEC), v.9 n.1, p.1-30, February 2006 [doi>10.1145/1127345.1127346]
• 5: Giuseppe Ateniese , Susan Hohenberger, Proxy re-signatures: new definitions, algorithms, and applications, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102161]
• 6: Mihir Bellare , Gregory Neven, Multi-signatures in the plain public-Key model and a general forking lemma, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180453]
• 7: M. Bellare, A. Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In CRYPTO, pp. 273--289, 2004.
• 8: M. Bellare, A. Palacio. Towards Plaintext-Aware Public-Key Encryption Without Random Oracles. In ASIACRYPT, pp. 48--62, 2004.
• 9: 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]
• 10: M. Blaze, G. Bleumer, M. Strauss. Divertible Protocols and Atomic Proxy Cryptography. In EUROCRYPT, pp. 127--144, 1998.
• 11: 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
• 12: D. Boneh, X. Boyen. Efficient selective-ID secure identity based encryption without random oracles. In EUROCRYPT, pp. 223--238, 2004.
• 13: 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
• 14: Ran Canetti , Susan Hohenberger, Chosen-ciphertext secure proxy re-encryption, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315269]
• 15: Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.229-235, August 20-24, 2000
• 16: Ivan Damgård, Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.445-456, August 11-15, 1991
• 17: A. Dent. The Hardness of the DHK Problem in the Generic Group Model. Cryptology ePrint Archive: report 2006/156.
• 18: Y. Dodis, A.-A. Ivan. Proxy Cryptography Revisited. In NDSS'03, 2003.
• 19: R. Granger, N. P. Smart. On Computing Products of Pairings. Cryptology ePrint Archive: Report 2006/172, 2006.
• 20: Matthew Green , Giuseppe Ateniese, Identity-Based Proxy Re-encryption, Proceedings of the 5th international conference on Applied Cryptography and Network Security, June 05-08, 2007, Zhuhai, China [doi>10.1007/978-3-540-72738-5_19]
• 21: Susan Hohenberger , Ronald L. Rivest, Advances in signatures, encryption, and e-cash from bilinear groups, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 22: S. Hohenberger, G. N. Rothblum, a. shelat, V. Vaikuntanathan. Securely Obfuscating Re-encryption. In TCC, pp. 233--252, 2007.
• 23: S. Kunz-Jacques, D. Pointcheval. About the Security of MTI/C0 and MQV. In SCN, pp. 156--172, 2006.
• 24: Benoît Libert , Damien Vergnaud, Multi-use unidirectional proxy re-signatures, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455835]
• 25: S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, B. Waters. Sequential Aggregate Signatures and Multisignatures Without Random Oracles. In EUROCRYPT, pp. 465--485, 2006.
• 26: Masahiro Mambo , Keisuke Usuda , Eiji Okamoto, Proxy signatures for delegating signing operation, Proceedings of the 3rd ACM conference on Computer and communications security, p.48-57, March 14-15, 1996, New Delhi, India [doi>10.1145/238168.238185]
• 27: M. Naor. On Cryptographic Assumptions and Challenges. In CRYPTO, pp. 96--109, 2003.
• 28: Thomas Ristenpart , Scott Yilek, The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks, Proceedings of the 26th annual international conference on Advances in Cryptology, p.228-245, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_13]
• 29: J. Shao, Z. Cao, L. Wang, X. Liang. Proxy Re-Signature Schemes without Random Oracles. In INDOCRYPT, pp. 197--209, 2007.
• 30: Claus-Peter Schnorr, Efficient Identification and Signatures for Smart Cards, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.239-252, August 20-24, 1989
• 31: B. Waters. Efficient Identity-Based Encryption Without Random Oracles. In EUROCRYPT, pp. 114--127, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Design, Security

Keywords:
digital signatures, multi-use proxy re-cryptography, unidirectionality