Substring search over encrypted data

Article type: Research Article

Authors: Moataz, Tarik^{a; c; *} | Ray, Indrajit^a | Ray, Indrakshi^a | Shikfa, Abdullatif^b | Cuppens, Frédéric^c | Cuppens, Nora^c

Affiliations: [a] Department of Computer Science, Colorado State University, USA | [b] Kindi Center for Computing Research, Qatar University, Qatar | [c] Institut Mines-Télécom Atlantique, France

Correspondence: [*] Corresponding author. E-mail: tarik.moataz@colostate.edu.

Abstract: We propose a general solution to the problem of efficient substring search over encrypted data. The solution enhances existing “keyword” searchable encryption schemes by allowing searching for any part of encrypted keywords without requiring one to store all possible combinations of substrings from a given dictionary. The proposed technique is based on the idea of letter orthogonalization that allows testing of string membership by performing efficient inner products. We first propose SED-1, the base protocol for substring search. We then identify some attacks on SED-1 that demonstrate the complexity of the substring search problem under different threat scenarios. This leads us to propose our second and main protocol SED-2. The protocol is also efficient in that the search complexity is linear in the size of the keyword dictionary. We run several experiments on a sizeable real world dataset to evaluate the performance of our protocol.

Keywords: Encrypted search, substring search, wildcard search, orthonormalization

DOI: 10.3233/JCS-14652

Journal: Journal of Computer Security, vol. 26, no. 1, pp. 1-30, 2018