More Web Proxy on the site http://driver.im/

Article

Protecting data privacy through hard-to-reverse negative databases

Authors:

Fernando Esponda,

Elena S. Ackley,

Stephanie ForrestAuthors Info & Claims

ISC'06: Proceedings of the 9th international conference on Information Security

Pages 72 - 84

https://doi.org/10.1007/11836810_6

Published: 30 August 2006 Publication History

Abstract

The paper extends the idea of negative representations of information for enhancing privacy. Simply put, a set DB of data elements can be represented in terms of its complement set. That is, all the elements not in DB are depicted and DB itself is not explicitly stored.

review the negative database (NDB) representation scheme for storing a negative image compactly and propose a design for depicting a multiple record DB using a collection of NDBs—in contrast to the single NDB approach of previous work. Finally, we present a method for creating negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB, by adapting a technique for generating 3-SAT formulas.

References

[1]

D. Achlioptas, Beame, and Molloy. A sharp threshold in proof complexity. In STOC: ACM Symposium on Theory of Computing (STOC), 2001.

Digital Library

[2]

D. Achlioptas, C. Gomes, H. Kautz, and B. Selman. Generating satisfiable problem instances. In Proceedings of AAAI-00 and IAAI-00, pages 256-261, Menlo Park, CA, July 30- 3 2000. AAAI Press.

Digital Library

[3]

D. Achlioptas and Peres. The threshold for random k-SAT is 2^k log 2 - O(k). JAMS: Journal of the American Mathematical Society, 17, 2004.

[4]

N. R. Adam and J. C. Wortman. Security-control methods for statistical databases. ACM Computing Surveys, 21(4):515-556, December 1989.

Digital Library

[5]

D. Agrawal and C. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Symposium on Principles of Database Systems, pages 247-255, 2001.

Digital Library

[6]

R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. of the ACM SIGMOD Conference on Management of Data, pages 439-450. ACM Press, May 2000.

Digital Library

[7]

J. Cohen Benaloh and M. de Mare. One-way accumulators: A decentralized alternative to digital signatures. In Advances in Cryptology--EUROCRYPT '93, pages 274-285, 1994.

Digital Library

[8]

G. R. Blakley and C. Meadows. 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, pages 116-122. IEEE CS Press, 1985.

[9]

M. Blum and S. Goldwasser. An efficient probabilistic public-key encryption scheme which hides all partial information. In George Robert Blakely and David Chaum, editors, Advances in Cryptology: proceedings of CRYPTO 84, volume 196 of Lecture Notes in Computer Science, pages 289-302, Berlin, Germany / Heidelberg, Germany / London, UK / etc., 1985. Springer-Verlag.

Digital Library

[10]

J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Moti Yung, editor, Advances in Cryptology - CRYPTO ' 2002, volume 2442 of Lecture Notes in Computer Science, pages 61-76. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 2002.

Digital Library

[11]

F. Chin. Security problems on inference control for sum, max, and min queries. J. ACM, 33(3):451-464, 1986.

Digital Library

[12]

S. A. Cook and D. G. Mitchell. Finding hard instances of the satisfiability problem: A survey. In Du, Gu, and Pardalos, editors, Satisfiability Problem: Theory and Applications, volume 35 of Dimacs Series in Discrete Mathematics and Theoretical Computer Science, pages 1-17. American Mathematical Society, 1997.

[13]

D. Denning. Cryptography and Data Security. AddisonWesley, Reading, MA, 1982.

[14]

D.E. Denning and J. Schlorer. Inference controls for statistical databases. Computer, 16(7):69-82, July 1983.

Digital Library

[15]

D. Dobkin, A. Jones, and R. Lipton. Secure databases: Protection against user influence. ACM Transactions on Database Systems, 4(1):97-106, March 1979.

Digital Library

[16]

F. Esponda. Negative Representations of Information. PhD thesis, University of New Mexico, 2005.

Digital Library

[17]

F. Esponda, E. S. Ackley, S. Forrest, and P. Helman. On-line negative databases. In Proceedings of ICARIS, 2004.

[18]

F. Esponda, E. S. Ackley, S. Forrest, and P. Helman. On-line negative databases (with experimental results). International Journal of Unconventional Computing, 1(3):201-220, 2005.

[19]

F. Esponda, S. Forrest, and P. Helman. Enhancing privacy through negative representations of data. Technical report, University of New Mexico, 2004.

[20]

F. Esponda, S. Forrest, and P. Helman. Negative representations of information. Submitted to International Journal of Information Security, 2004.

Digital Library

[21]

S. Even and Y. Yacobi. Cryptography and np-completeness. In Proc. 7th Colloq. Automata, Languages, and Programming (Lecture Notes in Computer Science), volume 85, pages 195-207. Springer-Verlag, 1980.

Digital Library

[22]

J. Feigenbaum, E. Grosse, and J. A. Reeds. Cryptographic protection of membership lists. 9(1):16-20, 1992.

[23]

J. Feigenbaum, M. Y. Liberman, and R. N. Wright. Cryptographic protection of databases and software. In Distributed Computing and Cryptography, pages 161-172. American Mathematical Society, 1991.

[24]

C. Fiorini, E. Martinelli, and F. Massacci. How to fake an RSA signature by encoding modular root finding as a SAT problem. Discrete Appl. Math., 130(2):101-127, 2003.

Digital Library

[25]

I. P. Gent and T. Walsh. The SAT phase transition. In Proceedings of the Eleventh European Conference on Artificial Intelligence (ECAI'94), pages 105-109, 1994.

[26]

O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2000.

Digital Library

[27]

S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-299, 1984.

[28]

R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 12-24. ACM Press, 1989.

Digital Library

[29]

R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. In IEEE, editor, 30th annual Symposium on Foundations of Computer Science, October 30-November 1, 1989, Research Triangle Park, NC, pages 236-241, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 1989. IEEE Computer Society Press.

Digital Library

[30]

H. Jia, C. Moore, and D. Strain. Generating hard satisfiable formulas by hiding solutions deceptively. In AAAI, 2005.

Digital Library

[31]

H. A. Kautz, Y. Ruan, D. Achlioptas, C. Gomes, B. Selman, and M. E. Stickel. Balance and filtering in structured satisfiable problems. In IJCAI, pages 351-358, 2001.

Digital Library

[32]

N. S. Matloff. Inference control via query restriction vs. data modification: a perspective. In on Database Security: Status and Prospects, pages 159-166. North-Holland Publishing Co., 1988.

Digital Library

[33]

R. C. Merkle and M. E. Hellman. Hiding information and signatures in trapdoor knapsacks. IT-24:525-530, 1978.

[34]

S. Micali, M. Rabin, and J. Kilian. Zero-knowledge sets. In Proc. FOCS 2003., page 80, 2003.

Digital Library

[35]

D. Mitchell, B. Selman, and H. Levesque. Problem solving: Hardness and easiness - hard and easy distributions of SAT problems. In Proceeding of (AAAI-92), pages 459-465. AAAI Press, Menlo Park, California, USA, 1992.

Digital Library

[36]

M. Naor and M. Yung. 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-17, 1989, pages 33-43, New York, NY 10036, USA, 1989. ACM Press.

Digital Library

[37]

A. M. Odlyzko. The rise and fall of knapsack cryptosystems. In Carl Pomerance and S. Goldwasser, editors, Cryptology and Computational Number Theory, volume 42 of Proceedings of symposia in applied mathematics. AMS short course lecture notes, pages 75-88. pub-AMS, 1990.

[38]

R. Ostrovsky, C. Rackoff, and A. Smith. Efficient consistency proofs for generalized queries on a committed database. In ICALP: Annual International Colloquium on Automata, Languages and Programming, pages 1041-1053, 2004.

[39]

P. Shaw, K. Stergiou, and T. Walsh. Arc consistency and quasigroup completion. In In Proceedings of ECAI98 Workshop on Non-binary Constraints, 1998.

[40]

P. Tendick and N. Matloff. A modified random perturbation method for database security. ACM Trans. Database Syst., 19(1):47-63, 1994.

Digital Library

[41]

P. Wayner. Translucent Databases. Flyzone Press, 2002.

Cited By

Dasgupta DNag AFerebee DSaha SSubedi KRoy AMadero ASanchez AWilliams J(2019)Design and implementation of Negative Authentication SystemInternational Journal of Information Security10.1007/s10207-017-0395-818:1(23-48)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10207-017-0395-8
Patti FBagnoli F(2008)Biologically Inspired ClassifierBio-Inspired Computing and Communication10.1007/978-3-540-92191-2_29(332-339)Online publication date: 27-Nov-2008
https://dl.acm.org/doi/10.1007/978-3-540-92191-2_29
Danezis GDiaz CFaust SKäsper ETroncoso CPreneel B(2007)Efficient negative databases from cryptographic hash functionsProceedings of the 10th international conference on Information Security10.5555/2396231.2396270(423-436)Online publication date: 9-Oct-2007
https://dl.acm.org/doi/10.5555/2396231.2396270

Protecting data privacy through hard-to-reverse negative databases
1. Theory of computation

Recommendations

Protecting data privacy through hard-to-reverse negative databases

A set DB of data elements can be represented in terms of its complement set, known as a negative database. That is, all of the elements not in DB are represented, and DB itself is not explicitly stored. This method of representing data has certain ...
Negative databases for biometric data
MM&Sec '10: Proceedings of the 12th ACM workshop on Multimedia and security

Negative databases -- negative representations of a set of data -- have been introduced in 2004 to protect the data they contain. Up to this day, there was no known solution to constitute biometric negative databases. This is surprising as biometric ...
Reverse engineering of relational databases: extraction of an EER model from a relational database

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISC'06: Proceedings of the 9th international conference on Information Security

August 2006

547 pages

ISBN:3540383417

Editors:
Sokratis K. Katsikas
University of the Aegean, University Hill, Mytilene, Greece
,
Javier López
Department of Information and Communication Technologies, University of A Coruña, University Hill, Mytilene, Spain
,
Michael Backes
Department of Information and Communication Technologies, MPI-SWS, University Hill, Mytilene,
,
Stefanos Gritzalis
Department of Information and Communication Systems Engineering, University of the Aegean, University Hill, Karlovassi, Samos, Greece
,
Bart Preneel
Department of Information and Communication Systems Engineering, Interdisciplinary Institute for BroadBand Technology (IBBT), University Hill, Karlovassi, Samos, Belgium

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 August 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dasgupta DNag AFerebee DSaha SSubedi KRoy AMadero ASanchez AWilliams J(2019)Design and implementation of Negative Authentication SystemInternational Journal of Information Security10.1007/s10207-017-0395-818:1(23-48)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10207-017-0395-8
Patti FBagnoli F(2008)Biologically Inspired ClassifierBio-Inspired Computing and Communication10.1007/978-3-540-92191-2_29(332-339)Online publication date: 27-Nov-2008
https://dl.acm.org/doi/10.1007/978-3-540-92191-2_29
Danezis GDiaz CFaust SKäsper ETroncoso CPreneel B(2007)Efficient negative databases from cryptographic hash functionsProceedings of the 10th international conference on Information Security10.5555/2396231.2396270(423-436)Online publication date: 9-Oct-2007
https://dl.acm.org/doi/10.5555/2396231.2396270

View Options

View options

Media

Figures

Other

Tables

View Table of Contents