ALGEBRAIC OPERATIONS ON ENCRYPTED RELATIONAL DATABASES

Abstract

In this paper, we consider the problem of performing algebraic operations and their extensions with encrypted relational databases. Each tuple of a relation is enciphered by a cryptosystem based on the extended Chinese remainder theorem. We show that one can perform the Projection, the Cartesian Product and their composite operations, such as performing the Projection followed by the Cartesian Product and performing Cartesian Product followed by the Projection, with the encrypted tuples directly without deciphering them. We also show that there does not exist a secure way to protect data for performing Comparison operations, such as Selection, Union,... , etc., with encrypted relational databases.