Towards Efficient and Secure Encrypted Databases: Extending Message-Locked Encryption in Three-Party Model

摘要

In database systems with three parties consisting of a data owner, a database manager and a data analyst, the data owner uploads encrypted data to a database and the data analyst delegated by the data owner analyzes the data by accessing to the database without knowing plaintexts. In this work, towards an efficient and secure scheme whose encryption can be processed in real time, we extend message-locked encryption (Bellare et al. [2]), where parts of ciphertexts are generated from their plaintexts deterministically. In particular, we introduce both delegations of relational search between ciphertexts from a data owner to a data analyst, and re-encryption of ciphertexts such that ciphertexts of the message-locked encryption become truly probabilistic against a database manager. We call the scheme message-locked encryption ivith re-encryption and relational search, and formalize the security, which is feasible and practical, in two cases, i.e., any relationship in a general setting and only an equality test in a restricted setting. Both settings are useful from a standpoint of trade-offs between the security and the efficiency. We also propose an instantiation with the equality test between ciphertexts.