Understanding database reconstruction attacks on public data

Abstract

These attacks on statistical databases are no longer a theoretical danger.

References

1. Adam, N.R., Worthmann, J.C. Security-control methods for statistical databases: A comparative study. ACM Computing Surveys 21, 4 (1989), 515--556
2. Biere, A. PicoSAT essentials. J. Satisfiability, Boolean Modeling and Computation 4, (2008), 75--97; https://bit.ly/2QcziqW
3. Blum, A., Dwork, C., McSherry, F. Nissim, K. Practical privacy: The SuLQ framework. In Proceedings of the 24^th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2005, 128--138; https://dl.acm.org/citation.cfm?id=1065184.
4. Dinur, I., Nissim, K. Revealing information while preserving privacy. In Proceedings of the 22^nd ACM SIGMOD-SIGACT-SIGART Principles of Database Systems, 2003, 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 3^rd Conference on Theory of Cryptography, 2006, 265--284. Springer-Verlag, Berlin, Heidelberg
6. Dwork, C., Nissim, K. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of the 24^th International Cryptology Conference 3152, 2004, 528--544. Springer Verlag, Santa Barbara, CA; https://bit.ly/2zKunmJ
7. Heule, M.J.H., Kullmann, O. The science of brute force. Commun. ACM 60, 8 (Aug. 2017), 70--79
8. Kleinberg, J., Papadimitriou, C., Raghavan, P. Auditing Boolean attributes. In Proceedings of the 19^th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000, 86--91
9. Kong, S., Malec, D. Cook-Levin theorem. Lecture, University of Wisconsin, 2007.
10. Marques-Silva, J., Lynce, I., Malik, S. Conflict-driven clause learning SAT solvers. Handbook of Satisfiability, 131--153. IOS Press, Amsterdam, The Netherlands, 2009.
11. McCarthy, J. Recursive functions of symbolic expressions and their computation by machine, part I. Commun. ACM 3, 4 (Apr. 1960), 184--195; https://dl.acm.org/citation.cfm?id=367199.
12. Metin, H., Baarir, S., Colange, M., Kordon, F. CDCLSym: Introducing effective symmetry breaking in SAT solving. Tools and Algorithms for the Construction and Analysis of Systems. D. Beyer and M. Huisman, eds. Springer International Publishing, 2018, 99--114; https://link.springer.com/chapter/10.1007/978-3-319-89960-2_6.
13. Tamura, N., Taga, A., Kitagawa, S., Banbara, M. Compiling finite linear CSP into SAT. Contraints 14, 2 (2009), 254--272; https://dl.acm.org/citation.cfm?id=1527316; http://bach.istc.kobe-u.ac.jp/sugar/.
14. Whitney, C.R. Jeanne Calment, world's elder, dies at 122. New York Times (Aug. 5, 1997); https://nyti.ms/2kM4oFb.
15. Zayatz, L., Lucero, J., Massell, P., Ramanayake, A. 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

  • Database and storage security

    • Database activity monitoring

    • Management and querying of encrypted data