Abstract
A negative database is a privacy-preserving storage system that allows to efficiently test if an entry is present, but makes it hard to enumerate all encoded entries. We improve significantly over previous work presented at ISC 2006 by Esponda et al. [9], by showing constructions for negative databases reducible to the security of well understood primitives, such as cryptographic hash functions or the hardness of the Discrete-Logarithm problem. Our constructions require only \({\cal O}(m)\) storage in the number m of entries in the database, and linear query time (compared to \({\cal O}(l\cdot m)\) storage and \({\cal O}(l\cdot m)\) query time, where l is a security parameter.) Our claims are supported by both proofs of security and experimental performance measurements.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
The non-denial of the non-self. The Economist (August 2006)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73. ACM Press, New York (1993)
Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation (extended abstract). In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200–207. Springer, Heidelberg (1993)
Chaum, D., Evertse, J.-H., van de Graaf, J.: An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 127–141. Springer, Heidelberg (1988)
Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Dobbertin, H., Bosselaers, A., Preneel, B.: RIPEMD-160: A strengthened version of RIPEMD. In: Gollmann, D. (ed.) Fast Software Encryption. LNCS, vol. 1039, pp. 71–82. Springer, Heidelberg (1996)
Esponda, F., Ackley, E.S., Forrest, S., Helman, P.: Online negative databases. In: Nicosia, G., Cutello, V., Bentley, P.J., Timmis, J. (eds.) ICARIS 2004. LNCS, vol. 3239, pp. 175–188. Springer, Heidelberg (2004)
Esponda, F., Ackley, E.S., Helman, P., Jia, H., Forrest, S.: Protecting data privacy through hard-to-reverse negative databases. In: Katsikas, S.K., Lopez, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) ISC 2006. LNCS, vol. 4176, pp. 72–84. Springer, Heidelberg (2006)
Esponda, F., Ackley, E.S., Helman, P., Jia, H., Forrest, S.: Protecting data privacy through hard-to-reverse negative databases. International Journal of Information Security (2007)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Gong, L., Lomas, T.M.A., Needham, R.M., Saltzer, J.H.: Protecting poorly chosen secrets from guessing attacks. IEEE Journal on Selected Areas in Communications 11(5), 648–656 (1993)
Gordon, D.M.: A Survey of Fast Exponentiation Methods. Journal of Algorithms 27(1), 129–146 (1998)
International Organization for Standardization. ISO/IEC 10118-3:2004: Information technology — Security techniques — Hash-functions — Part 3: Dedicated hash-functions. International Organization for Standardization, Geneva, Switzerland (February 2004)
Lien, R., Grembowski, T., Gaj, K.: A 1 Gbit/s partially unrolled architecture of hash functions SHA-1 and SHA-512. In: Topics in Cryptology-CT-RSA 2004 Proceedings, pp. 324–338 (2004)
National Institute of Standards and Technology. FIPS PUB 180-2: Secure Hash Standard. National Institute for Standards and Technology, Gaithersburg, MD, USA, August 2002, Supersedes FIPS PUB 180 1993 May 11 and 180-1 (April 17, 1995)
Rivest, R.: The MD5 Message-Digest Algorithm. RFC 1321 (Informational) (April 1992)
Sakiyama, K., Mentens, N., Batina, L., Preneel, B., Verbauwhede, I.: Reconfigurable modular arithmetic logic unit supporting high-performance RSA and ECC over GF(p). International Journal of Electronics 99(99), 15 (2007)
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Danezis, G., Diaz, C., Faust, S., Käsper, E., Troncoso, C., Preneel, B. (2007). Efficient Negative Databases from Cryptographic Hash Functions. In: Garay, J.A., Lenstra, A.K., Mambo, M., Peralta, R. (eds) Information Security. ISC 2007. Lecture Notes in Computer Science, vol 4779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75496-1_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-75496-1_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75495-4
Online ISBN: 978-3-540-75496-1
eBook Packages: Computer ScienceComputer Science (R0)