Understanding Database Reconstruction Attacks on Public Data: These attacks on statistical databases are no longer a theoretical danger.

Abstract

With the dramatic improvement in both computer speeds and the efficiency of SAT and other NP-hard solvers in the last decade, DRAs on statistical databases are no longer just a theoretical danger. The vast quantity of data products published by statistical agencies each year may give a determined attacker more than enough information to reconstruct some or all of a target database and breach the privacy of millions of people. Traditional disclosure-avoidance techniques are not designed to protect against this kind of attack.

References

1. Adam, N.R., Worthmann, J.C. 1989. Security-control methods for statistical databases: A comparative study. ACM Computing Surveys 21(4), 515-556).
2. Biere, A. 2008. PicoSAT essentials. Journal on Satisfiability, Boolean Modeling and Computation 4, 75-97; https://pdfs.semanticscholar.org/7ea4/cdd0003234f9e98ff5a080d9191c398e26c2.pdf.
3. Blum, A., Dwork, C., McSherry, F., Nissim, K. 2005. Practical privacy: the SuLQ framework. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 128-138; https://dl.acm.org/citation.cfm?id=1065184.
4. Dinur, I., Nissim, K. 2003. Revealing information while preserving privacy. In Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Principles of Database Systems, 202-210; https://dl.acm.org/citation.cfm?id=773173.
5. Dwork, C., McSherry, F., Nissim, K., Smith, A. 2006. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, 265-284. Berlin, Heidelberg: Springer-Verlag.
6. Dwork, C., Nissim, K. 2004. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of the 24th International Cryptology Conference 3152, 528-544. Santa Barbara, California: Springer Verlag; https://www.microsoft.com/en-us/research/publication/privacy-preserving-datamining-on-vertically-partitioned-databases/.
7. Heule, M.J.H., Kullmann, O. 2017. The science of brute force. Communications of the ACM 60(8), 70-79.
8. Kleinberg, J., Papadimitriou, C., Raghavan, P. 2000. Auditing Boolean attributes. In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 86-91.
9. Kong, S., Malec, D. 2007. Cook-Levin theorem. Lecture, University of Wisconsin.
10. Marques-Silva, J., Lynce, I., Malik, S. 2009. Conflict-driven clause learning SAT solvers. In Handbook of Satisfiability, 131-153. Amsterdam, The Netherlands: IOS Press.
11. McCarthy, J. 1960. Recursive functions of symbolic expressions and their computation by machine, part I. Communications of the ACM 3(4), 184-195; https://dl.acm.org/citation.cfm?id=367199.
12. Metin, H., Baarir, S., Colange, M., Kordon, F. 2018. CDCLSym: Introducing effective symmetry breaking in SAT solving. In Tools and Algorithms for the Construction and Analysis of Systems, ed. D. Beyer and M. Huisman, 99-114. Springer International Publishing; https://link.springer.com/chapter/10.1007/978-3-319-89960-2_6.
13. Tamura, N., Taga, A., Kitagawa, S., Banbara, M. 2009. Compiling finite linear CSP into SAT. Contraints 14(2), 254-272; https://dl.acm.org/citation.cfm?id=1527316; http://bach.istc.kobe-u.ac.jp/sugar/.
14. Whitney, C.R. 1997. Jeanne Calment, world's elder, dies at 122. New York Times (August 5); https://nyti.ms/2kM4oFb.
15. Zayatz, L., Lucero, J., Massell, P., Ramanayake, A. 2009. Disclosure avoidance for Census 2010 and American Community Survey five-year tabular data products. Statistical Research Division, U.S. Census Bureau; https://www.census.gov/srd/CDAR/rrs2009-10_ACS_5yr.pdf.

Index Terms

• Security and privacy

  • Human and societal aspects of security and privacy

• Social and professional topics

  • Computing / technology policy

    • Privacy policies