Sorting of Fully Homomorphic Encrypted Cloud Data: Can Partitioning be Effective?
- 1 June 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Services Computing
- Vol. 13 (3) , 545-558
Abstract
The challenge of maintaining confidentiality of stored data in cloud is of utmost importance to realize the potential of cloud computing as an emerging storage solution service. Storing data in encrypted form may solve the problem, but exposes data to an adversary for each required computation. This repeated encryption decryption also diminishes the essence of cloud for storing encrypted database and huge computation power of cloud remains unused. Fully homomorphic encryption (FHE) is an effective scheme to support arbitrary operations directly on encrypted data, but has serious performance issues. In this paper, we have considered sorting on encrypted data, which is a frequently required database operation. We have investigated the feasibility of performing comparison as well as partition based sort on CPA resistant FHE data and highlight an important observation that time requirement of partition based sort on FHE data is no better than comparison based sort owing to the underlying security of the cryptosystem. We identify the recrypt operation, which is the denoising step of FHE as the main reason of costly timing requirement of such operations. We propose a FHE specific two stage sorting technique termed as Lazy sort with reduced recrypt operation, which proves to be better in terms of performance on FHE data in comparison to partition as well as comparison sort. Finally, we provide some multi-core implementation results to show that with proper implementation tricks performance of FHE computations can be improved further.Keywords
This publication has 34 references indexed in Scilit:
- Privacy/performance trade-off in private search on bio-medical dataFuture Generation Computer Systems, 2013
- Accelerating Sorting of Fully Homomorphic Encrypted DataLecture Notes in Computer Science, 2013
- Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries2013
- CryptDBCommunications of the ACM, 2012
- Computing arbitrary functions of encrypted dataCommunications of the ACM, 2010
- Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers2010
- Faster Fully Homomorphic Encryption2010
- Deterministic and Efficiently Searchable Encryption2007
- Public Key Encryption with Keyword Search2004
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996