Giora Slutzki Awarded NSF Grant for Secrecy Preserving Reasoning

October 11, 2011

Professor Slutzki has been recently awarded a National Science Foundation grant titled "Secrecy-Preserving Reasoning: Foundations, Algorithms, and Software". The award is for a total of about $450,000 over three years. 

Much of current research in the area of the Semantic Web aims at developing theoretical foundations as well as algorithms for secrecy-preserving reasoning within the context of Knowledge Bases (KBs). A secrecy set being just a set of assertions, the goal of secrecy-preserving reasoning is to provide maximum possible reasoning services while making sure that secret information is not compromised. 

In our research we assume that the KBs are expressed in some language based on Description Logics (DLs, decidable fragments of 1st order logic). A key novel idea is to exploit the indistinguishability (from the querying agent's point of view) between secret information and incomplete information under the Open World Semantics. To this end we utilize the idea of computing small "secrecy envelopes" so that answering UNKNOWN to assertions inside the envelope while answering queries outside the envelope truthfully, constitutes a secrecy-preserving reasoning method. We have developed a novel approach to computing secrecy envelopes. It is based on the idea of inverting the tableau expansion rules used by the KB. At the fundamental level the idea is simple: if a consequence of an inference rule must be secret, so must be at least one of its premises. 

For a simple (but quite useful) class of DLs we have shown that although finding the optimum envelope is NP-complete, minimal envelope can be computed in polynomial time. Some immediate goals of this research are to extend these results to (1) more powerful DLs, and (2) multi-agent environments. 

This research is done jointly with Ph.D. student Jia Tao and professor Vasant Honavar.