Confidentiality-Preserving Image Search: A Comparative Study Between Homomorphic Encryption and Distance-Preserving Randomization

Recent years have seen increasing popularity of storing and managing personal multimedia data using online services. Preserving confidentiality of online personal data while offering efficient functionalities thus becomes an important and pressing research issue. In this paper, we study the problem of content-based search of image data archived online while preserving content confidentiality. The problem has different settings from those typically considered in the secure computation literature, as it deals with data in rank-ordered search, and has a different security-efficiency requirement. Secure computation techniques, such as homomorphic encryption, can potentially be used in this application, at a cost of high computational and communication complexity. Alternatively, efficient techniques based on randomizing visual feature and search indexes have been proposed recently to enable similarity comparison between encrypted images. This paper focuses on comparing these two major paradigms of techniques, namely, homomorphic encryption based techniques and feature/index randomization-based techniques, for confidentiality-preserving image search. We develop novel and systematic metrics to quantitatively evaluate security strength in this unique type of data and applications. We compare these two paradigms of techniques in terms of their search performance, security strength, and computational efficiency. The insights obtained through this paper and comparison will help design practical algorithms appropriate for privacy-aware cloud multimedia systems.