Reducing communication cost of encrypted data search with compressed Bloom filters

Muhammad Umer, Tahir Azim, Zeeshan Pervez

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Downloads (Pure)

Abstract

Consumer data, such as documents and photos, are increasingly being stored in the cloud. To ensure confidentiality, the data is encrypted before being outsourced. However, this makes it difficult to search the encrypted data directly. Recent approaches to enable searching of this encrypted data have relied on trapdoors, locally stored indexes, and homomorphic encryption. However, data communication cost for these techniques is very high and they limit search capabilities either to a small set of pre-defined trapdoors or only allow exact keyword matching. This paper addresses the problem of high communication cost of bloom-filter based privacy-preserving search for measuring similarity between the search query and the encrypted data. We propose a novel compression algorithm which avoids the need to send the entire encrypted bloom filter index back to the client. This reduces the cost of communicating results to the client by over 95%. Using sliding window bloom filters and homomorphic encryption also enables our system to search over encrypted data using keywords that only partially match the originally stored words. We demonstrate the viability of our system by implementing it on Google Cloud, and our results show that the cost of partially matching search queries on encrypted data scales linearly with the total number of keywords stored on the server.
Original languageEnglish
Title of host publication16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE
PublisherIEEE
Pages1-4
Volume16
ISBN (Electronic)978-1-5386-1465-5
ISBN (Print)978-1-5386-1464-8, 978-1-5386-1466-2
DOIs
Publication statusPublished - 11 Dec 2017

Fingerprint

Communication
Cryptography
Costs
Servers

Cite this

Umer, M., Azim, T., & Pervez, Z. (2017). Reducing communication cost of encrypted data search with compressed Bloom filters. In 16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE (Vol. 16, pp. 1-4). IEEE. https://doi.org/10.1109/NCA.2017.8171329
Umer, Muhammad ; Azim, Tahir ; Pervez, Zeeshan. / Reducing communication cost of encrypted data search with compressed Bloom filters. 16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE . Vol. 16 IEEE, 2017. pp. 1-4
@inproceedings{76cccd08cea5471e8bfc163cd016a90f,
title = "Reducing communication cost of encrypted data search with compressed Bloom filters",
abstract = "Consumer data, such as documents and photos, are increasingly being stored in the cloud. To ensure confidentiality, the data is encrypted before being outsourced. However, this makes it difficult to search the encrypted data directly. Recent approaches to enable searching of this encrypted data have relied on trapdoors, locally stored indexes, and homomorphic encryption. However, data communication cost for these techniques is very high and they limit search capabilities either to a small set of pre-defined trapdoors or only allow exact keyword matching. This paper addresses the problem of high communication cost of bloom-filter based privacy-preserving search for measuring similarity between the search query and the encrypted data. We propose a novel compression algorithm which avoids the need to send the entire encrypted bloom filter index back to the client. This reduces the cost of communicating results to the client by over 95{\%}. Using sliding window bloom filters and homomorphic encryption also enables our system to search over encrypted data using keywords that only partially match the originally stored words. We demonstrate the viability of our system by implementing it on Google Cloud, and our results show that the cost of partially matching search queries on encrypted data scales linearly with the total number of keywords stored on the server.",
author = "Muhammad Umer and Tahir Azim and Zeeshan Pervez",
year = "2017",
month = "12",
day = "11",
doi = "10.1109/NCA.2017.8171329",
language = "English",
isbn = "978-1-5386-1464-8",
volume = "16",
pages = "1--4",
booktitle = "16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE",
publisher = "IEEE",
address = "United States",

}

Umer, M, Azim, T & Pervez, Z 2017, Reducing communication cost of encrypted data search with compressed Bloom filters. in 16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE . vol. 16, IEEE, pp. 1-4. https://doi.org/10.1109/NCA.2017.8171329

Reducing communication cost of encrypted data search with compressed Bloom filters. / Umer, Muhammad ; Azim, Tahir; Pervez, Zeeshan.

16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE . Vol. 16 IEEE, 2017. p. 1-4.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Reducing communication cost of encrypted data search with compressed Bloom filters

AU - Umer, Muhammad

AU - Azim, Tahir

AU - Pervez, Zeeshan

PY - 2017/12/11

Y1 - 2017/12/11

N2 - Consumer data, such as documents and photos, are increasingly being stored in the cloud. To ensure confidentiality, the data is encrypted before being outsourced. However, this makes it difficult to search the encrypted data directly. Recent approaches to enable searching of this encrypted data have relied on trapdoors, locally stored indexes, and homomorphic encryption. However, data communication cost for these techniques is very high and they limit search capabilities either to a small set of pre-defined trapdoors or only allow exact keyword matching. This paper addresses the problem of high communication cost of bloom-filter based privacy-preserving search for measuring similarity between the search query and the encrypted data. We propose a novel compression algorithm which avoids the need to send the entire encrypted bloom filter index back to the client. This reduces the cost of communicating results to the client by over 95%. Using sliding window bloom filters and homomorphic encryption also enables our system to search over encrypted data using keywords that only partially match the originally stored words. We demonstrate the viability of our system by implementing it on Google Cloud, and our results show that the cost of partially matching search queries on encrypted data scales linearly with the total number of keywords stored on the server.

AB - Consumer data, such as documents and photos, are increasingly being stored in the cloud. To ensure confidentiality, the data is encrypted before being outsourced. However, this makes it difficult to search the encrypted data directly. Recent approaches to enable searching of this encrypted data have relied on trapdoors, locally stored indexes, and homomorphic encryption. However, data communication cost for these techniques is very high and they limit search capabilities either to a small set of pre-defined trapdoors or only allow exact keyword matching. This paper addresses the problem of high communication cost of bloom-filter based privacy-preserving search for measuring similarity between the search query and the encrypted data. We propose a novel compression algorithm which avoids the need to send the entire encrypted bloom filter index back to the client. This reduces the cost of communicating results to the client by over 95%. Using sliding window bloom filters and homomorphic encryption also enables our system to search over encrypted data using keywords that only partially match the originally stored words. We demonstrate the viability of our system by implementing it on Google Cloud, and our results show that the cost of partially matching search queries on encrypted data scales linearly with the total number of keywords stored on the server.

U2 - 10.1109/NCA.2017.8171329

DO - 10.1109/NCA.2017.8171329

M3 - Conference contribution

SN - 978-1-5386-1464-8

SN - 978-1-5386-1466-2

VL - 16

SP - 1

EP - 4

BT - 16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE

PB - IEEE

ER -

Umer M, Azim T, Pervez Z. Reducing communication cost of encrypted data search with compressed Bloom filters. In 16th International Symposium on Network Computing and Applications (NCA), 2017 IEEE . Vol. 16. IEEE. 2017. p. 1-4 https://doi.org/10.1109/NCA.2017.8171329