More Web Proxy on the site http://driver.im/

research-article

A Conceptual Framework for Secrecy-preserving Reasoning in Knowledge Bases

Authors:

Vasant HonavarAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 16, Issue 1

Article No.: 3, Pages 1 - 32

https://doi.org/10.1145/2637477

Published: 29 December 2014 Publication History

Abstract

In many applications, Knowledge Bases (KBs) contain confidential or private information (secrets). The KB should be able to use this secret information in its reasoning process but in answering user queries care must be exercised so that secrets are not revealed to unauthorized users. We consider this problem under the Open World Assumption (OWA) in a setting with multiple querying agents M₁,…, M_m that can pose queries against the KB K and selectively share answers that they receive from K with one or more other querying agents. We assume that for each M_i, the KB has a prespecified set of secrets S_i that need to be protected from M_i. Communication between querying agents is modeled by a communication graph, a directed graph with self-loops. We introduce a general framework and propose an approach to secrecy-preserving query answering based on sound and complete proof systems. The idea is to hide the truthful answer from a querying agent M_i by feigning ignorance without lying (i.e., to provide the answer ‘Unknown’ to a query q if it needs to be protected. Under the OWA, a querying agent cannot distinguish between the case that q is being protected (for reasons of secrecy) and the case that it cannot be inferred from K. In the pre-query stage we compute a set of envelopes E₁, …, E_m (restricted to a finite subset of the set of formulae that are entailed by K) so that S_i⊆ E_i, and a query α posed by agent M_i can be answered truthfully whenever α ∉ E_i and ¬ α ∉ E_i. After the pre-query stage, the envelope is updated as needed. We illustrate this approach with two simple cases: the Propositional Horn KBs and the Description Logic AL KBs.

References

[1]

Franz Baader. 2009. Description logics. In Reasoning Web: Semantic Technologies for Information Systems, 5th International Summer School 2009. Lecture Notes in Computer Science, Vol. 5689. Springer--Verlag, 1--39.

Digital Library

[2]

Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider (Eds.). 2003. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press.

Digital Library

[3]

Franz Baader, Martin Knechtel, and Rafael Peñaloza. 2009. A generic approach for large-scale ontological reasoning in the presence of access restrictions to the ontology’s axioms. In International Semantic WebConference (Lecture Notes in Computer Science), Abraham Bernstein, David R. Karger, Tom Heath, Lee Feigenbaum, Diana Maynard, Enrico Motta, and Krishnaprasad Thirunarayan (Eds.), Vol. 5823. Springer, 49--64.

Digital Library

[4]

Franz Baader and Ulrike Sattler. 2001. An overview of tableau algorithms for description logics. Studia Logica 69, 1 (2001), 5--40.

[5]

Jie Bao, Giora Slutzki, and Vasant Honavar. 2007. Privacy-preserving reasoning on the semantic web. In Web Intelligence. IEEE Computer Society, 791--797.

Digital Library

[6]

David E. Bell and Len LaPadula. 1974a. Secure Computer Systems. Technical Report ESD-TR-73-278, Vols. 1, 2. MITRE Corp., Bedford, MA.

[7]

David E. Bell and Len LaPadula. 1974b. Secure Computer Systems: A Mathematical Model. Technical Report ESD-TR-73-278, Vol. 2. MITRE Corp., Bedford, MA.

[8]

David E. Bell and Len LaPadula. 1974c. Secure Computer Systems: Mathematical Foundations. Technical Report ESD-TR-73-278, Vol. 1. MITRE Corp., Bedford, MA.

[9]

Elisa Bertino, L. R. Khan, Ravi S. Sandhu, and Bhavani M. Thuraisingham. 2006. Secure knowledge management: Confidentiality, trust, and privacy. IEEE Transactions on Systems, Man, and Cybernetics, Part A 36, 3 (2006), 429--438.

Digital Library

[10]

Joachim Biskup. 2011. History-dependent inference control of queries by dynamic policy adaption. In DBSecurity 106--121.

Digital Library

[11]

Joachim Biskup, Gabriele Kern-Isberner, and Matthias Thimm. 2008. Towards enforcement of confidentiality in agent interactions. In Proceedings of the 12th International Workshop on Non-Monotonic Reasoning (NMR’08). 104--112.

[12]

Joachim Biskup and Cornelia Tadros. 2012. Revising belief without revealing secrets. Foundations of Information and Knowledge Systems (2012), 51--70.

Digital Library

[13]

Joachim Biskup, Cornelia Tadros, and Lena Wiese. 2010. Towards controlled query evaluation for incomplete first-order databases. Foundations of Information and Knowledge Systems (2010), 230--247.

Digital Library

[14]

Joachim Biskup and Torben Weibert. 2008. Keeping secrets in incomplete databases. International Journal of Information Security 7, 3 (2008), 199--217.

Digital Library

[15]

Piero A. Bonatti, Claudiu Duma, Norbert Fuchs, Wolfgang Nejdl, Daniel Olmedilla, Joachim Peer, and Nahid Shahmehri. 2006. Semantic web policies - A discussion of requirements and research issues. In ESWC. 712--724.

Digital Library

[16]

Piero A. Bonatti and Daniel Olmedilla. 2007. Rule-based policy representation and reasoning for the semantic web. In Reasoning Web (LNCS), Vol. 4636. Springer, 240--268.

Digital Library

[17]

Piero A. Bonatti and Luigi Sauro. 2013. A confidentiality model for ontologies. In The Semantic Web--ISWC 2013. Springer, 17--32.

Digital Library

[18]

Stefan Borgwardt and Rafael Peñaloza. 2011. Description logics over lattices with multi-valued ontologies. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Vol. 2. AAAI Press, 768--773.

Digital Library

[19]

Sabrina De Capitani di Vimercati, Pierangela Samarati, and Sushil Jajodia. 2005. Policies, models, and languages for access control. In DNIS (Lecture Notes in Computer Science), Subhash Bhalla (Ed.), Vol. 3433. Springer, 225--237.

Digital Library

[20]

William F. Dowling and Jean H. Gallier. 1984. Linear-Time algorithms for testing the satisfiability of propositional horn formulae. Journal of Logical Programming 1, 3 (1984), 267--284.

[21]

Simon Godik and Tim Moses (ed.). 2002. OASIS eXtensible Access Control Markup Language (XACML). OASIS Committee Specification cs-xacml-specification-1.0, November 2002, Available at http://www.oasis-open.org/committees/xacml/. (2002).

[22]

Joseph A. Goguen and José Meseguer. 1982. Security policies and security models. In IEEE Symposium on Security and Privacy. 11--20.

[23]

James W. Gray and Paul F. Syverson. 1998. A logical approach to multilevel security of probabilistic systems. Distributed Computing 11, 2 (1998), 73--90.

Digital Library

[24]

Joseph Y. Halpern and Kevin R. O’Neill. 2008. Secrecy in multiagent systems. ACM Transactions on Information System Security 12, 1 (2008), 1--47.

Digital Library

[25]

Joseph Y. Halpern and Vicky Weissman. 2008. Using first-order logic to reason about policies. ACM Transactions on Information System Security 11, 4 (2008), 1--41.

Digital Library

[26]

I. Hodkinson, F. Wolter, and M. Zakharyaschev. 2000. Decidable fragments of first-order temporal logics. Annals of Pure and Applied logic 106, 1 (2000), 85--134.

[27]

Amit Jain and Csilla Farkas. 2006. Secure resource description framework: an access control model. In SACMAT. 121--129.

Digital Library

[28]

Sushil Jajodia. 1996. Database security and privacy. ACM Computing Survey 28, 1 (1996), 129--131.

Digital Library

[29]

Sushil Jajodia, Pierangela Samarati, Maria Luisa Sapino, and V. S. Subrahmanian. 2001. Flexible support for multiple access control policies. ACM Transactions on Database Systems 26, 2 (2001), 214--260.

Digital Library

[30]

Lalana Kagal, Tim Berners-Lee, Dan Connolly, and Daniel J. Weitzner. 2006. Using semantic web technologies for policy management on the web. In AAAI. AAAI Press.

Digital Library

[31]

Lalana Kagal, Timothy W. Finin, and Anupam Joshi. 2003. A policy based approach to security for the semantic web. In ISWC. 402--418.

[32]

Lalana Kagal, Massimo Paolucci, Naveen Srinivasan, Grit Denker, Timothy W. Finin, and Katia P. Sycara. 2004. Authorization and privacy for semantic web services. IEEE Intelligent Systems 19, 4 (2004), 50--56.

Digital Library

[33]

Vladimir Kolovski, James A. Hendler, and Bijan Parsia. 2007. Analyzing web access control policies. In WWW, Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-Schneider, and Prashant J. Shenoy (Eds.). ACM, 677--686.

Digital Library

[34]

Johann A. Makowsky. 1987. Why horn formulas matter in computer science: Initial structures and generic examples. Journal of Computer System Science 34, 2--3 (1987), 266--292.

Digital Library

[35]

John McLean. 1992. Proving noninterference and functional correctness using traces. Journal of Computer Security 1, 1 (1992), 37--58.

Digital Library

[36]

Sylvia Osborn, Ravi Sandhu, and Qamar Munawer. 2000. Configuring role-based access control to enforce mandatory and discretionary access control policies. ACM Transactions on Information System Security 3, 2 (2000), 85--106.

Digital Library

[37]

Manfred Schmidt-Schauß and Gert Smolka. 1991. Attributive concept descriptions with complements. Artificial Intelligence 48, 1 (1991), 1--26.

Digital Library

[38]

C. E. Shannon. 1949. Communication theory of secrecy systems. Bell Systems Technical Journal 28 (1949), 656--715.

[39]

George L. Sicherman, Wiebren de Jonge, and Reind P. van de Riet. 1983. Answering queries without revealing secrets. ACM Transactions on Database Systems 8, 1 (1983), 41--59.

Digital Library

[40]

S. Staab and R. Studer. 2009. Handbook on Ontologies. Springer.

Digital Library

[41]

Umberto Straccia. 2006. Description logics over lattices. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 14, 01 (2006), 1--16.

[42]

D. Sutherland. 1986. A model of information. In Proceedings of the 9th National Computer Security Conference, Vol. 247. 175--183.

[43]

Jia Tao, Giora Slutzki, and Vasant Honavar. 2010. Secrecy-preserving query answering for instance checking in EL. In RR. 195--203.

Digital Library

[44]

Gianluca Tonti, Jeffrey M. Bradshaw, Renia Jeffers, Rebecca Montanari, Niranjan Suri, and Andrzej Uszok. 2003. Semantic web languages for policy representation and reasoning: A comparison of kaos, rei, and ponder. In ISWC. 419--437.

[45]

Daniel J. Weitzner, Harold Abelson, Tim Berners-Lee, Joan Feigenbaum, James A. Hendler, and Gerald J. Sussman. 2008. Information accountability. Communications of the ACM 51, 6 (2008), 82--87.

Digital Library

[46]

Daniel J. Weitzner, Jim Hendler, Tim Berners-Lee, and Dan Connolly. 2005. Creating the policy-aware web: Discretionary, rules-based access for the world wide web. In Elena Ferrari and Bhavani Thuraisingham (editors), Web and Information Security, Elena Ferrari and Bhavani Thuraisingham (Eds.). Idea Group, Inc., Hershey, PA.

Cited By

Cima GLembo DRosati RSavo D(2024)Controlled Query Evaluation in Description Logics through Consistent Query AnsweringArtificial Intelligence10.1016/j.artint.2024.104176(104176)Online publication date: Jul-2024
https://doi.org/10.1016/j.artint.2024.104176
Zhu TYe DWang WZhou WYu P(2022)More Than Privacy: Applying Differential Privacy in Key Areas of Artificial IntelligenceIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.301424634:6(2824-2843)Online publication date: 1-Jun-2022
https://doi.org/10.1109/TKDE.2020.3014246
Lembo DRosati RSavo D(2019)Revisiting controlled query evaluation in description logicsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367243.3367286(1786-1792)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367243.3367286
Show More Cited By

Index Terms

A Conceptual Framework for Secrecy-preserving Reasoning in Knowledge Bases
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
    2. Knowledge representation and reasoning
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Theorem proving algorithms
2. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems

Recommendations

Secrecy-Preserving Query Answering in ELH Knowledge Bases
ICAART 2016: Proceedings of the 8th International Conference on Agents and Artificial Intelligence

In this paper we study Secrecy-Preserving Query Answering problem under Open World Assumption (OWA) for ELH Knowledge Bases (KBs). We employ two tableau procedures designed to compute some consequences of ABox (A) and TBox (T ) denoted by Aâ and T â ...
Topics in knowledge bases: epistemic ontologies and secrecy-preserving reasoning
OptiRef: Query Optimization for Knowledge Bases
WWW '23 Companion: Companion Proceedings of the ACM Web Conference 2023

Ontology-mediated query answering (OMQA) consists in asking database queries on a knowledge base (KB); a KB is a set of facts, the KB’s database, described by domain knowledge, the KB’s ontology.

FOL-rewritability is the main OMQA technique: it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 16, Issue 1

March 2015

246 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/2670130

Editor:
Dale Miller
INRIA Saclay, France

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 December 2014

Accepted: 01 June 2014

Revised: 01 May 2014

Received: 01 July 2013

Published in TOCL Volume 16, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
190
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cima GLembo DRosati RSavo D(2024)Controlled Query Evaluation in Description Logics through Consistent Query AnsweringArtificial Intelligence10.1016/j.artint.2024.104176(104176)Online publication date: Jul-2024
https://doi.org/10.1016/j.artint.2024.104176
Zhu TYe DWang WZhou WYu P(2022)More Than Privacy: Applying Differential Privacy in Key Areas of Artificial IntelligenceIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.301424634:6(2824-2843)Online publication date: 1-Jun-2022
https://doi.org/10.1109/TKDE.2020.3014246
Lembo DRosati RSavo D(2019)Revisiting controlled query evaluation in description logicsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367243.3367286(1786-1792)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367243.3367286
Garcia JMartinel NMicheloni CGardel A(2015)Person Re-Identification Ranking Optimisation by Discriminant Context Information AnalysisProceedings of the 2015 IEEE International Conference on Computer Vision (ICCV)10.1109/ICCV.2015.154(1305-1313)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.1109/ICCV.2015.154
Naumov PTao J(2015)Knowledge in communication networksJournal of Logic and Computation10.1093/logcom/exv080(exv080)Online publication date: 7-Dec-2015
https://doi.org/10.1093/logcom/exv080

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents