Einar Mykletun
Gene Tsudik
Skip Abstract Section
Abstract
In the Outsourced Database (ODB) model, entities outsource their data management needs to a third-party service provider. Such a service provider offers mechanisms for its clients to create, store, update, and access (query) their databases. This work provides mechanisms to ensure data integrity and authenticity for outsourced databases. Specifically, this article provides mechanisms that assure the querier that the query results have not been tampered with and are authentic (with respect to the actual data owner). It investigates both the security and efficiency aspects of the problem and constructs several secure and practical schemes that facilitate the integrity and authenticity of query replies while incurring low computational and communication costs.
- Bellare, M., Garay, J., and Rabin, T. 1998. Fast batch verification for modular exponentiation and digital signatures. In Proceedings of the Eurocrypt Conference, vol. 1403, 191--204.]]Google Scholar
- Bellare, M. and Palacio, A. 2002. Gq and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Advances in Cryptology---CRYPTO, M. Yung, ed. Lecture Notes in Computer Science, vol. 2442, Springer-Verlag, Berlin Germany, 162--177.]] Google Scholar
- Bellare, M. and Rogaway, P. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security. 62--73.]] Google Scholar
- Boneh, D., Gentry, C., Lynn, B., and Shacham, H. 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology---EUROCRYPT, E. Biham, ed. LNCS, Springer-Verlag, Berlin.]]Google Scholar
- Boyd, C. and Pavlovski, C. 2000. Attacking and repairing batch verification schemes. In Asiacrypt. 58--71.]] Google Scholar
- Camenisch, J. 1998. Group signature schemes and paymen systems based on the discrete logarithm problem, vol. 2, ETH-Series in Information Security and Cryptography. Hartung-Gorre Verlag, Konstanz, Germany.]]Google Scholar
- Camenisch, J. and Stadler, M. 1997. Efficient group signature schemes for large groups. In Advances in Cryptology---CRYPTO, vol. 1294, Springer-Verlag, Berlin Germany. 410--424.]] Google Scholar
- Chor, B., Gilboa, N., and Naor, M. 1997. Private information retrieval by keywords. Tech. Rep. TR CS0917, Technion, University.]]Google Scholar
- Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. 1998. Private information retrieval. J. ACM 45, 6 (Nov.), 965--981.]] Google Scholar
- Devanbu, P., Gertz, M., Martel, C., and Stubblebine, S. G. 2000. Authentic third-party data publication. In Proceedings of the 14th IFIP 11.3 Working Conference in Database Security, 101--112.]] Google Scholar
- Fiat, A. and Shamir, A. 1987. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology---CRYPTO '86, A. M. Odlyzko, ed, Lecture Notes in Computer Science, vol. 263, Springer-Verlag, Berlin Germany, Santa, 186--194.]] Google Scholar
- Fiat, A. 1990. Batch RSA. In Advances in Cryptology---CRYPTO '89, G. Brassard, ed. Lecture Notes in Computer Science, vol. 435, Springer-Verlag, Berlin Germany, 175--185.]] Google Scholar
- Fiat, A. 1997. Batch RSA. J. Cryptology 10, 2, 75--88.]]Google Scholar
- Gertner, Y., Ishai, Y., Kushilevitz, E., and Malkin, T. 1998. Protecting data privacy in private information retrieval schemes. In Proceedings of the 30th Annual Symposium on Theory of Computing (STOC) (Dallas, TX).]] Google Scholar
- Goh, E.-J. 2003. Secure indexes for efficient searching on encrypted compressed data. Cryptology ePrint Archive, Rep. 2003/216 http://eprint.iacr.org/2003/216/]]Google Scholar
- Guillou, L. and Quisquater, J. J. 1988. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. In Advances in Cryptology---CRYPTO, S. Goldwasser, ed. Lecture Notes in Computer Science, vol. 403, Springer-Verlag, Berlin Germany.]] Google Scholar
- Hacigümüş, H., Iyer, B., Li, C., and Mehrotra, S. 2002. Executing SQL over encrypted data in the database-service-provider model. In Proceedings of the ACM SIGMOD Conference on Management of Data, 216--227.]] Google Scholar
- Hacigümüş, H., Iyer, B., and Mehrotra, S. 2002a. Encrypted database integrity in database service provider model. In Proceedings of the International Workshop on Certification and Security in E-Services (CSES IFIP WCC).]]Google Scholar
- Hacigümüş, H., Iyer, B., and Mehrotra, S. 2002b. Providing database as a service. In Proceedings of the International Conference on Data Engineering.]] Google Scholar
- Harn, L. 1995. DSA-Type secure interactive batch verification protocols. Electron. Lett. 31, 4 (Feb.), 257--258.]]Google Scholar
- Harn, L. 1998a. Batch verifying multiple DSA-Type digital signatures. Electron. Lett. 34, 9 (Apr.), 870--871.]]Google Scholar
- Harn, L. 1998b. Batch verifying RSA signatures. Electron. Lett. 34, 12 (Apr.), 1219--1220.]]Google Scholar
- Joux, A. and Nguyen, K. 2001. Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. In Cryptology ePrint Archive. Number Rep. 2001/003.]]Google Scholar
- Law, P. 1996. The health insurance portability and accountability act of 1996 (HIPAA). http://www.cms.hhs.gov/hipaa/]]Google Scholar
- Menezes, A. J., Van Oorschot, P. C., and Vanstone, S. A. 1997. Handbook of Applied Cryptography. CRC Press.]] Google Scholar
- Merkle, R. 1980. Protocols for public key cryptosystems. In Proceedings of the IEEE Symposium on Research in Security and Privacy.]]Google Scholar
- Miracl, Library. 2006 http://indigo.ie/~mscott]]Google Scholar
- Mykletun, E., Narasimha, M., and Tsudik, G. 2004a. Authentication and integrity in outsourced databases. In Proceedings of the Symposium on Network and Distributed Systems Security (NDSS).]]Google Scholar
- Mykletun E., Narasimha M., and Tsudik G. 2004b. Signature 'Bouquets': Immutability of Aggregated Signatures, In Proceedings of the European Symposium on Research in Computer Security (ESORICS).]]Google Scholar
- Naccache, D., M'Raïhi, D., Raphaeli, D., and Vaudenay, S. 1994. Can DSA be improved: Complexity trade-offs with the digital signature standard. In Advances in Cryptology---EUROCRYPT, Lecture Notes in Computer Science, Springer-Verlag, Berlin Germany, 85--94.]]Google Scholar
- Narasimha, M. and Tsudik, G. 2005. DSAC: Integrity of outsourced databases with signature aggregation and chaining. In Proceedings of the ACM Conference on Information and Knowledge Management.]] Google Scholar
- OpenSSL Project. 2006. http://www.openssl.org]]Google Scholar
- Pang, H. and Tan, K.-L. 2004. Authenticating query results in edge computing. In Proceedings of the International Conference on Data Engineering, 560--571.]] Google Scholar
- Rivest, R. L., Shamir, A., and Adleman, L. M. 1978. A method for obtaining digital signatures and public-key cryptosystems. Communi. ACM 21, 2 (Feb.), 120--126.]] Google Scholar
- Song, D., Wagner, D., and Perrig, A. 2000. Practical techniques for searches on encrypted data. In Proceedings of the IEEE Symposium on Security and Privacy.]] Google Scholar
- United States Code. 2002. Sarbanes-Oxley act of 2002, HR 3763, PL 107-204, 116 Stat 745. Codified in sections 11, 15, 18, 28, and 29 USC.]]Google Scholar
- Yen, S. and Laih, C. 1995. Improved digital signature suitable for batch verification. IEEE Trans. Comput. 44, 7 (July), 957--959.]] Google Scholar
Index Terms
- Authentication and integrity in outsourced databases
Recommendations
Dynamic authenticated index structures for outsourced databases
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of dataIn outsourced database (ODB)systems the database owner publishes its data through a number of remote servers, with the goal of enabling clients at the edge of the network to access and query the data more efficiently. As servers might be untrusted or ...
Practical Immutable Signature Bouquets PISB for Authentication and Integrity in Outsourced Databases
DBSec 2013: Proceedings of the 27th Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy XXVII - Volume 7964Database outsourcing is a prominent trend that enables organizations to offload their data management overhead e.g., query handling to the external service providers. Immutable signatures are ideal tools to provide authentication and integrity for such ...
Integrity analysis of authenticated encryption based on stream ciphers
We study the security of authenticated encryption based on a stream cipher and a universal hash function. We consider ChaCha20-Poly1305 and generic constructions proposed by Sarkar, where the generic constructions include 14 AEAD (authenticated ...
Comments