Abstract
As cloud computing has become prominent, the need for searching cloud data has grown increasingly urgent. However, cloud search may be incorrect due to errors of cloud providers and attacks from other malicious tenants. Previous work on verifiable computing returns results with probabilistically checkable proofs, which targets at different applications other than search and requires a large computation overhead. We propose a hybrid approach for generating proofs of cloud search results. Specifically, we model search indices as sets and search operations as set intersections, and build proofs based on RSA accumulators and aggregated membership and no membership witnesses. Because generating witnesses for large sets is computationally expensive, we employ interval-based witnesses for fast proof generation. To reduce proof size, our hybrid method uses Bloom filters when set difference is large. Evaluation on real datasets shows that our hybrid approach generates proofs in an average of 0.197s, up to 83.2% faster than previous work with a smaller proof size. Experiments also show our approach allows incremental updates with constant cost.
Original language | English |
---|---|
Title of host publication | Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015 |
Publisher | IEEE |
Pages | 504-513 |
Number of pages | 10 |
ISBN (Electronic) | 9781479986484 |
DOIs | |
Publication status | Published - 17 Jul 2015 |
Event | 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015 - Hyderabad, India Duration: 25 May 2015 → 29 May 2015 |
Conference
Conference | 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015 |
---|---|
Country/Territory | India |
City | Hyderabad |
Period | 25/05/15 → 29/05/15 |
Keywords
- Bloom filter
- RSA accumulator
- Verifiable computing
ASJC Scopus subject areas
- Computer Networks and Communications