Abstract
This paper studies the notion of point-based 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 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.
Portions of this work were supported by Grants IIS-0325345, IIS-0219560, IIS-0312357, and IIS-0242421 from the National Science Foundation, Contract N00014-02-1-0364 from the Office of Naval Research, by sponsors of the Center for Education and Research in Information Assurance and Security, and by Purdue Discovery Park’s e-enterprise Center.
Chapter PDF
Similar content being viewed by others
References
Atallah, M.J., Du, W.: Secure multi-party computational geometry. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 165–179. Springer, Heidelberg (2001)
Atallah, M.J., Li, J.: Secure outsourcing of sequence comparisons. In: Martin, D., Serjantov, A. (eds.) PET 2004. LNCS, vol. 3424, pp. 63–78. Springer, Heidelberg (2005)
Ben-Or, M., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: The Twentieth Annual ACM Symposium on Theory of Computing (STOC), pp. 1–10. ACM Press, New York (1988)
Beth, T., Borcherding, M., Klein, B.: Valuation of trust in open networks. In: Gollmann, D. (ed.) ESORICS 1994. LNCS, vol. 875, pp. 3–18. Springer, Heidelberg (1994)
Bonatti, P.A., Samarati, P.: A uniform framework for regulating service access and information release on the web. Journal of Computer Security 10(3), 241–272 (2002)
Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Bradshaw, R., Holt, J., Seamons, K.: Concealing complex policies with hidden credentials. In: Proceedings of 11th ACM Conference on Computer and Communications Security (CCS) (October 2004)
Camenisch, J., Van Herreweghen, E.: Design and implementation of the idemix anonymous credential system. In: Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS), pp. 21–30 (2002)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Chaum, D.: Security without identification: transaction systems to make big brother obsolete. Communications of the ACM 28(10), 1030–1044 (1985)
Chaum, D., Crépeau, C., Damgard, I.: Multiparty unconditionally secure protocols. In: The twentieth annual ACM Symposium on Theory of Computing (STOC), pp. 11–19. ACM Press, New York (1988)
Chaum, D., Evertse, J.-H.: A secure and privacy-protecting protocol for transmitting personal information between organizations. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 118–167. Springer, Heidelberg (1987)
Chen, W., Clarke, L., Kurose, J., Towsley, D.: Optimizing cost-sensitive trust-negotiation protocols. In: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 2, pp. 1431–1442 (2005)
Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 360–363. Springer, Heidelberg (2001)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT Press, Cambridge (2001)
Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
Damiani, E., De Capitani di Vimercati, S., Paraboschi, S., Samarati, P., Violante, F.: A reputation-based approach for choosing reliable resources in peer-to-peer networks. In: ACM Conference on Computer and Communications Security (CCS 2002), pp. 207–216 (2002)
Du., W.: A study of several specific secure two-party computation problems, PhD thesis, Purdue University, West Lafayette, Indiana (2001)
Freedman, M., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
Frikken, K.B., Atallah, M.J.: Privacy preserving route planning. In: Proceedings of the 2004 ACM workshop on Privacy in the Electronic Society (WPES), pp. 8–15. ACM Press, New York (2004)
Frikken, K.B., Atallah, M.J., Li, J.: Hidden access control policies with hidden credentials. In: Proceedings of the 3nd ACM Workshop on Privacy in the Electronic Society (WPES) (October 2004)
Frikken, K.B., Li, J., Atallah, M.J.: Trust negotiation with hidden credentials, hidden policies, and policy cycles. In: Proceedings of the 13th Annual Network and Distributed System Security Symposium (NDSS) (2006)
Goldreich, O.: Secure multi-party computation (October 2002) (unpublished manuscript)
Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: The nineteenth annual ACM conference on theory of computing, pp. 218–229. ACM Press, New York (1987)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC), pp. 291–304 (1985)
Gruteser, M., Grunwald, D.: Anonymous usage of location-based services through spatial and temporal cloaking. In: ACM/USENIX International Conference on Mobile Systems, Applications, and Services (MobiSys) (2003)
Holt, J.E., Bradshaw, R.W., Seamons, K.E., Orman, H.: Hidden credentials. In: Proceedings of the 2nd ACM Workshop on Privacy in the Electronic Society (WPES) (October 2003)
Huang, Q., Jao, D., Wang, H.J.: Applications of secure electronic voting to automated privacy-preserving troubleshooting. In: Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS) (November 2005)
Jagannathan, G., Wright, R.N.: Privacy-preserving distributed k-means clustering over arbitrarily partitioned data. In: Proceeding of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 593–599 (2005)
Kissner, L., Song, D.: Private and threshold set-intersection. In: CRYPTO 2005 (2005)
Li, J., Li, N., Winsborough, W.H.: Automated trust negotiation using cryptographic credentials. In: Proceedings of 12th ACM Conference on Computer and Communications Security (CCS), pp. 46–57 (2005)
Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Tran, H., Hitchens, M., Varadharajan, V., Watters, P.: A trust based access control framework for P2P file-sharing systems. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS 2005) - Track 9, p. 302. IEEE Computer Society, Los Alamitos (2005)
Winsborough, W.H., Li, N.: Safety in automated trust negotiation. In: Proceedings of IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos (2004)
Winsborough, W.H., Seamons, K.E., Jones, V.E.: Automated trust negotiation. In: DARPA Information Survivability Conference and Exposition, vol. I, pp. 88–102. IEEE Press, Los Alamitos (2000)
Yankelovich, N., Walker, W., Roberts, P., Wessler, M., Kaplan, J., Provino, J.: Meeting central: making distributed meetings more effective. In: Proceedings of the 2004 ACM Conference on Computer Supported Cooperative Work (CSCW 2004), pp. 419–428. ACM Press, New York (2004)
Yao, A.C.: How to generate and exchange secrets. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 162–167. IEEE Computer Society Press, Los Alamitos (1986)
Yao, D., Frikken, K.B., Atallah, M.J., Tamassia, R.: Flexible, secure and private point-based trust management, Technical Report. Brown University (November 2005)
Yao, D., Tamassia, R., Proctor, S.: Privacy-preserving computation of trust with application to fuzzy location queries, Brown University Technical Report (March 2006)
Yu, T., Ma, X., Winslett, M.: PRUNES: An efficient and complete strategy for automated trust negotiation over the internet. In: Proceedings of the ACM Conference on Computer and Communications Security (CCS), November 2000, pp. 210–219 (2000)
Yu, T., Winslett, M.: A unified scheme for resource protection in automated trust negotiation. In: Proceedings of IEEE Symposium on Security and Privacy, pp. 110–122. IEEE Computer Society Press, Los Alamitos (2003)
Yu, T., Winslett, M., Seamons, K.E.: Interoperable strategies in automated trust negotiation. In: Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS 2001), pp. 146–155. ACM Press, New York (2001)
Zouridaki, C., Mark, B.L., Hejmo, M., Thomas, R.K.: A quantitative trust establishment framework for reliable data packet delivery in MANETs. In: Atluri, V., Ning, P., Du, W. (eds.) Proceedings of the Third ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN), pp. 1–10. ACM, New York (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yao, D., Frikken, K.B., Atallah, M.J., Tamassia, R. (2006). Point-Based Trust: Define How Much Privacy Is Worth. In: Ning, P., Qing, S., Li, N. (eds) Information and Communications Security. ICICS 2006. Lecture Notes in Computer Science, vol 4307. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11935308_14
Download citation
DOI: https://doi.org/10.1007/11935308_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49496-6
Online ISBN: 978-3-540-49497-3
eBook Packages: Computer ScienceComputer Science (R0)