Secure and efficient wildcard search over encrypted data
| Autor: | Sanjit Chatterjee, Jayam Modi, Akash Shah, Manish Kesarwani, Sayantan Mukherjee, Shravan Kumar Parshuram Puria |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
021110 strategic
defence & security studies Computer Networks and Communications business.industry Computer science 0211 other engineering and technologies Wildcard character 02 engineering and technology computer.file_format Encryption Combinatorics Safety Risk Reliability and Quality business computer Computer communication networks Software Information Systems |
| Zdroj: | International Journal of Information Security. 20:199-244 |
| ISSN: | 1615-5270 1615-5262 |
| DOI: | 10.1007/s10207-020-00492-w |
| Popis: | In this work, we investigate the problem of secure wildcard search over encrypted data. The setting comprises of three entities, viz. the data owner, the server and the client. The data owner outsources the encrypted data to the server, who obliviously services the clients’ queries. We first analyze efficiency and security of two recent proposals from International Journal of Information Security, called, respectively, the Wei–Reiter (WR) and Hu–Han (HH) protocol. We demonstrate that HH protocol is completely insecure while WR is not scalable for the problem of wildcard search over encrypted data. Our main contribution consists of three protocols, viz. $$\mathsf {\Pi }_{\mathsf {OXT}}$$ , $$\mathsf {\Pi }_{{\mathsf {BS}}}$$ and $$\mathsf {\Pi }_{{\mathsf {OTE}}}$$ , to support secure wildcard search over encrypted data. Protocols $$\mathsf {\Pi }_{\mathsf {OXT}}$$ and $$\mathsf {\Pi }_{{\mathsf {BS}}}$$ reduce the problem of secure wildcard search to that of boolean search. The search time in $$\mathsf {\Pi }_{\mathsf {OXT}}$$ and $$\mathsf {\Pi }_{{\mathsf {BS}}}$$ is sub-linear in the number of keywords. $$\mathsf {\Pi }_{\mathsf {OXT}}$$ and $$\mathsf {\Pi }_{{\mathsf {BS}}}$$ do not rule out false positives completely, but our experiment results indicate that the false positive rate of both the protocols is very less. Our third protocol $$\mathsf {\Pi }_{{\mathsf {OTE}}}$$ utilizes Oblivious Transfer Extension protocols to achieve linear time wildcard search with no false positive. $$\mathsf {\Pi }_{\mathsf {OXT}}$$ / $$\mathsf {\Pi }_{{\mathsf {BS}}}$$ and $$\mathsf {\Pi }_{{\mathsf {OTE}}}$$ can be easily combined to obtain the first construction that addresses the problem of wildcard search in the three-party setting achieving sub-linear search time with no false positives or false negatives. We provide performance analysis based on our prototype implementations to depict the feasibility of our proposed constructions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink