Minimal Data Upgrading to Prevent Inference and Association Attacks

Summary: Formulates the minimal information reclassification problem: assign security levels to prevent inference and association attacks while minimizing unnecessary overclassification. Provides an algorithmic solution that's linear in simple instances, O(n^2) in general, and identifies an NP-hard variant. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1165
Venue: PODS
Year: 1999
Pagerank: 5.4328982e-05
Overall Rank: 8,403 | 42.35%
DOI: 10.1145/303976.303988

Incoming Non-self Citations Over Time

Authors

1. Steven Dawson (SRI International)
2. Sabrina De Capitani di Vimercati (University of Milan)
3. Patrick Lincoln (SRI International)
4. Pierangela Samarati (SRI International; University of Milan)

BibTeX Citation

@inproceedings{dawson_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Minimal Data Upgrading to Prevent Inference and Association Attacks}},
        url = {https://dl.acm.org/doi/10.1145/303976.303988},
        doi = {10.1145/303976.303988},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dawson, Steven and di Vimercati, Sabrina De Capitani and Lincoln, Patrick and Samarati, Pierangela},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,731	Secure XML Publishing without Information Leakage in the Presence of Data Inference	2004	VLDB	6.106721e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,659	Toward a Multilevel Secure Relational Data Model	1991	SIGMOD	0.00010079787
3,468	Security and Inference in Multilevel Database and Knowledge-Base Systems	1987	SIGMOD	7.3895239e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,695	Incrementally Maintaining Classification using an RDBMS	2011	VLDB
2	5,315	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD
3	3,174	On the Correctness Criteria of Fine-Grained Access Control in Relational Databases	2007	VLDB
4	9,070	Integrity-based Attacks for Encrypted Databases and Implications	2021	CIDR
5	5,731	Secure XML Publishing without Information Leakage in the Presence of Data Inference	2004	VLDB
6	2,017	Auditing Boolean Attributes	2000	PODS
7	9,838	Don’t Be a Tattle-Tale: Preventing Leakages through Data Dependencies on Access Control Protected Data	2022	VLDB
8	1,674	The Tao of Inference in Privacy-Protected Databases	2018	VLDB
9	7,115	Efficient Secure Query Evaluation over Encrypted XML Databases	2006	VLDB
10	3,468	Security and Inference in Multilevel Database and Knowledge-Base Systems	1987	SIGMOD