{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T04:08:55Z","timestamp":1759205335239,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>We present a novel definition of privacy in the framework of offline (retroactive) database query auditing. Given information about the database, a description of sensitive data, and assumptions about users' prior knowledge, our goal is to determine if answering a past user's query could have led to a privacy breach. According to our definition, an audited property<jats:italic>A<\/jats:italic>is private, given the disclosure of property<jats:italic>B<\/jats:italic>, if no user can gain confidence in<jats:italic>A<\/jats:italic>by learning<jats:italic>B<\/jats:italic>, subject to prior knowledge constraints. Privacy is not violated if the disclosure of<jats:italic>B<\/jats:italic>causes a loss of confidence in<jats:italic>A<\/jats:italic>. The new notion of privacy is formalized using the well-known semantics for reasoning about knowledge, where logical properties correspond to sets of possible worlds (databases) that satisfy these properties. Database users are modeled as either possibilistic agents whose knowledge is a set of possible worlds, or as probabilistic agents whose knowledge is a probability distribution on possible worlds.<\/jats:p><jats:p>We analyze the new privacy notion, show its relationship with the conventional approach, and derive criteria that allow the auditor to test privacy efficiently in some important cases. In particular, we prove characterization theorems for the possibilistic case, and study in depth the probabilistic case under the assumption that all database records are considered a-priori independent by the user, as well as under more relaxed (or absent) prior-knowledge assumptions. In the probabilistic case we show that for certain families of distributions there is no efficient algorithm to test whether an audited property<jats:italic>A<\/jats:italic>is private given the disclosure of a property<jats:italic>B<\/jats:italic>, assuming<jats:italic>P<\/jats:italic>\u2260<jats:italic>NP<\/jats:italic>. Nevertheless, for many interesting families, such as the family of product distributions, we obtain algorithms that are efficient both in theory and in practice.<\/jats:p>","DOI":"10.1145\/1870103.1870105","type":"journal-article","created":{"date-parts":[[2010,12,22]],"date-time":"2010-12-22T14:41:31Z","timestamp":1293028891000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Epistemic privacy"],"prefix":"10.1145","volume":"58","author":[{"given":"Alexandre","family":"Evfimievski","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Ronald","family":"Fagin","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"David","family":"Woodruff","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]}],"member":"320","published-online":{"date-parts":[[2010,12,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog0901_7"},{"volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04)","author":"Agrawal R.","key":"e_1_2_1_2_1","unstructured":"Agrawal , R. , Bayardo , R. J. , Faloutsos , C. , Kiernan , J. , Rantzau , R. , and Srikant , R . 2004. Auditing compliance with a hippocratic database . In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04) . 516--527. Agrawal, R., Bayardo, R. J., Faloutsos, C., Kiernan, J., Rantzau, R., and Srikant, R. 2004. Auditing compliance with a hippocratic database. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04). 516--527."},{"volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02)","author":"Agrawal R.","key":"e_1_2_1_3_1","unstructured":"Agrawal , R. , Kiernan , J. , Srikant , R. , and Xu , Y . 2002. Hippocratic databases . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02) . 143--154. Agrawal, R., Kiernan, J., Srikant, R., and Xu, Y. 2002. Hippocratic databases. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02). 143--154."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-48.3.385"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00536201"},{"key":"e_1_2_1_6_1","volume-title":"Australian privacy act of","author":"Australia","year":"1998","unstructured":"Australia . 1998. Australian privacy act of 1998 . http:\/\/www.privacy.gov.au\/ACT\/privacyact. Australia. 1998. Australian privacy act of 1998. http:\/\/www.privacy.gov.au\/ACT\/privacyact."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/954092.954101"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/7228"},{"key":"e_1_2_1_11_1","volume-title":"2nd Session, 36th Parliament, 48-49 Elizabeth II","author":"Canada 0.","year":"1999","unstructured":"Canada . 200 0. Personal information protection and electronic documents act . 2nd Session, 36th Parliament, 48-49 Elizabeth II , 1999 --2000, Statutes of Canada . Canada. 2000. Personal information protection and electronic documents act. 2nd Session, 36th Parliament, 48-49 Elizabeth II, 1999--2000, Statutes of Canada."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.5.409"},{"key":"e_1_2_1_13_1","unstructured":"Caramanis C. 2001. Non-convex optimization via real algebraic geometry. http:\/\/web.mit. edu\/~cmcaram\/www\/pubs\/nonconvex_opt_review.pdf. Caramanis C. 2001. Non-convex optimization via real algebraic geometry. http:\/\/web.mit. edu\/~cmcaram\/www\/pubs\/nonconvex_opt_review.pdf."},{"key":"e_1_2_1_14_1","first-page":"409","article-title":"Elements of Information Theory. 2nd Ed. Wiley-Interscience","volume":"12","author":"Cover T. M.","year":"2006","unstructured":"Cover , T. M. , and Thomas , J. A. 2006 . Elements of Information Theory. 2nd Ed. Wiley-Interscience , Chapter 12 , 409 -- 425 . Cover, T. M., and Thomas, J. A. 2006. Elements of Information Theory. 2nd Ed. Wiley-Interscience, Chapter 12, 409--425.","journal-title":"Chapter"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.02.005"},{"volume-title":"Proceedings of the 4th International Symposium on Imprecise Probabilities and Their Applications.","author":"de Campos C. P.","key":"e_1_2_1_16_1","unstructured":"de Campos , C. P. , and Cozman , F. G . 2005. Computing lower and upper expectations under epistemic independence . In Proceedings of the 4th International Symposium on Imprecise Probabilities and Their Applications. de Campos, C. P., and Cozman, F. G. 2005. Computing lower and upper expectations under epistemic independence. In Proceedings of the 4th International Symposium on Imprecise Probabilities and Their Applications."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"volume-title":"Proceedings of the 24th International Conference on Cryptology (CRYPTO). 528--544","author":"Dwork C.","key":"e_1_2_1_18_1","unstructured":"Dwork , C. , and Nissim , K . 2004. Privacy-preserving datamining on vertically partitioned databases . In Proceedings of the 24th International Conference on Cryptology (CRYPTO). 528--544 . Dwork, C., and Nissim, K. 2004. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of the 24th International Conference on Cryptology (CRYPTO). 528--544."},{"key":"e_1_2_1_19_1","first-page":"281","article-title":"Directive 95\/46\/EC on the protection of individuals with regard to the processing of personal data and on the free movement of such data","author":"Parliament","year":"1995","unstructured":"E.U. Parliament . 1995 . Directive 95\/46\/EC on the protection of individuals with regard to the processing of personal data and on the free movement of such data . Official J. European Communities L. 281 , 31. E.U. Parliament. 1995. Directive 95\/46\/EC on the protection of individuals with regard to the processing of personal data and on the free movement of such data. Official J. European Communities L. 281, 31.","journal-title":"Official J. European Communities"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376941"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Fagin R. Halpern J. Y. Moses Y. and Vardi M. Y. 1995. Reasoning About Knowledge. The MIT Press Cambridge MA. (Paperbook edition appeared in 2001.) Fagin R. Halpern J. Y. Moses Y. and Vardi M. Y. 1995. Reasoning About Knowledge. The MIT Press Cambridge MA. (Paperbook edition appeared in 2001.)","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/103516.128680"},{"key":"e_1_2_1_24_1","article-title":"Submodular functions and optimization","volume":"58","author":"Fujishige S.","year":"2005","unstructured":"Fujishige , S. 2005 . Submodular functions and optimization , Annals of Discrete Mathematics , vol. 58. Elsevier Science. Fujishige, S. 2005. Submodular functions and optimization, Annals of Discrete Mathematics, vol. 58. Elsevier Science.","journal-title":"Annals of Discrete Mathematics"},{"volume-title":"Proceedings of the Conference on Effective Methods in Algebraic Geometry (MEGA)","author":"Grigoriev D.","key":"e_1_2_1_25_1","unstructured":"Grigoriev , D. , de Klerk , E. , and Pasechnik , D. V . 2003. Finding optimum subject to few quadratic constraints in polynomial time . In Proceedings of the Conference on Effective Methods in Algebraic Geometry (MEGA) . Universit\u00e4t Kaiserslautern, Germany. Grigoriev, D., de Klerk, E., and Pasechnik, D. V. 2003. Finding optimum subject to few quadratic constraints in polynomial time. In Proceedings of the Conference on Effective Methods in Algebraic Geometry (MEGA). Universit\u00e4t Kaiserslautern, Germany."},{"key":"e_1_2_1_26_1","unstructured":"Hintikka J. 1962. Knowledge and Belief. Cornell University Press Ithaca N.Y. Hintikka J. 1962. Knowledge and Belief. Cornell University Press Ithaca N.Y."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Karp R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Karp R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065183"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19630090502"},{"volume-title":"Mathematical Programming\u2014The State of the Art","author":"Lov\u00e1sz L.","key":"e_1_2_1_30_1","unstructured":"Lov\u00e1sz , L. 1983. Submodular functions and convexity . In Mathematical Programming\u2014The State of the Art , A. Bachem, M. Gr\u00f6tchel, and B. Korte, Eds. Springer-Verlag , 235--257. Lov\u00e1sz, L. 1983. Submodular functions and convexity. In Mathematical Programming\u2014The State of the Art, A. Bachem, M. Gr\u00f6tchel, and B. Korte, Eds. Springer-Verlag, 235--257."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1969-081-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007633"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497437"},{"volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases. 151--162","author":"Nabar S. U.","key":"e_1_2_1_34_1","unstructured":"Nabar , S. U. , Marthi , B. , Kenthapadi , K. , Mishra , N. , and Motwani , R . 2006. Towards robustness in query auditing . In Proceedings of the 32nd International Conference on Very Large Data Bases. 151--162 . Nabar, S. U., Marthi, B., Kenthapadi, K., Mishra, N., and Motwani, R. 2006. Towards robustness in query auditing. In Proceedings of the 32nd International Conference on Very Large Data Bases. 151--162."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Parrilo P. A. and Sturmfels B. 2001. Minimizing polynomial functions. In Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science. 83--100. Parrilo P. A. and Sturmfels B. 2001. Minimizing polynomial functions. In Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science. 83--100.","DOI":"10.1090\/dimacs\/060\/08"},{"key":"e_1_2_1_37_1","unstructured":"PITAC. 2004. Revolutionizing health care through information technology. U.S. President's Information Technology Advisory Committee. PITAC. 2004. Revolutionizing health care through information technology. U.S. President's Information Technology Advisory Committee."},{"key":"e_1_2_1_38_1","volume-title":"Mathematics and Plausible Reasoning, Volume I: Induction and Analogy in Mathematics","author":"P\u00f3lya G.","unstructured":"P\u00f3lya , G. 1954. Mathematics and Plausible Reasoning, Volume I: Induction and Analogy in Mathematics 1 st Ed. Princeton University Press . P\u00f3lya, G. 1954. Mathematics and Plausible Reasoning, Volume I: Induction and Analogy in Mathematics 1st Ed. Princeton University Press.","edition":"1"},{"key":"e_1_2_1_39_1","volume-title":"How to Solve It: A New Aspect of Mathematical Method","author":"P\u00f3lya G.","year":"2004","unstructured":"P\u00f3lya , G. 1957. How to Solve It: A New Aspect of Mathematical Method 2 nd Ed. Princeton University Press . (Expanded ed. 2004 .) P\u00f3lya, G. 1957. How to Solve It: A New Aspect of Mathematical Method 2nd Ed. Princeton University Press. (Expanded ed. 2004.)","edition":"2"},{"volume-title":"Mathematics and Plausible Reasoning","author":"P\u00f3lya G.","key":"e_1_2_1_40_1","unstructured":"P\u00f3lya , G. 1968. Mathematics and Plausible Reasoning , Volume II : Patterns of Plausible Inference 2nd Ed. Princeton University Press . P\u00f3lya, G. 1968. Mathematics and Plausible Reasoning, Volume II: Patterns of Plausible Inference 2nd Ed. Princeton University Press."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446568"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb00928.x"},{"key":"e_1_2_1_44_1","first-page":"731","article-title":"Class of global minimum bounds of polynomial functions","volume":"6","author":"Shor N. Z.","year":"1987","unstructured":"Shor , N. Z. 1987 . Class of global minimum bounds of polynomial functions . Cybernetics 6 , 731 -- 734 . Shor, N. Z. 1987. Class of global minimum bounds of polynomial functions. Cybernetics 6, 731--734.","journal-title":"Cybernetics"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02733104"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01362149"},{"key":"e_1_2_1_47_1","volume-title":"Health insurance portability and accountability act of","author":"Congress","year":"1996","unstructured":"U. S. Congress 1996. Health insurance portability and accountability act of 1996 , United States public law 104--191. http:\/\/www.hhs.gov\/ocr\/hipaa. U. S. Congress 1996. Health insurance portability and accountability act of 1996, United States public law 104--191. http:\/\/www.hhs.gov\/ocr\/hipaa."},{"volume-title":"An Essay in Modal Logic. North-Holland","author":"van Wright G. H.","key":"e_1_2_1_48_1","unstructured":"van Wright , G. H. 1951. An Essay in Modal Logic. North-Holland , Amsterdam . van Wright, G. H. 1951. An Essay in Modal Logic. North-Holland, Amsterdam."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1870103.1870105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1870103.1870105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:47Z","timestamp":1750244387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1870103.1870105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1145\/1870103.1870105"],"URL":"https:\/\/doi.org\/10.1145\/1870103.1870105","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}