Partitioning is an interesting approach to protecting statistical databases. It is highly secure and can, among other things, take into account the dynamics of a statistical database. This paper shows that partitioning often will either result in high information loss or in a serious distortion of important statistical functions. In order to make partitioning practical, these difficulties must be overcome.

Statistical databases aim to provide frequencies, averages, and other statistics about groups of persons (or organizations), while protecting the confidentiality of the individuals represented in the database. This objective is difficult to achieve, as users of statistical databases have a host of inference techniques at their disposal for retrieving information about identifiable persons (e.g., see [36,15,16,14,17,26, 31].) There are two broad categories of inference controls: controls that place restrictions on the set of allowable statistics, and controls that add noise to the data or to the released statistics. This paper focuses on restriction techniques.

The concept of multidimensional transformation of statistical databases is described. A given set of statistical output may be compatible with more than one statistical database. A transformed database D ' is a database which (1) differs from the original database D in its record content, but (2) produces, within certain limits, the same statistical output as the original database. For a transformable database D there are two options: One may physically transform D into a suitable database D ', or one may release only that output which will not permit the users to decide whether it comes from D or D '. The second way is, of course, the easier one. Basic structural requirements for transformable statistical databases are investigated. The closing section discusses advantages, drawbacks, and open questions.

To avoid trivial compromises, most on-line statistical databases refuse to answer queries for statistics about small subgroups. Previous research discovered a powerful snooping tool, the tracker, with which the answers to these unanswerable queries are easily calculated. However, the extent of this threat was not clear, for no one had shown that finding a tracker is guaranteed to be easy. This paper gives a simple algorithm for finding a tracker when the maximum number of identical records is not too large. The number of queries required to find a tracker is at most Ο (log 2 S ) queries, where S is the number of distinct records possible. Experimental results show that the procedure often finds a tracker with just a few queries. The threat posed by trackers is therefore considerable.

Statistical evaluation of databases which contain personal records may entail risks for the confidentiality of the individual records. The risk has increased with the availability of flexible interactive evaluation programs which permit the use of trackers, the most dangerous class of snooping tools known. A class of trackers, called union trackers, is described. They permit reconstruction of the entire database without supplementary knowledge and include the general tracker recently described as a special case. For many real statistical databases the overwhelming majority of definable sets of records will form trackers. For such databases a random search for a tracker is likely to succeed rapidly. Individual trackers are redefined and counted and their cardinalities are investigated. If there are n records in the database, then most individual trackers employ innocent cardinalities near n /3, making them difficult to detect. Disclosure with trackers usually requires little effort per retrieved data element.