Analysis of a Database and Index Encryption Scheme - Problems and Fixes

摘要

The database encryption scheme of Elovici et al. [3] uses encryption of individual cells in a data base table to preserve the database structure. A suitable index encryption scheme is also given for prevention of information leakage from the index. An updated and improved method for index encryption is described by the same authors in [12]. The security goals of these schemes are privacy and authenticity of the cell data at the given position in the table. Furthermore, the encrypted index data shall not have any correlation to the table column data to avoid information leakage. The index shall be protected against unauthorized modification of the index data. In the present paper we cryptanalyze these schemes with respect to possible instantiations and give counter-examples, i.e. give instantiations of these schemes with usual components that are insecure. These counterexamples highlight that the schemes involve assumptions about cryptographic primitives that do no necessarily hold. Furthermore, we show how to modify the schemes so that the original basic ideas of [3] and [12] lead to secure database and index encryption.