Supporting Insertion in Encrypted Multi-Maps with Volume Hiding

A new threat in encrypted databases, called volume leakage was reported by Kellaris et al. and Grubbs et al., where the volume of data associated with each key in a multi-map is leaked. An existing method addresses this problem by adding noise entries to the multi-map according to differential privacy so that adversaries cannot infer the volume of data. However, it assumes that the data is static and therefore does not support any update operations, such as insertion, deletion, etc. To this problem, this paper proposes a method that enables data insertion in the encrypted multi-map with volume hiding. The basic idea is to use local differential privacy instead of differential privacy in adding noise entries when performing insertions. Besides, we employ cuckoo hashing to perturb the place of insertion, thereby allowing insertions of new items without leaking the volume of entries.However, our proposed method is not suitable for large databases. We consider the use of cloud database in healthcare as a use case. The cloud database is necessary for healthcare in cases such as when multiple medical institutions want to share medical data or when home healthcare providers want to access medical data from outside of hospitals. There are privacy issues if the number of patients for each disease is known. Furthermore, when inserting data of a new patient, we want to hide which disease the patient is suffering from.We conduct experiments to assess the feasibility of the proposed method, and it presents a reasonable performance.