Databases Reference
In-Depth Information
(u,v+2)
(0,u+v+2)
(u,v+1)
(0,u+v+1)
(u,v)
(0,u+v)
(0,u+1)
(0,2)
(u,2)
Privacy constraint is
assigned level
Private
(0,1)
(u,1)
Highly-Private Point
(u,0)
(0,0)
Fig. 6.
Multilevel privacy constraints
3 Summary and Directions
In this paper we have defined the notion of privacy function and gave the
formulation of the privacy problem in terms of the privacy function. Our
formulation of the privacy problem defines it as a decision problem for the
set of all non-privacy enhanced database designs. Furthermore, we obtain a
different set for each privacy level. We then stated and proved several proper-
ties of these sets based on recursive functions and computability theory. Our
ideas on privacy enhanced database designs as well as privacy constraints and
the development of privacy controllers were discussed in an earlier paper (see
[THUR05c]). In this paper we formalize our notions.
Our discussion of complexity is based on recursion theoretic complexity.
The next step is to examine the computational complexity. For example while
the general privacy problem is unsolvable (as we have shown in this paper),
can we find classes of problems that are solvable? What is the computational
complexity of the various classes of problems. When we say computational
complexity, we mean the space and time complexity as discussed by Blum
and others (see [BLUM67]). Can we obtain a characterization of the privacy
problem in terms of the computational complexity?
The work in this paper is just the first step toward exploring the founda-
tions of the privacy problem. There is still a lot to be done even for recursion
theoretic complexity. The major challenge will also be to obtain a characteri-
zation of the privacy problem in terms of computational complexity.
