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: Andrew W. Appel , Edward W. Felten, Proof-carrying authentication, Proceedings of the 6th ACM conference on Computer and communications security, p.52-62, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319718]
• 2: Lujo Bauer , Scott Garriss , Michael K. Reiter, Distributed Proving in Access-Control Systems, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.81-95, May 08-11, 2005 [doi>10.1109/SP.2005.9]
• 3: Trust-X: A Peer-to-Peer Framework for Trust Establishment, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.827-842, July 2004 [doi>10.1109/TKDE.2004.1318565]
• 4: Piero Bonatti , Pierangela Samarati, Regulating service access and information release on the Web, Proceedings of the 7th ACM conference on Computer and communications security, p.134-143, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352620]
• 5: 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]
• 6: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 7: John DeTreville, Binder, a Logic-Based Security Language, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.105, May 12-15, 2002
• 8: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 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 , 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]
• 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: Tadayoshi Kohno , Andre Broido , K. C. Claffy, Remote Physical Device Fingerprinting, IEEE Transactions on Dependable and Secure Computing, v.2 n.2, p.93-108, April 2005 [doi>10.1109/TDSC.2005.26]
• 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: Adam J. Lee , Kazuhiro Minami , Marianne Winslett, Lightweight cnsistency enforcement schemes for distributed proofs with hidden subtrees, Proceedings of the 12th ACM symposium on Access control models and technologies, June 20-22, 2007, Sophia Antipolis, France [doi>10.1145/1266840.1266856]
• 16: Adam J. Lee , Marianne Winslett, Enforcing Safety and Consistency Constraints in Policy-Based Authorization Systems, ACM Transactions on Information and System Security (TISSEC), v.12 n.2, p.1-33, December 2008 [doi>10.1145/1455518.1455520]
• 17: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 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: Jiangtao Li , Ninghui Li, OACerts: Oblivious Attribute Certificates, IEEE Transactions on Dependable and Secure Computing, v.3 n.4, p.340-352, October 2006 [doi>10.1109/TDSC.2006.54]
• 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: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 22: Kazuhiro Minami , David Kotz, Secure context-sensitive authorization, Pervasive and Mobile Computing, v.1 n.1, p.123-156, March 2005 [doi>10.1016/j.pmcj.2005.01.004]
• 23: Arvind Narayanan , Vitaly Shmatikov, Robust De-anonymization of Large Sparse Datasets, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.111-125, May 18-21, 2008 [doi>10.1109/SP.2008.33]
• 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: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 27: N. Li , W. Winsborough, Towards Practical Automated Trust Negotiation, Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks (POLICY'02), p.92, June 05-07, 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: Marianne Winslett , Charles C. Zhang , Piero A. Bonatti, PeerAccess: a logic for distributed authorization, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102144]
• 30: Xiaokui Xiao , Yufei Tao, M-invariance: towards privacy preserving re-publication of dynamic datasets, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247556]
• 31: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls; Authentication

  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:
Security

Keywords:
consistency, distributed proof, pervasive computing