TL;DR
This dissertation tackles two key challenges in knowledge representation and reasoning: handling knowledge from multiple experts and protecting sensitive information in knowledge bases. It introduces novel algorithms for query answering in epistemic description logics and develops techniques for secrecy-preserving query answering in both single-agent and multi-agent settings under the open world assumption.
What Problem Does This Paper Address?
The paper addresses two main problems:
- Reasoning with Knowledge from Multiple Experts: In many real-world scenarios, knowledge comes from different sources or experts, and it's crucial to represent and reason about what each expert knows. Traditional description logics (DLs) struggle to capture this "epistemic" aspect of knowledge.
- Secrecy-Preserving Query Answering: As knowledge bases (KBs) become more prevalent in sensitive domains like healthcare and national security, there's a growing need to answer queries while protecting confidential information (secrets). Existing access control methods can be too restrictive, preventing the use of sensitive information even when it's possible to do so without compromising secrecy. The paper also considers the complexity of this problem in multi-agent systems where agents can share information, each with potentially different secrecy requirements.
Methods
The paper introduces several novel techniques:
- Epistemic Description Logics (ALCKm and ALCS4m): These logics extend the standard description logic ALC by incorporating modal operators to represent knowledge of different experts.
- Tableau Algorithms (Ax and As4): Sound and complete tableau algorithms are developed for query answering in ALCKm and ALCS4m knowledge bases with acyclic TBoxes. These algorithms are designed to be implementable in PSPACE.
- Secrecy-Preserving Query Answering (SPQA) Framework: A general framework is proposed for SPQA under the Open World Assumption (OWA). This framework aims to answer queries informatively while protecting secrets by "feigning ignorance" (answering "Unknown") when a truthful answer might reveal sensitive information.
- Secrecy Envelopes: The core idea for SPQA is to precompute "secrecy envelopes." These are sets of assertions that "disrupt" proofs of secrets, preventing an agent from deducing sensitive information. The paper focuses on computing "tight" envelopes, which are minimal in the sense that removing any part would compromise secrecy.
- EL Description Logic for SPQA: The SPQA framework is applied to the Description Logic EL, known for its computational tractability. Novel algorithms for computing tight envelopes in EL are presented, including a naive approach and an optimized procedure (TIGHT).
- Multi-Agent SPQA: The framework is extended to handle multiple querying agents who can communicate and share answers. This is modeled using a communication graph (a DAG), and the concept of individual secrecy envelopes for each agent is introduced.
- Horn KB for SPQA: The approach is illustrated with Propositional Horn Knowledge Bases, a computationally efficient class of KBs.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Epistemic DLs Offer a Solution for Expert Knowledge: By adding modal operators, DLs can effectively represent and reason about knowledge attributed to specific experts, opening up new possibilities for modeling complex information.
- OWA is Crucial for Secrecy: The Open World Assumption is essential for SPQA because it allows the system to answer "Unknown" when information is incomplete or when secrecy is being enforced, preventing agents from distinguishing between the two.
- Envelopes as a Proactive Secrecy Mechanism: Precomputing secrecy envelopes allows for more efficient and informative query answering compared to reactive, lazy evaluation methods, especially as query histories grow.
- Tight Envelopes Balance Informativeness and Secrecy: The concept of "tight" envelopes is key to maximizing informativeness while ensuring secrecy. Computing minimum envelopes is hard, but tight envelopes offer a practical compromise.
- Inverting Inference Rules for Envelope Construction: A novel technique of inverting inference rules is used to construct secrecy envelopes by identifying "disrupting" formulas.
- Multi-Agent Communication Graphs Model Information Flow: Using communication graphs effectively models how agents share information and how secrecy policies propagate in a multi-agent system.
Key Results
- PSPACE Algorithms for Epistemic DLs: Sound and complete tableau algorithms (Ax and As4) for ALCKm and ALCS4m are developed, with PSPACE implementations for query answering. This is a significant result, especially considering the higher complexity of general ALC with modal operators.
- Efficient SPQA Algorithms for EL: Algorithms for computing tight envelopes in EL are presented, with experimental results showing the optimized approach (TIGHT) to be significantly more efficient than the naive approach, especially for smaller TBoxes and secrecy sets.
- General Framework for Multi-Agent SPQA: A general framework for SPQA in multi-agent settings is introduced, with an illustration using Horn KBs.
- Theoretical Guarantees: The paper provides theoretical guarantees for the soundness and completeness of the proposed algorithms and the correctness of the secrecy envelopes.
Limitations and Future Work
- Complexity of Minimum Envelopes: Computing a minimum secrecy envelope is shown to be NP-hard, motivating the focus on tight envelopes.
- Finite Secrecy Sets: The current work assumes finite secrecy sets. Future work could explore relaxing this assumption to handle secrecy sets with finite descriptions expressible in a policy language.
- More Expressive Communication Graphs: The multi-agent framework could be extended to more realistic communication graphs, potentially with restrictions on information sharing (e.g., predicates on edges) or more general graph structures.
- Applying Framework to Other DLs: The multi-agent framework could be applied to other description logics, such as ALC.
- Automated Secret Specification: Developing strategies for automatically specifying secrets (policy specifications) and generating secrecy sets would be a valuable extension.
- Combining Probabilistic and Logical Approaches: The paper notes the potential for combining logical approaches with probabilistic methods for privacy-preserving query answering, especially in contexts involving statistical data.
Summary updated