Policy-hiding access control in open environment

ABSTRACT

In trust management and attribute-based access control systems, access control decisions are based on the attributes (rather than the identity) of the requester: Access is granted if Alice's attributes in her certificates satisfy Bob's access control policy. In this paper, we develop a policy-hiding access control scheme that protects both sensitive attributes and sensitive policies. That is, Bob can decide whether Alice's certified attribute values satisfy Bob's policy, without Bob learning any other information about Alice's attribute values or Alice learning Bob's policy. To enable policy-hiding access control, we introduce the notion of certified input private policy evaluation. Our construction uses Yao's scrambled circuit protocol and two new techniques introduced in this paper. One novel technique is constructing circuits with uniform topology that can compute arbitrary functions in a family. The other technique is committed-integer based oblivious transfer.

REFERENCES

• 1: M. Abadi , J. Feigenbaum, Secure circuit evaluation, Journal of Cryptology, v.2 n.1, p.1-12, 1990 [doi>10.1007/BF02252866]
• 2: S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
• 3: Dirk Balfanz , Glenn Durfee , Narendar Shankar , Diana Smetters , Jessica Staddon , Hao-Chi Wong, Secret Handshakes from Pairing-Based Key Agreements, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.180, May 11-14, 2003
• 4: Mihir Bellare , Silvio Micali, Non-Interactive Oblivious Transfer and Spplications, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.547-557, August 20-24, 1989
• 5: Matt Blaze , Joan Feigenbaum , Jack Lacy, Decentralized Trust Management, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.164, May 06-08, 1996
• 6: Sharon Boeyen, Tim Howes, and Patrick Richard. Internet X.509 Public Key Infrastructure LDAPc2 Schema. IETF RFC 2587, June 1999.
• 7: Fabrice Boudot. Efficient proofs that a committed number lies in an interval. In Advances in Cryptology: EUROCRYPT '00, volume 1807 of Lecture Notes in Computer Science, pages 431--444. Springer, May 2000.
• 8: Robert W. Bradshaw , Jason E. Holt , Kent E. Seamons, Concealing complex policies with hidden credentials, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030104]
• 9: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 10: Christian Cachin , Jan Camenisch, Optimistic Fair Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.93-111, August 20-24, 2000
• 11: Jan Camenisch , Els Van Herreweghen, Design and implementation of the idemix anonymous credential system, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586114]
• 12: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 13: Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 14: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 15: Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384047]
• 16: David Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM, v.28 n.10, p.1030-1044, Oct. 1985 [doi>10.1145/4372.4373]
• 17: David Chaum , Ivan Damgård , Jeroen van de Graaf, Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.87-119, August 16-20, 1987
• 18: Dwaine Clarke , Jean-Emile Elien , Carl Ellison , Matt Fredette , Alexander Morcos , Ronald L. Rivest, Certificate chain discovery in SPKI?SDSI, Journal of Computer Security, v.9 n.4, p.285-322, January 2001
• 19: Ronald Cramer , Ivan Damgård, Zero-Knowledge Proofs for Finite Field Arithmetic; or: Can Zero-Knowledge be for Free?, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.424-441, August 23-27, 1998
• 20: Claude Crépeau, Verifiable disclose for secrets and applications (abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.150-154, November 1990, Houthalen, Belgium
• 21: Glenn Durfee , Matt Franklin, Distribution chain security, Proceedings of the 7th ACM conference on Computer and communications security, p.63-70, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352610]
• 22: 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
• 23: Carl Ellison, Bill Frantz, Butler Lampson, Ron Rivest, Brian Thomas, and Tatu Ylonen. SPKI certificate theory. IETF RFC 2693, September 1999.
• 24: Stephen Farrell and Russell Housley. An internet attribute certificate profile for authorization. IETF RFC 3281, April 2002.
• 25: Keith Frikken , Mikhail Atallah , Jiangtao Li, Hidden access control policies with hidden credentials, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029186]
• 26: Juan Garay, Philip MacKenzie, and Ke Yang. Efficient and universally composable committed oblivious transfer and applications. In Theory of Cryptography, TCC 2004, volume 2951 of Lecture Notes in Computer Science, pages 297--316. Springer, 2004.
• 27: Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277716]
• 28: Oded Goldreich. Secure multi-party computation, October 2002.
• 29: Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003 [doi>10.1007/s00446-002-0077-1]
• 30: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 31: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 32: Jason E. Holt , Robert W. Bradshaw , Kent E. Seamons , Hilarie Orman, Hidden Credentials, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC [doi>10.1145/1005140.1005142]
• 33: Russell Housley, Warwick Ford, Tim Polk, and David Solo. Internet X.509 Public Key Infrastructure Certificate and CRL Profile. IETF RFC 2459, January 1999.
• 34: Jiangtao Li and Ninghui Li. OACerts: Oblivious attribute certificates. In Proceedings of the 3rd Conference on Applied Cryptography and Network Security (ACNS), volume 3531 of Lecture Notes in Computer Science. Springer, June 2005.
• 35: Jiangtao Li and Ninghui Li. Policy-hiding access control in open environment. Technical Report CERIAS-TR-2005-31, Center for Education and Research in Information Assurance and Security, Purdue University, May 2005.
• 36: Ninghui Li , Wenliang Du , Dan Boneh, Oblivious signature-based envelope, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.182-189, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872061]
• 37: Ninghui Li , John C. Mitchell , William H. Winsborough, Design of a Role-Based Trust-Management Framework, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.114, May 12-15, 2002
• 38: Ninghui Li , William H. Winsborough , John C. Mitchell, Distributed credential chain discovery in trust management, Journal of Computer Security, v.11 n.1, p.35-86, February 2003
• 39: Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. Fairplay -- secure two-party computation system. In Proceedings of the 13th USENIX Security Symposium, pages 287--302. USENIX, 2004.
• 40: Wenbo Mao, Guaranteed Correct Sharing of Integer Factorization with Off-Line Shareholders, Proceedings of the First International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.60-71, February 05-06, 1998
• 41: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 42: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 43: Ju P. Ofman. A universal automaton. Transactions of the Moscow Math Society, 14:200--215, 1965.
• 44: Joon S. Park and Ravi Sandhu. Smart certificates: Extending X.509 for secure attribute services on the web. In Proceedings of the 22nd National Information Systems Security Conference, October 1999.
• 45: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 46: Nicholas J. Pippenger. Generalized connectors. Technical Report RC-6532, IBM Res. Rep., 1977.
• 47: Ronald L. Rivest and Bulter Lampson. SDSI --- a simple distributed security infrastructure, October 1996. Available at: http://theory.lcs.mit.edu/~rivest/sdsi11.html.
• 48: Tomas Sander , Adam Young , Moti Yung, Non-Interactive CryptoComputing For NC1, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.554, October 17-18, 1999
• 49: Clark D. Thompson. Generalized connection networks for parallel processor intercommunication. IEEE Transactions on Computers, 27(12):1119--1125, December 1978.
• 50: Yiannis Tsiounis , Moti Yung, On the Security of ElGamal Based Encryption, Proceedings of the First International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.117-134, February 05-06, 1998
• 51: Wen-Guey Tzeng, Efficient 1-Out-n Oblivious Transfer Schemes, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.159-171, February 12-14, 2002
• 52: William H. Winsborough and Ninghui Li. Safety in automated trust negotiation. In Proceedings of the IEEE Symposium on Security and Privacy, pages 147--160, May 2004.
• 53: William H. Winsborough, Kent E. Seamons, and Vicki E. Jones. Automated trust negotiation. In DARPA Information Survivability Conference and Exposition, volume I, pages 88--102. IEEE Press, January 2000.
• 54: Yuanyuan Yang , Gerald M. Masson, The Necessary Conditions for Clos-Type Nonblocking Multicast Networks, IEEE Transactions on Computers, v.48 n.11, p.1214-1227, November 1999 [doi>10.1109/12.811110]
• 55: Andrew C. Yao. How to generate and exchange secrets. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 162--167. IEEE Computer Society Press, 1986.
• 56: Ting Yu , Marianne Winslett, A Unified Scheme for Resource Protection in Automated Trust Negotiation, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.110, May 11-14, 2003
• 57: Ting Yu , Marianne Winslett , Kent E. Seamons, Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation, ACM Transactions on Information and System Security (TISSEC), v.6 n.1, p.1-42, February 2003 [doi>10.1145/605434.605435]
• 58: Ellen Witte Zegura, Evaluating blocking probability in generalized connectors, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.387-398, Aug. 1995 [doi>10.1109/90.413213]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

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

General Terms:
Design, Security

Keywords:
access control, automated trust negotiation, cryptographic commitment, cryptographic protocol, digital credentials, evaluation, privacy, secure function