{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:32:18Z","timestamp":1761597138108,"version":"3.37.0"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2009,4,14]],"date-time":"2009-04-14T00:00:00Z","timestamp":1239667200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Inf. Secur."],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s10207-009-0078-1","type":"journal-article","created":{"date-parts":[[2009,4,13]],"date-time":"2009-04-13T04:20:52Z","timestamp":1239596452000},"page":"331-345","source":"Crossref","is-referenced-by-count":25,"title":["Negative representations of information"],"prefix":"10.1007","volume":"8","author":[{"given":"Fernando","family":"Esponda","sequence":"first","affiliation":[]},{"given":"Stephanie","family":"Forrest","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Helman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,4,14]]},"reference":[{"key":"78_CR1","unstructured":"Achlioptas, D., Gomes, C., Kautz, H., Selman, B.: Generating satisfiable problem instances. In: Proceedings of the 7th Conference on Artificial Intelligence (AAAI-00) and of the 12th Conference on Innovative Applications of Artificial Intelligence (IAAI-00), pp. 256\u2013261. AAAI Press, Menlo Park (2000)"},{"issue":"4","key":"78_CR2","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1145\/76894.76895","volume":"21","author":"N.R. Adam","year":"1989","unstructured":"Adam N.R., Wortman J.C.: Security-control methods for statistical databases. ACM Comput. Surv. 21(4), 515\u2013556 (1989)","journal-title":"ACM Comput. Surv."},{"key":"78_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, D., Aggarwal, C.C.: On the design and quantification of privacy preserving data mining algorithms. In: Symposium on Principles of Database Systems, pp. 247\u2013255 (2001)","DOI":"10.1145\/375551.375602"},{"key":"78_CR4","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 439\u2013450. ACM Press, New York (2000). http:\/\/citeseer.nj.nec.com\/agrawal00privacypreserving.html","DOI":"10.1145\/342009.335438"},{"key":"78_CR5","unstructured":"Benaloh, J.C., de Mare, M.: One-way accumulators: a decentralized alternative to digital signatures. In: Advances in Cryptology\u2014 EUROCRYPT \u201993, pp. 274\u2013285 (1994). http:\/\/citeseer.nj.nec.com\/article\/benaloh93oneway.html"},{"key":"78_CR6","doi-asserted-by":"crossref","unstructured":"Blakley, G.R., Meadows, C.: A database encryption scheme which allows the computation of statistics using encrypted data. In: Proceedings of the IEEE Symposium on Research in Security and Privacy, pp. 116\u2013122. IEEE CS Press (1985)","DOI":"10.1109\/SP.1985.10024"},{"key":"78_CR7","doi-asserted-by":"crossref","unstructured":"Blum, M., Goldwasser, S.: An efficient probabilistic public-key encryption scheme which hides all partial information. In: Blakely, G.R., Chaum, D. (eds.) Advances in Cryptology: proceedings of CRYPTO 84. Lecture Notes in Computer Science, vol. 196, pp. 289\u2013302. Springer, Berlin (1985)","DOI":"10.1007\/3-540-39568-7_23"},{"issue":"2","key":"78_CR8","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/TIT.1979.1056010","volume":"25","author":"G. Brassard","year":"1979","unstructured":"Brassard G.: A note on the complexity of cryptography. IEEE Trans. Inform. Theory 25(2), 232\u2013233 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"78_CR9","unstructured":"Brassard, G., Fortune, S., Hopcroft, J.E.: A note on cryptography and NP $${\\cap}$$ coNP-P. Technical Report TR78-338, Cornell University, Computer Science Department (1978)"},{"key":"78_CR10","doi-asserted-by":"crossref","unstructured":"Bryant R.E. (1992) Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24(3), 293\u2013318 (1992). http:\/\/citeseer.nj.nec.com\/bryant92symbolic.html","DOI":"10.1145\/136035.136043"},{"key":"78_CR11","doi-asserted-by":"crossref","unstructured":"Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) Advances in Cryptology\u2014CRYPTO \u2019 2002, Lecture Notes in Computer Science, vol. 2442, pp. 61\u201376. International Association for Cryptologic Research, Springer, Germany (2002). http:\/\/www.springerlink.com\/link.asp?id=yklb7xdvbbc0wwgy","DOI":"10.1007\/3-540-45708-9_5"},{"issue":"3","key":"78_CR12","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1145\/5925.5928","volume":"33","author":"F. Chin","year":"1986","unstructured":"Chin F.: Security problems on inference control for sum, max, and min queries. J. ACM 33(3), 451\u2013464 (1986). doi: 10.1145\/5925.5928","journal-title":"J. ACM"},{"key":"78_CR13","first-page":"1","volume-title":"Satisfiability Problem: Theory and Applications, Dimacs Series in Discrete Mathematics and Theoretical Computer Science, vol 35","author":"S.A. Cook","year":"1997","unstructured":"Cook S.A., Mitchell D.G.: Finding hard instances of the satisfiability problem: A survey. In: Du, D., Gu, J., Pardalos, P.M. (eds) Satisfiability Problem: Theory and Applications, Dimacs Series in Discrete Mathematics and Theoretical Computer Science, vol 35, pp. 1\u201317. American Mathematical Society, Providence (1997)"},{"key":"78_CR14","first-page":"21","volume-title":"Proceedings of the Eleventh National Conference on Artificial Intelligence","author":"J.M. Crawford","year":"1993","unstructured":"Crawford J.M., Anton L.D.: Experimental results on the crossover point in satisfiability problems. In: Fikes, R., Lehnert, W. (eds) Proceedings of the Eleventh National Conference on Artificial Intelligence, pp. 21\u201327. American Association for Artificial Intelligence, AAAI Press, Menlo Park (1993)"},{"key":"78_CR15","doi-asserted-by":"crossref","unstructured":"Danezis, G., Diaz, G., Faust, S., K\u00e4sper, E., Troncoso, C., Preneel, B.: Efficient negative databases from cryptographic hash functions. In: LNCS (ed.). Information Security Conference, vol. 4779, pp. 423\u2013436 (2007)","DOI":"10.1007\/978-3-540-75496-1_28"},{"key":"78_CR16","volume-title":"Cryptography and Data Security","author":"D. Denning","year":"1982","unstructured":"Denning D.: Cryptography and Data Security. Addison Wesley, Reading (1982)"},{"issue":"7","key":"78_CR17","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/MC.1983.1654444","volume":"16","author":"D. Denning","year":"1983","unstructured":"Denning D., Schlorer J.: Inference controls for statistical databases. Computer 16(7), 69\u201382 (1983)","journal-title":"Computer"},{"key":"78_CR18","doi-asserted-by":"crossref","unstructured":"Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second- generation onion router. In: Proceedings of the 13th USENIX Security Symposium (2004)","DOI":"10.21236\/ADA465464"},{"issue":"1","key":"78_CR19","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/320064.320068","volume":"4","author":"D. Dobkin","year":"1979","unstructured":"Dobkin D., Jones A., Lipton R.: Secure databases: protection against user influence. ACM Trans. Database Syst. 4(1), 97\u2013106 (1979)","journal-title":"ACM Trans. Database Syst."},{"key":"78_CR20","doi-asserted-by":"crossref","unstructured":"Esponda, F.: Hiding a needle in a haystack using negative databases. In: Proceedings of the 10th Information Hiding Conference (2008)","DOI":"10.1007\/978-3-540-88961-8_2"},{"issue":"3","key":"78_CR21","first-page":"201","volume":"1","author":"F. Esponda","year":"2005","unstructured":"Esponda F., Ackley E.S., Forrest S., Helman P.: On-line negative databases (with experimental results). Int. J. Unconvent. Comput. 1(3), 201\u2013220 (2005)","journal-title":"Int. J. Unconvent. Comput."},{"key":"78_CR22","doi-asserted-by":"crossref","unstructured":"Esponda, F., Forrest, S., Helman, P.: Enhancing privacy through negative representations of data. Technical report, University of New Mexico (2004)","DOI":"10.21236\/ADA498766"},{"issue":"1","key":"78_CR23","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1109\/TSMCB.2003.817026","volume":"34","author":"F. Esponda","year":"2004","unstructured":"Esponda F., Forrest S., Helman P.: A formal framework for positive and negative detection schemes. IEEE Trans. Syst. Man Cybernet. Part B: Cybernet. 34(1), 357\u2013373 (2004)","journal-title":"IEEE Trans. Syst. Man Cybernet. Part B: Cybernet."},{"issue":"6","key":"78_CR24","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s10207-007-0030-1","volume":"6","author":"F. Esponda","year":"2007","unstructured":"Esponda F., Forrest S., Helman P.: Protecting data privacy through hard-to-reverse negative databases. Int. J. Inform. Security 6(6), 403\u2013415 (2007)","journal-title":"Int. J. Inform. Security"},{"key":"78_CR25","unstructured":"Esponda, F., Trias, E., Ackley, E., Forrest, S.: A relational algebra for negative databases. Tech. Rep. TR-CS-2007-18, University of New Mexico (2007)"},{"key":"78_CR26","doi-asserted-by":"crossref","unstructured":"Even, S., Yacobi, Y.: Cryptography and np-completeness. In: Proc. 7th Colloq. Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 85, pp. 195\u2013207. Springer, Berlin (1980)","DOI":"10.1007\/3-540-10003-2_71"},{"key":"78_CR27","unstructured":"Feigenbaum, J., Grosse, E., Reeds, J.A.: Cryptographic protection of membership lists 9(1), 16\u201320 (1992). ftp:\/\/cm.bell-labs.com\/cm\/cs\/doc\/91\/4-12.ps.gz"},{"key":"78_CR28","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Liberman, M.Y., Wright, R.N.: Cryptographic protection of databases and software. In: Distributed Computing and Cryptography, pp. 161\u2013172. American Mathematical Society, Providence (1991)","DOI":"10.1090\/dimacs\/002\/10"},{"issue":"2","key":"78_CR29","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0166-218X(02)00400-6","volume":"130","author":"C. Fiorini","year":"2003","unstructured":"Fiorini C., Martinelli E., Massacci F.: How to fake an RSA signature by encoding modular root finding as a SAT problem. Discrete Appl. Math. 130(2), 101\u2013127 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"78_CR30","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1145\/356924.356929","volume":"16","author":"H. Gallaire","year":"1984","unstructured":"Gallaire H., Minker J., Nicolas J.: Logic and databases: a deductive approach. Comput. Surv. 16(2), 154\u2013185 (1984)","journal-title":"Comput. Surv."},{"key":"78_CR31","volume-title":"Foundations of Cryptography: Basic Tools","author":"O. Goldreich","year":"2000","unstructured":"Goldreich O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2000)"},{"key":"78_CR32","doi-asserted-by":"crossref","unstructured":"Goldwasser, S.: Multi party computations: past and present. In: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 1\u20136. ACM Press, New York (1997). doi: 10.1145\/259380.259405","DOI":"10.1145\/259380.259405"},{"key":"78_CR33","unstructured":"Goldwasser S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2):270\u2013299 (1984). See also preliminary version in 14th STOC, 1982"},{"key":"78_CR34","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 12\u201324. ACM Press, New York (1989). doi: 10.1145\/73007.73009","DOI":"10.1145\/73007.73009"},{"key":"78_CR35","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. In: IEEE (ed.) 30th annual Symposium on Foundations of Computer Science, October 30\u2013November 1, 1989, Research Triangle Park, NC, pp. 236\u2013241. IEEE Computer Society Press, USA (1989)","DOI":"10.1109\/SFCS.1989.63484"},{"key":"78_CR36","doi-asserted-by":"crossref","unstructured":"Jia, H., Moore, C., Strain, D.: Generating hard satisfiable formulas by hiding solutions deceptively. In: AAAI (2005)","DOI":"10.1007\/11527695_16"},{"key":"78_CR37","doi-asserted-by":"crossref","unstructured":"Karnaugh, M.: The map method for synthesis of combinational logic circuits. Trans. AIEE, pp. 593\u2013598 (1953)","DOI":"10.1109\/TCE.1953.6371932"},{"key":"78_CR38","doi-asserted-by":"crossref","unstructured":"Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: On the learnability of discrete distributions. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of computing, pp. 273\u2013282. ACM Press, New York (1994). doi: 10.1145\/195058.195155","DOI":"10.1145\/195058.195155"},{"key":"78_CR39","doi-asserted-by":"crossref","unstructured":"Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Advances in Cryptology\u2014Eurocrypt \u20192004 Proceedings. LNCS, vol. 3027, pp. 1\u201319. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"78_CR40","doi-asserted-by":"crossref","unstructured":"de Mare, M., Secure, R.W.: Set membership using 3sat. In: Proceedings of the Eighth International Conference on Information and Communication Security (ICICS \u201906) (2006)","DOI":"10.1007\/11935308_32"},{"key":"78_CR41","unstructured":"Matloff, N.S.: Inference control via query restriction vs. data modification: a perspective. In: On Database Security: Status and Prospects, pp. 159\u2013166. North-Holland Publishing Co., Amsterdam (1988)"},{"key":"78_CR42","doi-asserted-by":"crossref","unstructured":"McCluskey, E.: Minimization of boolean functions. Bell System Technical Journal, pp. 1417\u20131444 (1956)","DOI":"10.1002\/j.1538-7305.1956.tb03835.x"},{"issue":"5","key":"78_CR43","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","volume":"24","author":"R.C. Merkle","year":"1978","unstructured":"Merkle R.C., Hellman M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Trans. Inf. Theory 24(5), 525\u2013530 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"78_CR44","doi-asserted-by":"crossref","unstructured":"Micali, S., Rabin, M., Kilian, J.: Zero-knowledge sets. In: Proceedings of the FOCS 2003, p. 80 (2003)","DOI":"10.1109\/SFCS.2003.1238183"},{"key":"78_CR45","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Problem solving: hardness and easiness\u2014hard and easy distributions of SAT problems. In: Proceeding of the 10th National Conference on Artificial Intelligence (AAAI-92), San Jose, California, pp. 459\u2013465. AAAI Press, Menlo Park (1992)"},{"key":"78_CR46","unstructured":"Morselli, R., Bhattacharjee, S., Katz, J., Keleher, P.: Trust preserving set operations. Tech. rep."},{"key":"78_CR47","doi-asserted-by":"crossref","unstructured":"Naor, M.: Evaluation may be easier than generation (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of computing, pp. 74\u201383. ACM Press, New York (1996). doi: 10.1145\/237814.237833","DOI":"10.1145\/237814.237833"},{"key":"78_CR48","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, Seattle, Washington, May 15\u201317, 1989, pp. 33\u201343. ACM Press, New York (1989)","DOI":"10.1145\/73007.73011"},{"key":"78_CR49","doi-asserted-by":"crossref","unstructured":"Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Pomerance, C., Goldwasser, S., (eds.) Cryptology and Computational Number Theory. Proceedings of Symposia in Applied Mathematics. AMS short course lecture notes, vol. 42, pp. 75\u201388. pub-AMS (1990)","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"78_CR50","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rackoff, C., Smith, A.: Efficient consistency proofs for generalized queries on a committed database. In: ICALP: Annual International Colloquium on Automata, Languages and Programming, pp. 1041\u20131053 (2004)","DOI":"10.1007\/978-3-540-27836-8_87"},{"key":"78_CR51","doi-asserted-by":"crossref","unstructured":"Quine, W.V.: A way to simplify truth functions. American Mathematical Monthly, pp. 627\u2013631 (1955)","DOI":"10.1080\/00029890.1955.11988710"},{"issue":"4","key":"78_CR52","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1109\/49.668972","volume":"16","author":"M.G. Reed","year":"1998","unstructured":"Reed M.G., Syverson P.F., Goldschlag D.M.: Anonymous connections and onion routing. IEEE J. Selected Areas Commun. 16(4), 482\u2013494 (1998)","journal-title":"IEEE J. Selected Areas Commun."},{"key":"78_CR53","volume-title":"Applied Cryptography: Protocols, Algorithms, and Source Code in C","author":"B. Schneier","year":"1994","unstructured":"Schneier B.: Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley and Sons, Inc., New York (1994)"},{"issue":"1","key":"78_CR54","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/174638.174641","volume":"19","author":"P. Tendick","year":"1994","unstructured":"Tendick P., Matloff N.: A modified random perturbation method for database security. ACM Trans. Database Syst. 19(1), 47\u201363 (1994). doi: 10.1145\/174638.174641","journal-title":"ACM Trans. Database Syst."},{"key":"78_CR55","doi-asserted-by":"crossref","unstructured":"Vaidya, J., Clifton, C.: Secure set intersection cardinality with application to association rule mining. J. Comput. Security (2004, to appear)","DOI":"10.3233\/JCS-2005-13401"},{"key":"78_CR56","volume-title":"Translucent Databases","author":"P. Wayner","year":"2002","unstructured":"Wayner P.: Translucent Databases. Flyzone Press, Baltimore (2002)"},{"key":"78_CR57","doi-asserted-by":"crossref","unstructured":"Yao, A.: Protocols for secure computations. In: IEEE (ed.) 23rd annual Symposium on Foundations of Computer Science, November 3\u20135, 1982, Chicago, IL, pp. 160\u2013164. IEEE Computer Society Press, USA (1982)","DOI":"10.1109\/SFCS.1982.38"}],"container-title":["International Journal of Information Security"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10207-009-0078-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10207-009-0078-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10207-009-0078-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T23:09:33Z","timestamp":1739056173000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10207-009-0078-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,14]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["78"],"URL":"https:\/\/doi.org\/10.1007\/s10207-009-0078-1","relation":{},"ISSN":["1615-5262","1615-5270"],"issn-type":[{"type":"print","value":"1615-5262"},{"type":"electronic","value":"1615-5270"}],"subject":[],"published":{"date-parts":[[2009,4,14]]}}}