Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Collaborative Planning with Confidentiality

  • Published:
Journal of Automated Reasoning Aims and scope Submit manuscript

Abstract

Collaboration among organizations or individuals is common.While these participants are often unwilling to share all their information with each other, some information sharing is unavoidable when achieving a common goal. The need to share information and the desire to keep it confidential are two competing notions which affect the outcome of a collaboration. This paper proposes a formal model of collaboration which addresses confidentiality concerns. We draw on the notion of a plan which originates in the AI literature. We use data confidentiality policies to assess confidentiality in transition systems whose actions have an equal number of predicates in their pre- and post-conditions. Under two natural notions of policy compliance, we show that it is PSPACE-complete to schedule a plan leading from a given initial state to a desired goal state while simultaneously deciding compliance with respect to the agents’ policies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Alur, R., Černý, P., Chaudhuri, S.: Model checking on trees with path equivalences. In: TACAS 2007, pp. 664–678. Springer (2007)

  2. Alur, R., Černý, P., Zdancewic, S.: Preserving secrecy under refinement. In: ICALP ’06: Proceedings (Part II) of the 33rd International Colloquium on Automata, Languages and Programming, pp. 107–118. Springer (2006)

  3. Ashley, P., Hada, S., Karjoth, G., Powers, C., Schunter, M.:Enterprise privacy authorization language (EPAL 1.2) (2003). http://www.zurich.ibm.com/security/enterprise-privacy/epal/Specification/index.html

  4. Barh, A., Mitchell, J.C., Datta, A., Sundaram, S.: Privacy and utility in business processes. In: 20th IEEE Computer Security Foundations Symposium (CSF 20). Venice, Italy (2007)

  5. Barth, A., Datta, A., Mitchell, J.C., Nissenbaum, H.: Privacy and conextual integrity: framework and applications. In: 27th IEEE Symposium on Security and Privacy (2006)

  6. Bibel, W.: A deductive solution for plan generation. New Gener. Comput. 4(2), 115–132 (1986)

    Article  MATH  Google Scholar 

  7. Cervesato, I., Durgin, N., Kanovich, M., Scedrov, A.: Interpreting strands in linear logic. In: Veith, H., Heintze, N., Clark, E. (eds.) 2000 Workshop on Formal Methods and Computer Security—FMCS’00. Chicago, IL (2000)

  8. Cervesato, I., Scedrov, A.: Relating state-based and process-based concurrency through linear logic. In: de Queiroz, R. (ed.) Thirteenth Workshop on Logic, Language, Information and Computation—WoLLIC’06, Stanford, CA, 18–21 July, pp. 145–176. Elsevier ENTCS 165 (2006)

  9. Cervesato, I., Scedrov, A.: Relating state-based and process-based concurrency through linear logic (full-version). Inf. Comput. 207(10), 1044–1077 (2009)

    Article  MATH  Google Scholar 

  10. Chapman, D.: Planning for conjunctive goals. Artif. Intell. 32(3), 333–377 (1987)

    Article  MATH  Google Scholar 

  11. Dolev, D., Yao, A.: On the security of public key protocols. IEEE Trans. Inf. Theory 29(2), 198–208 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  12. Durgin, N., Lincoln, P., Mitchell, J., Scedrov, A.: Multiset rewriting and the complexity of bounded security protocols. J. Comput. Secur. 12(2), 247–311 (2004)

    Google Scholar 

  13. Garg, D., Bauer, L., Bowers, K.D., Pfenning, F., Reiter, M.K.: A linear logic of authorization and knowledge. In: Proceedings of the 11th European Symposium on Research in Computer Science (ESORICS’06). Springer Lecture Notes in Computer Science, vol. 4189, pp. 297–312. Springer-Verlag (2006)

  14. Garg, D., Pfenning, F.: Non-interference in constructive authorization logic. In: Proc. of the IEEE Computer Security Foundations Workshop (CSFW), pp. 283–296 (2006)

  15. Gehlot, V., Gunter, C.: Normal process representatives. In: Proc. of the Fifth Annual IEEE Symposium on Logic in Computer Science, pp. 200–207. Philadelphia, PA (1990)

  16. Girard, J.-Y.: Linear logic. Theor. Comp. Sci. 50(1), 1–102 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  17. Girard, J.-Y.: Linear logic: Its syntax and semantics. In: Girard, J.-Y., Lafont, Y., Regnier, L. (eds.) Advances in Linear Logic. London Mathematical Society Lecture Notes, vol. 222, pp. 1–42. Cambridge University Press (1995)

  18. Goguen, J.A., Meseguer, J.: Security policies and security models. In: IEEE Symposium on Security and Privacy, pp. 11–20 (1982)

  19. Greenstadt, R., Pierce, J.P., Tambe, M.: Analysis of privacy loss in distributed constraint optimization. In: 21st Conference on Artificial Intelligence (AAAI). Boston, MA (2006)

  20. Greenstadt, R., Smith, M.D.: Collaborative scheduling: threats and promises. In: Fifth Annual Workshop on Economics and Information Security. Cambridge, England (2006)

  21. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Longman Publishing Co., Inc., Boston, MA (2001)

    MATH  Google Scholar 

  22. Ives, Z.G., Khandelwal, N., Kapur, A., Cakir, M.: ORCHESTRA: Rapid, collaborative sharing of dynamic data. In: Conference on Innovative Data Systems Research (CIDR), pp. 107–118 (2005)

  23. Jones, N.D., Landweber, L.H., Lien, Y.E.: Complexity of some problems in Petri nets. Theor. Comp. Sci. 4(3), 277–299 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  24. Kanovich, M., Rowe, P., Scedrov, A.: Collaborative planning with privacy. In: 20th IEEE Computer Security Foundations Symposium (CSF 20). Venice, Italy (2007)

  25. Kanovich, M., Rowe, P., Scedrov, A.: Policy compliance in collaborative systems. In: 22nd IEEE Computer Security Foundations Symposium (CSF22), pp. 218–233. Port Jefferson, NY (2009)

  26. Kanovich, M., Vauzeilles, J.: The classical AI planning problems in the mirror of Horn linear logic: semantics, expressibility, complexity. Math. Struct. Comput. Sci. 11(6), 689–716 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kanovich, M.I.: Horn programming in linear logic is NP-complete. In: Proc. 7-th Annual IEEE Syposium on Logic in Computer Science, Santa Cruz, pp. 200–210 (1992)

  28. Kanovich, M.I.: The complexity of Horn fragments of linear logic. Ann. Pure Appl. Logic 69, 195–241 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  29. Kanovich, M.I.: Linear logic as a logic of computations. Ann. Pure Appl. Logic 67, 183–212 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  30. Kanovich, M.I.: The direct simulation of Minsky machines in linear logic. In: Girard, J.-Y., Lafont, Y., Regnier, L. (eds.) Advances in Linear Logic. London Mathematical Society Lecture Notes, vol. 222, pp. 123–145 (1995)

  31. Kanovich, M.I.: Petri nets, Horn programs, linear logic and vector games. Ann. Pure Appl. Logic 75(1-2), 107–135 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  32. Li, M., Vitanyi, P.: An introduction to Kolmogorov complexity and its applications. Springer, New York (1997)

    MATH  Google Scholar 

  33. Lincoln, P.D., Shankar, N.: Proof search in first-order linear logic and other cut-free sequent calculi. In: Ninth Annual Symposium on Logic in Computer Science (Paris, France), pp. 282–291. IEEE Computer Society Press (1994)

  34. Masseron, M., Tollu, C., Vauzeilles, J.: Generating plans in linear logic I: actions as proofs. Theor. Comp. Sci. 113(2), 349–370 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  35. Mayr, E.W.: An algorithm for the general Petri net reachability problem. SIAM J. Comput. 13(3), 441–460 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  36. McDermott, D., Hendler, J.: Planning: what it is, what it could be, An introduction to the special issue on planning and scheduling. Artif. Intell. 76, 1–16 (1995)

    Article  Google Scholar 

  37. McLean, J.: Security models. In: Marciniak, J. (ed.) Encyclopedia of Software Engineering. Wiley (1994)

  38. Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. In: Selected Papers of the Second Workshop on Concurrency and Compositionality, pp. 73–155. Elsevier Science Publishers Ltd. Essex (1992)

  39. Myers, A.C., Sabelfeld, A., Zdancewic, S.: Enforcing robust declassification and qualified robustness. J. Comput. Secur. 14(2), 157–196 (2006). Extended abstract in CSFW, pp. 172–186 (2004)

    Google Scholar 

  40. Nilsson, N.J.: Principles of Artificial Intelligence. Springer, Berlin (1980)

    MATH  Google Scholar 

  41. Papadimitriou, C.: Computational Complexity. Addison-Wesley Publishing Company, Inc., Reading, MA (1994)

    MATH  Google Scholar 

  42. Reagle, J., Cranor, L.F.: The platform for privacy preferences. Commun. ACM 42(2), 48–55 (1999)

    Article  Google Scholar 

  43. Reynolds, J.C.: Syntactic control of interference. In: Symposium on Principles of Programming Languages (POPL), pp. 39–46 (1978)

  44. Rowe, P.: Policy Compliance, Confidentiality and Complexity in Collaborative Systems. PhD thesis, University of Pennsylvania (2009)

  45. Savitch, W.J., Relationship between nondeterministic and deterministic tape classes. J. Comput. Syst. Sci. 4, 177–192 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  46. Scedrov, A.: Linear logic and computation: A survey. In: Schwichtenberg, H. (ed.) Proof and Computation, Proceedings Marktoberdorf Summer School 1993, pp. 281–298. NATO Advanced Science Institutes, Series F, Springer-Verlag, Berlin (1994)

    Google Scholar 

  47. Taylor, N.E., Ives, Z.G.: Reconciling while tolerating disagreement in collaborative data sharing. In: ACM SIGMOD Conference on Management of Data, pp. 13–24 (2006)

  48. Wiederhold, G., Bilello, M., Sarathy, V., Qian, X.: Protecting collaboration. In: Proc. 19th NIST-NCSC National Information Systems Security Conference, pp. 561–569 (1996)

  49. Zdancewic, S., Myers, A.C.: Robust declassification. In: Proc. 14th IEEE Computer Securtiy Foundations Workshop (CSFW), pp. 15–23 (2001)

Download references

Author information

Authors and Affiliations

  1. Queen Mary, University of London, London, UK

    Max Kanovich

  2. The MITRE Corporation, Bedford, MA, USA

    Paul Rowe

  3. University of Pennsylvania, Philadelphia, PA, USA

    Andre Scedrov

Authors
  1. Max Kanovich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul Rowe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andre Scedrov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Max Kanovich.

Additional information

Research partially supported by OSD/ONR CIP/SW URI “Software Quality and Infrastructure Protection for Diffuse Computing” through ONR Grant N00014-01-1-0795, OSD/ONR CIP/SW URI “Trustworthy Infrastructure, Mechanisms, and Experimentation for Diffuse Computing” through ONR Grant N00014-04-1-0725, by ONR Grant N00014-07-1-1039, by OSD/AFOSR MURI “Collaborative policies and assured information sharing”, and by EPSRC Grant EP/D053625/1 “Modularity and Resource Separation”. Additional support from NSF Grants CNS-0429689, CNS-0524059, and CNS-0830949. Rowe’s affiliation with The MITRE Corporation is provided for identification purposes only, and is not intended to convey or imply MITRE’s concurrence with, or support for, the positions, opinions or viewpoints expressed by the author. Most of the work was done while Rowe was PhD student at the University of Pennsylvania. Approved for Public Release: 10-1569.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kanovich, M., Rowe, P. & Scedrov, A. Collaborative Planning with Confidentiality. J Autom Reasoning 46, 389–421 (2011). https://doi.org/10.1007/s10817-010-9190-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10817-010-9190-1

Keywords

Search

Navigation