1983/03/01 by Wiebren de Jonge · 1 citation
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Cryptography and Data Security
paper · pdf · doi:10.1145/319830.319834
openalex publication_date 1983/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
This paper describes how to compromise a statistical database which only answers queries about arithmetic means for query sets whose cardinality falls in the range [ k, N - k ], for some k > 0, where N ≥ 2 k is the number of records in the database. The compromise is shown to be easy and to require only a little preknowledge; knowing the cardinality of just one nonempty query set is usually sufficient. This means that not only count and sum queries, but also queries for arithmetic means can be extremely dangerous for the security of a statistical database, and that this threat must be taken into account explicitly by protective measures. This seems quite important from a practical standpoint: while arithmetic means were known for some time to be not altogether harmless, the (perhaps surprising) extent of the threat is now shown.