Improved proxy re-encryption schemes with applications to secure distributed storage

ABSTRACT

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed an application called atomic proxy re-encryption, in which a semitrusted proxy converts a ciphertext for Alice into a ciphertext for Bob without seeing the underlying plaintext. We predict that fast and secure re-encryption will become increasingly popular as a method for managing encrypted file systems. Although efficiently computable, the wide-spread adoption of BBS re-encryption has been hindered by considerable security risks. Following recent work of Dodis and Ivan, we present new re-encryption schemes that realize a stronger notion of security and demonstrate the usefulness of proxy re-encryption as a method of adding access control to a secure file system. Performance measurements of our experimental file system demonstrate that proxy re-encryption can work effectively in practice.

REFERENCES

• 1: 104th United States Congress. 1996. Health Insurance Portability and Accountability Act of 1996 (HIPPA). http://aspe.hhs.gov/admnsimp/pl104191.htm; Last access: August 16, 2004.
• 2: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844130]
• 3: 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
• 4: Ateniese, G., Fu, K., Green, M., and Hohenberger, S. 2005. Improved proxy re-encryption schemes with applications to secure distributed storage. In Proceedings of the 12th Annual Network and Distributed System Security Symposium. Internet Society, 29--44.
• 5: 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
• 6: Matt Blaze, A cryptographic file system for UNIX, Proceedings of the 1st ACM conference on Computer and communications security, p.9-16, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168590]
• 7: Blaze, M., Bleumer, G., and Strauss, M. 1998. Divertible protocols and atomic proxy cryptography. In Proceedings of Eurocrypt '98. Vol. 1403. 127--144.
• 8: 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]
• 9: 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
• 10: Boneh, D., Gentry, C., Lynn, B., and Shacham, H. 2003. Aggregate and verifiably encrypted signatures. In Proceedings of Eurocrypt '03. Vol. 2656 of LNCS. 416--432.
• 11: Bresson, E., Catalano, D., and Pointcheval, D. 2003. A simple public-key cryptosystem. In Proceedings of Asiacrypt '03. Vol. 2894 of LNCS. 37--54.
• 12: Cheon, J. H. and Lee, D. H. 2001. Diffie-Hellman problems and bilinear maps. Cryptology ePrint Archive: Report 2002/117.
• 13: Ronald Cramer , Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.45-64, May 02, 2002
• 14: Dodis, Y., Franklin, M. K., Katz, J., Miyaji, A., and Yung, M. 2003. Intrusion-resilient public-key encryption. In Proceedings of CT-RSA '03. Vol. 2612 of LNCS. 19--32.
• 15: Dodis, Y., Franklin, M. K., Katz, J., Miyaji, A., and Yung, M. 2004. A generic construction for intrusion-resilient public-key encryption. In Proceedings of CT-RSA '04. Vol. 2964 of LNCS. 81--98.
• 16: Dodis, Y. and Ivan, A. 2003. Proxy cryptography revisited. In Proceedings of the Tenth Network and Distributed System Security Symposium.
• 17: Dodis, Y. and Yampolskiy, A. 2005. A verifiable random function with short proofs an keys. In Public Key Cryptography. Vol. 3386 of LNCS. 416--431.
• 18: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Key-Insulated Public Key Cryptosystems, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.65-82, May 02, 2002
• 19: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 20: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 21: Fu, K. 1999. Group sharing and random access in cryptographic storage file systems. M.S. thesis, Massachusetts Institute of Technology, Cambridge, MA.
• 22: Fu, K. 2005. Integrity and access control in untrusted content distribution networks. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA.
• 23: Kevin Fu , M. Frans Kaashoek , David Mazières, Fast and secure distributed read-only file system, ACM Transactions on Computer Systems (TOCS), v.20 n.1, p.1-24, February 2002 [doi>10.1145/505452.505453]
• 24: Eiichiro Fujisaki , Tatsuaki Okamoto, Secure Integration of Asymmetric and Symmetric Encryption Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.537-554, August 15-19, 1999
• 25: 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
• 26: Goh, E.-J., Shacham, H., Modadugu, N., and Boneh, D. 2003. SiRiUS: Securing remote untrusted storage. In Proceedings of the Tenth Network and Distributed System Security Symposium. 131--145.
• 27: Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. Journal of Computer and System Sciences 28, 2, 270--299.
• 28: Golle, P., Jakobsson, M., Juels, A., and Syverson, P. F. 2004. Universal re-encryption for mixnets. In Proceedings of CT-RSA '04. Vol. 2964 of LNCS. 163--178.
• 29: Anthony Harrington , Christian Jensen, Cryptographic access control in a distributed file system, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775432]
• 30: Markus Jakobsson, On Quorum Controlled Asymmetric Proxy Re-encryption, Proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography, p.112-121, March 01-03, 1999
• 31: 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
• 32: Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 33: Li, J., Krohn, M. N., Mazières, D., and Shasha, D. 2004. Secure untrusted data repository (SUNDR). In Proceedings of the 6th Symposium on Operating Systems Design and Implementation. San Francisco, CA, 91--106.
• 34: Mambo, M. and Okamoto, E. 1997. Proxy cryptosystems: Delegation of the power to decrypt ciphertexts. IEICE Trans. Fund. Electronics Communications and Computer Science E80-A/1, 54--63.
• 35: Perlman, R. and Kaufman, C. 2001. PDM: A new strong password-based protocol. In Proceedings of the 10th USENIX Security Symposium.
• 36: Reed, D. and Svobodova, L. 1981. Swallow: A distributed data storage system for a local network. In Local Networks for Computer Communications, A. West and P. Janson, Eds. North-Holland, Amsterdam, 355--373.
• 37: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 38: Schnorr, C.-P. 1991. Efficient signature generation by smart cards. Journal of Cryptography 4, 161--174.
• 39: Scott, M. 2005. MIRACL library. Indigo Software. http://indigo.ie/~mscott/#download.
• 40: Shoup, V. 1997. Lower bounds of discrete logarithms and related problems. In Proceedings of Eurocrypt '97. Vol. 1233 of LNCS. 256--266.
• 41: Yuliang Zheng, Signcryption and Its Applications in Efficient Public Key Solutions, Proceedings of the First International Workshop on Information Security, p.291-312, September 17-19, 1997
• 42: Zhou, L., Marsh, M. A., Schneider, F. B., and Redz, A. 2004. Distributed blinding for ElGamal re-encryption. Tech. Rep. 2004--1924, Cornell Computer Science Department, Ithaca, NY.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Keywords:
Proxy re-encryption, bilinear maps, double decryption, key translation