International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Encryption Techniques for Secure Database Outsourcing

Sergei Evdokimov
Oliver Guenther
Search ePrint
Search Google
Abstract: While the idea of database outsourcing is becoming increasingly popular, the associated security risks still prevent many potential users from deploying it. In particular, the need to give full access to one's data to a third party, the database service provider, remains a major obstacle. A seemingly obvious solution is to encrypt the data in such a way that the service provider retains the ability to perform relational operations on the encrypted database. In this paper we present a model and an encryption scheme that solves this problem at least partially. Our approach represents the provably secure solution to the database outsourcing problem that allows operations exact select, Cartesian product, and projection, and that guarantees the probability of erroneous answers to be negligible. Our scheme is simple and practical, and it allows effective searches on encrypted tables: For a table consisting of n tuples the scheme performs search in O(n) steps.
  title={Encryption Techniques for Secure Database Outsourcing},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / secret-key cryptography, search, privacy homomorphism},
  note={Full version (published originally at ESORICS'07) 13783 received 24 Aug 2007, last revised 27 Sep 2007},
  author={Sergei Evdokimov and Oliver Guenther},