Confidentiality-preserving distributed proofs of conjunctive queries

ABSTRACT

Distributed proof construction protocols have been shown to be valuable for reasoning about authorization decisions in open distributed environments such as pervasive computing spaces. Unfortunately, existing distributed proof protocols offer only limited support for protecting the confidentiality of sensitive facts, which limits their utility in many practical scenarios. In this paper, we propose a distributed proof construction protocol in which the release of a fact's truth value can be made contingent upon facts managed by other principals in the system. We formally prove that our protocol can safely prove conjunctions of facts without leaking the truth values of individual facts, even in the face of colluding adversaries and fact release policies with cyclical dependencies. This facilitates the definition of context-sensitive release policies that enable the conditional use of sensitive facts in distributed proofs.

References

1. A. W. Appel and E. W. Felten. Proof-carrying authentication. In Proceedings of the Sixth ACM Conference on Computer and Communications Security, Nov. 1999.
2. L. Bauer, S. Garriss, and M. K. Reiter. Distributed proving in access-control systems. In Proceedings of the 2005 IEEE Symposium on Security and Privacy, pages 81--95, 2005.
3. E. Bertino, E. Ferrari, and A. C. Squicciarini. Trust-X: A peer-to-peer framework for trust establishment. IEEE Transactions on Knowledge and Data Engineering, 16(7):827--842, July 2004.
4. P. Bonatti and P. Samarati. Regulating service access and information release on the web. In Proceedings of the Seventh ACM Conference on Computer and Communications Security, pages 134--143, 2000.
5. D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. SIAM Journal of Computing, 32(3):586--615, 2003.
6. S. A. Brands. Rethinking Public Key Infrastructure and Digital Certificates. MIT Press, Cambridge, MA, USA, 2000.
7. J. DeTreville. Binder, a logic-based security language. In Proceedings of the 2002 IEEE Symposium on Security and Privacy, page 105, 2002.
8. D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography. In STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 542--552, New York, NY, USA, 1991. ACM.
9. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryptography Conference, pages 265--284, Mar. 2006.
10. T. Elgamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469--472, 1985.
11. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the 19th annual ACM Conference on Theory of Computing, pages 218--229, New York, NY, USA, 1987. ACM Press.
12. A. Ivan and Y. Dodis. Proxy cryptography revisited. In Proceedings of the 10th Annual Network and Distributed System Security Symposium (NDSS 2003), Feb. 2003.
13. T. Kohno, A. Broido, and K. Claffy. Remote physical device fingerprinting. IEEE Transactions on Dependable and Secure Computing, 2(2):93--108, 2005.
14. A. J. Lee, K. Minami, and N. Borisov. Confidentiality-preserving distributed proofs of conjunctive queries (extended version). Department of Computer Science Technical Report TR-08-161, University of Pittsburgh, Dec. 2008.
15. A. J. Lee, K. Minami, and M. Winslett. Lightweight consistency enforcement schemes for distributed proofs with hidden subtrees. In Proceedings of the 12th ACM Symposium on Access Control Models and Technologies, pages 101--110, 2007.
16. A. J. Lee and M. Winslett. Enforcing safety and consistency constraints in policy-based authorization systems. ACM Transactions on Information and System Security, to appear.
17. K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. Mondrian multidimensional k-anonymity. In Proceedings of the 22nd International Conference on Data Engineering (ICDE), Apr. 2006.
18. J. Li and N. Li. A construction for general and efficient oblivious commitment based envelope protocols. In Proceedings of 8th International Conference on Information and Communications Security (ICICS), pages 122--138, Dec. 2006.
19. J. Li and N. Li. OACerts: oblivious attribute certificates. IEEE Transactions on Dependable and Secure Computing (TDSC), 3(4):340--352, Oct. 2006.
20. J. Li, N. Li, and W. H. Winsborough. Automated trust negotiation using cryptographic credentials. ACM Transactions on Information and System Security, to appear.
21. A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. In Proceedings of the 22nd International Conference on Data Engineering (ICDE), Apr. 2006.
22. K. Minami and D. Kotz. Secure context-sensitive authorization. Journal of Pervasive and Mobile Computing, 1(1):123--156, Mar. 2005.
23. A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets (how to break anonymity of the Netflix prize dataset). In Proceedings of 29th IEEE Symposium on Security and Privacy, May 2008.
24. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proceedings of EUROCRYPT---Advances in Cryptology, 1999.
25. M. Prabhakaran and M. Rosulek. Cryptographic complexity of multi-party computation problems: Classifications and separations. Electronic Colloquium on Computational Complexity (ECCC), 15(50), 2008.
26. L. Sweeney. k-anonymity: A model for protecting privacy. International Journal on Uncertainty, Fuzziness and Kowledge-based Systems, 10(5):557--570, 2002.
27. W. H. Winsborough and N. Li. Towards practical automated trust negotiation. In Proceedings of the Third IEEE International Workshop on Policies for Distributed Systems and Networks, pages 92--103, June 2002.
28. W. H. Winsborough, K. E. Seamons, and V. E. Jones. Automated trust negotiation. In Proceedings of the DARPA Information Survivability Conference and Exposition, pages 88--102, Jan. 2000.
29. M. Winslett, C. C. Zhang, and P. A. Bonatti. PeerAccess: a logic for distributed authorization. In Proceedings of the 12th ACM Conference on Computer and Communications Security, pages 168--179, 2005.
30. X. Xiao and Y. Tao. m-invariance: Towards privacy preserving re-publication of dynamic datasets. In Proceedings of the ACM Conference on Management of Data (SIGMOD), pages 689--700, June 2007.
31. T. Yu, M. Winslett, and K. E. Seamons. Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation. ACM Transactions on Information and System Security, 6(1):1--42, Feb. 2003.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Security and privacy

  • Security services

    • Access control

    • Authentication

  • Systems security

    • Operating systems security

• Social and professional topics

  • Computing / technology policy

    • Computer crime

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles