Databases Reference
In-Depth Information
On the Complexity of the Privacy Problem
in Databases
Bhavani Thuraisingham
University of Texas, Dallas, TX, USA
Summary.
This paper explores the complexity of the privacy problem. In particu-
lar the recursion theoretic properties of the privacy problem are examined. We view
the privacy problem as a form of inference problem in databases. We develop a theory
for the privacy problem based on deductive databases and then prove some prop-
erties of the problem. Essentially while our previous papers describe strategies and
approaches to handle the privacy problem as well as designs of privacy controllers
and privacy preserving data mining tools, this paper explores the foundations of the
privacy problem.
1 Introduction
As we have stated in our previous papers (see [THUR03a], [THUR03b],
[THUR03c] and [THUR03d]), privacy is about protecting information about
individuals. Privacy has been discussed a great deal in the past especially when
it relates to protecting medical information about patients. Social scientists
as well as technologists have been working on privacy issues. However, pri-
vacy has received enormous attention during the recent years. This is mainly
because of counter-terrorism and national security. For example in order to
extract information about various individuals and perhaps prevent and/or
detect potential terrorist attacks data mining tools are being examined. We
have heard a lot about national security vs. privacy in newspapers, magazines
and television talk shows. This is mainly due to the fact that people are now
realizing that to handle terrorism, the government may need to collect infor-
mation about individuals and mine this information. This is causing a major
concern with various civil liberties unions [THUR03a], [THUT03b]. Conse-
quently there is now much research on privacy preserving data mining that
attempts to maintain some level of privacy while carrying out data mining
[THUR05a], [THUR05b].
Our previous papers (see [THUR05c]) attempt to provide solutions to han-
dle the privacy problem. In particular, we described a system that enforces
