Secrecy in Multiagent Systems

ABSTRACT

We introduce a general framework for reasoning about secrecy requirements in multiagent systems. Our definitions extend earlier definitions of secrecy and nondeducibility given by Shannon and Sutherland. Roughly speaking, one agent maintains secrecy with respect to another if the second agent cannot rule out any possibilities for the behavior or state of the first agent. We show that the framework can handle probability and nondeterminism in a clean way, is useful for reasoning about asynchronous systems as well as synchronous systems, and suggests generalizations of secrecy that may be useful for dealing with issues such as resource-bounded reasoning. We also show that a number of well-known attempts to characterize the absence of information flow are special cases of our definitions of secrecy.

REFERENCES

• 1: Chawla, S., Dwork, C., McSherry, F., Smith, A., and Wee, H. 2005. Towards privacy in public databases. Theory of Cryptography, To appear.
• 2: Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
• 3: Clark, D., Hunt, S., and Malacaria, P. 2002. Quantitative analysis of the leakage of confidential data. Electronic Notes in Theoretical Computer Science 59, 3. In Proceedings of the Workshop on Quantitative Aspects of Programming Languages (QAPL'01).
• 4: Ellis Cohen, Information transmission in computational systems, Proceedings of the sixth ACM symposium on Operating systems principles, p.133-139, November 16-18, 1977, West Lafayette, Indiana, United States
• 5: Alessandra Di Pierro , Chris Hankin , Herbert Wiklicky, Approximate Non-Interference, Proceedings of the 15th IEEE workshop on Computer Security Foundations, p.3, June 24-26, 2002
• 6: Emerson, E. A. 1983. Alternative semantics for temporal logics. Theor. Comput. Sci., 26, 121--130.
• 7: Kai Engelhardt , Ron van der Meyden , Yoram Moses, Knowledge and the logic of local propositions, Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, July 22-24, 1998, Evanston, Illinois
• 8: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 9: R. Fagin , Joseph Y. Halpern , Nimrod Megiddo, A logic for reasoning about probabilities, Information and Computation, v.87 n.1-2, p.78-128, July/August 1990 [doi>10.1016/0890-5401(90)90060-U]
• 10: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 11: Focardi, R. and Gorrieri, R. 1994. A classification of security properties for process algebra. J. Comput. Sci., 3, 1, 5--33.
• 12: Riccardo Focardi , Roberto Gorrieri, Classification of Security Properties (Part I: Information Flow), Revised versions of lectures given during the IFIP WG 1.7 International School on Foundations of Security Analysis and Design on Foundations of Security Analysis and Design: Tutorial Lectures, p.331-396, September 01, 2000
• 13: Gill, R. D., van der Laan, M., and Robins, J. 1997. Coarsening at random: Characterizations, conjectures and counter-examples. In Proceedings of the 1st Seattle Conference on Biostatistics. 255--294.
• 14: Goguen, J. A. and Meseguer, J. 1982. Security policies and security models. In Proceedings of the IEEE Symposium on Security and Privacy (SP'82). 11--20.
• 15: James W. Gray, III , Paul F. Syverson, A logical approach to multilevel security of probabilistic systems, Distributed Computing, v.11 n.2, p.73-90, April 1998 [doi>10.1007/s004460050043]
• 16: Grünwald, P. D. and Halpern, J. Y. 2003. Updating probabilities. J. Art. Intell. Res., 19, 243--278.
• 17: Halpern, J. Y. 2002. Characterizing the common prior assumption. J. Econ. Theory, 106, 2, 316--355.
• 18: Joseph Y. Halpern, Reasoning about Uncertainty, MIT Press, Cambridge, MA, 2003
• 19: Halpern, J. Y. and O'Neill, K. 2003. Anonymity and information hiding in multiagent systems. In Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW'03). 75--88.
• 20: Halpern, J. Y. and O'Neill, K. 2005. Secrecy in multiagent systems. Available at http://www.kevinoneill.org/papers.
• 21: Halpern, J. Y. and Pucella, R. 2003a. Modeling adversaries in a logic for security protocol analysis. In Proceedings of the Formal Aspects of Security (FASec'02). Lecture Notes in Computer Science, Volume 2629. Springer-Verlag, Berlin/Heidelberg/New York, 115--132.
• 22: Joseph Y. Halpern , Riccardo Pucella, Probabilistic algorithmic knowledge, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846258]
• 23: Joseph Y. Halpern , Mark R. Tuttle, Knowledge, probability, and adversaries, Journal of the ACM (JACM), v.40 n.4, p.917-960, Sept. 1993 [doi>10.1145/153724.153770]
• 24: Kyburg, H. 1983. Recent work in inductive logic. In Recent Work in Philosophy, T. Machan and K. Lucey, Eds. Rowman & Allanheld, Totowa, NJ. 87--150.
• 25: Gavin Lowe, Quantifying Information Flow, Proceedings of the 15th IEEE workshop on Computer Security Foundations, p.18, June 24-26, 2002
• 26: Heiko Mantel, Possibilistic Definitions of Security - An Assembly Kit, Proceedings of the 13th IEEE workshop on Computer Security Foundations, p.185, July 03-05, 2000
• 27: Mantel, H. 2003. A uniform framework for the formal specification and verification of information flow security. Ph.D. thesis, Universität des Saarlandes.
• 28: McCullough, D. 1987. Specifications for multi-level security and a hook-up property. In Proceedings of the IEEE Symposium on Security and Privacy (SP'87). 161--166.
• 29: John McLean, A General Theory of Composition for Trace Sets Closed under Selective Interleaving Functions, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.79, May 16-18, 1994
• 30: Ron van der Meyden, Common knowledge and update in finite environments, Information and Computation, v.140 n.2, p.115-157, Feb. 1, 1998 [doi>10.1006/inco.1997.2679]
• 31: John C. Mitchell , Ajith Ramanathan , Andre Scedrov , Vanessa Teague, A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols, Theoretical Computer Science, v.353 n.1, p.118-164, 14 March 2006 [doi>10.1016/j.tcs.2005.10.044]
• 32: Morris, S. 1995. The common prior assumption in economic theory. Econom. Philos., 11, 227--253.
• 33: Andrew C. Myers , Andrei Sabelfeld , Steve Zdancewic, Enforcing Robust Declassification, Proceedings of the 17th IEEE workshop on Computer Security Foundations, p.172, June 28-30, 2004 [doi>10.1109/CSFW.2004.9]
• 34: Kevin R. O'Neill , Michael R. Clarkson , Stephen Chong, Information-Flow Security for Interactive Programs, Proceedings of the 19th IEEE workshop on Computer Security Foundations, p.190-201, July 05-07, 2006 [doi>10.1109/CSFW.2006.16]
• 35: Rabin, M. O. 1982. n-process mutual exclusion with bounded waiting by 4·logn-valued shared variable. J. Comp. Syst. Sci., 25, 1, 66--75.
• 36: P Y A Ryan , S A Schneider, Process Algebra and Non-interference, Proceedings of the 12th IEEE workshop on Computer Security Foundations, p.214, June 28-30, 1999
• 37: P. Ryan , S. Schneider, The modelling and analysis of security protocols: the csp approach, Addison-Wesley Professional, 2000
• 38: Sabelfeld, A. and Myers, A. C. 2003. Language-based information-flow security. IEEE J. Select. Areas Comm., 21, 1, 5--19.
• 39: Steve Schneider , Abraham Sidiropoulos, CSP and Anonymity, Proceedings of the 4th European Symposium on Research in Computer Security: Computer Security, p.198-218, September 25-27, 1996
• 40: Shannon, C. E. 1949. Communication theory of secrecy systems. Bell System Tech. J., 28-4, 656--715.
• 41: Sutherland, D. 1986. A model of information. In Proceedings of the 9th National Security Conference. 175--183.
• 42: Moshe Y. Vardi, Automatic verification of probabilistic concurrent finite state programs, Proceedings of the 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), p.327-338, October 21-23, 1985 [doi>10.1109/SFCS.1985.12]
• 43: Wittbold, J. T. and Johnson, D. M. 1990. Information flow in nondeterministic systems. In Proceedings of the IEEE Symposium on Research in Security and Privacy (SP'90). 144--161.
• 44: A. Zakinthinos , E. S. Lee, A general theory of security properties, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.94, May 04-07, 1997

INDEX TERMS

Primary Classification:
  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, Theory

Keywords:
information flow, secrecy