Towards a Practical Auditing Method for the Prevention of Statistical Database Compromise

In this paper we consider the applicability of an auditing method for preventing a statistical database compromise. In 1982 Chin and Oszoyoglu proposed Audit Expert for the prevention of database compromise using SUM queries. As originally proposed, Audit Expert was meant to be used dynamically and it was considered suitable only for small databases. In the static mode Audit Expert is much more efficient both in the storage and time required and so can be used for large databases as well as small ones. Moreover, in static mode it is possible to achieve maximum usability of the database. However, sometimes this will prevent the system from answering queries which are particularly important. In this paper we consider the inclusion of a limited number of user-posed queries and its impact on the usability. Then we say that the Audit Expert is used in a hybrid mode. We prove that mazimising usability in a general hybrid Audit Expert is NP-complete and isolate certain restricted cases when maximising usability is polynomial.