Private Information: To Reveal or not to Reveal

ABSTRACT

This article studies the notion of quantitative policies for trust management and gives protocols for realizing them in a disclosure-minimizing fashion. Specifically, Bob values each credential with a certain number of points, and requires a minimum total threshold of points before granting Alice access to a resource. In turn, Alice values each of her credentials with a privacy score that indicates her degree of reluctance to reveal that credential. Bob's valuation of credentials and his threshold are private. Alice's privacy-valuation of her credentials is also private. Alice wants to find a subset of her credentials that achieves Bob's required threshold for access, yet is of as small a value to her as possible. We give protocols for computing such a subset of Alice's credentials without revealing any of the two parties' above-mentioned private information. Furthermore, we develop a fingerprint method that allows Alice to independently and easily recover the optimal knapsack solution, once the computed optimal value is given, but also enables verification of the integrity of the optimal value. The fingerprint method is useful beyond the specific authorization problem studied, and can be applied to any integer knapsack dynamic programming in a private setting.

REFERENCES

• 1: Mikhail J. Atallah , Wenliang Du, Secure Multi-party Computational Geometry, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.165-179, August 08-10, 2001
• 2: Atallah, M. J. and Li, J. 2004. Secure outsourcing of sequence comparisons. In Proceedings of the 4th Workshop on Privacy Enhancing Technologies (PET'04). Lecture Notes in Computer Science, vol. 3424. 63--78.
• 3: T. Aura, On the Structure of Delegation Networks, Proceedings of the 11th IEEE workshop on Computer Security Foundations, p.14, June 09-11, 1998
• 4: Tuomas Aura, Distributed access-rights management with delegation certificates, Secure Internet programming: security issues for mobile and distributed objects, Springer-Verlag, London, 2001
• 5: Nilanjan Banerjee , Arup Acharya , Sajal K. Das, Enabling SIP-based sessions in ad hoc networks, Wireless Networks, v.13 n.4, p.461-479, August 2007 [doi>10.1007/s11276-006-9200-8]
• 6: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 7: Thomas Beth , Malte Borcherding , Birgit Klein, Valuation of Trust in Open Networks, Proceedings of the Third European Symposium on Research in Computer Security, p.3-18, November 07-09, 1994
• 8: Piero A. Bonatti , Pierangela Samarati, A uniform framework for regulating service access and information release on the web, Journal of Computer Security, v.10 n.3, p.241-271, 2002
• 9: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 10: 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]
• 11: 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
• 12: 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]
• 13: Camp, L. J. and Wolfram, C. 2004. Pricing security. In Advances in Information Security -- Economics of Information Security. Vol. 12. Kluwer Academic Publishers, 17--34.
• 14: Canetti, R. 2000. Security and composition of multiparty cryptographic protocols. J. Crypto., 13(1), 143--202.
• 15: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 16: Chen, W., Clarke, L., Kurose, J., and Towsley, D. 2005. Optimizing cost-sensitive trust-negotiation protocols. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05). Vol. 2. 1431--1442.
• 17: Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, p.360-363, December 17-19, 2001
• 18: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 19: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 20: Ernesto Damiani , De Capitani di Vimercati , Stefano Paraboschi , Pierangela Samarati , Fabio Violante, A reputation-based approach for choosing reliable resources in peer-to-peer networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586138]
• 21: Danezis, G., Lewis, S., and Anderson, R. 2005. How much is location privacy worth? In Fourth Workshop on the Economics of Information Security (WEIS'05).
• 22: Wenliang Du , Mikhail J. Atallah , Eugene H. Spafford, A study of several specific secure two-party computation problems, Purdue University, West Lafayette, IN, 2001
• 23: Freedman, M., Nissim, K., and Pinkas, B. 2004. Efficient private matching and set intersection. In Advances in Cryptology (Eurocrypt'04). LNCS, vol. 3027. Springer-Verlag, 1--19.
• 24: Keith B. Frikken , Mikhail J. Atallah, Privacy preserving route planning, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029182]
• 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: Frikken, K. B., Li, J., and Atallah, M. J. 2006. Trust negotiation with hidden credentials, hidden policies, and policy cycles. In Proceedings of the 13th Annual Network and Distributed System Security Symposium (NDSS'06).
• 27: Goldreich, O. 2002. Secure multi-party computation. Unpublished manuscript.
• 28: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 29: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 30: Shafi Goldwasser, Multi party computations: past and present, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.1-6, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259405]
• 31: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 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: Qiang Huang , David Jao , Helen J. Wang, Applications of secure electronic voting to automated privacy-preserving troubleshooting, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102132]
• 34: Geetha Jagannathan , Rebecca N. Wright, Privacy-preserving distributed k-means clustering over arbitrarily partitioned data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081942]
• 35: Kissner, L. and Song, D. 2005. Private and threshold set-intersection. In Advances in Cryptology (CRYPTO'05).
• 36: Landwehr, C. E. 2004. Improving information flow in the information security market. In Advances in Information Security -- Economics of Information Security. Vol. 12. Kluwer Academic Publishers, 155--163.
• 37: Jiangtao Li , Ninghui Li , William H. Winsborough, Automated trust negotiation using cryptographic credentials, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102129]
• 38: Lipmaa, H. 2003. Verifiable homomorphic oblivious transfer and private equality test. In Advances in Cryptology (Asiacrypt'03). Lecture Notes in Computer Science. 416--433.
• 39: Paillier, P. 1999. Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology (EUROCRYPT'99), Lecture Notes in Computer Science 1592, 223--238.
• 40: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 41: Roberto Tamassia , Danfeng Yao , William H. Winsborough, Role-based cascaded delegation, Proceedings of the ninth ACM symposium on Access control models and technologies, June 02-04, 2004, Yorktown Heights, New York, USA [doi>10.1145/990036.990061]
• 42: Huu Tran , Michael Hitchens , Vijay Varadharajan , Paul Watters, A Trust based Access Control Framework for P2P File-Sharing Systems, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 9, p.302.3, January 03-06, 2005 [doi>10.1109/HICSS.2005.58]
• 43: Winsborough, W. H. and Li, N. 2004. Safety in automated trust negotiation. In Proceedings of IEEE Symposium on Security and Privacy (SP'04). IEEE Computer Society Press.
• 44: Winsborough, W. H., Seamons, K. E., and Jones, V. E. 2000. Automated trust negotiation. In DARPA Information Survivability Conference and Exposition (DARPA'00). Vol. I. IEEE Press, 88--102.
• 45: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]
• 46: Yao, D., Frikken, K. B., Atallah, M. J., and Tamassia, R. 2006. Point-based trust: Define how much privacy is worth. In Proceedings of the International Conference on Information and Communications Security (ICICS'06). LNCS, vol. 4307. Springer, 190--209.
• 47: Yao, D., Tamassia, R., and Proctor, S. 2007. Private distributed scalar product protocol with application to privacy-preserving computation of trust. In Proceedings of the IFIPTM Joint iTrust and PST Conferences on Privacy, Trust Management and Security (iTRUST'07).
• 48: Makoto Yokoo , Koutarou Suzuki, Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544770]
• 49: Ting Yu , Xiaosong Ma , Marianne Winslett, PRUNES: an efficient and complete strategy for automated trust negotiation over the Internet, Proceedings of the 7th ACM conference on Computer and communications security, p.210-219, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352633]
• 50: 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
• 51: Ting Yu , Marianne Winslett , Kent E. Seamons, Interoperable strategies in automated trust negotiation, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502004]
• 52: C. Zouridaki , B. L. Mark , M. Hejmo , R. K. Thomas, A quantitative trust establishment framework for reliable data packet delivery in MANETs, Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, November 07-07, 2005, Alexandria, VA, USA [doi>10.1145/1102219.1102222]

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)
          Subjects: Authentication

Keywords:
authorization, policies, secure multi-party computation