Paper 2015/995

Updates on Sorting of Fully Homomorphic Encrypted Data

Nitesh Emmadi, Praveen Gauravaram, Harika Narumanchi, and Habeeb Syed

Abstract

In this paper, we show implementation results of various algorithms that sort data encrypted with Fully Ho- momorphic Encryption scheme based on Integers. We analyze the complexities of sorting algorithms over encrypted data by considering Bubble Sort, Insertion Sort, Bitonic Sort and Odd- Even Merge sort. Our complexity analysis together with imple- mentation results show that Odd-Even Merge Sort has better performance than the other sorting techniques. We observe that complexity of sorting in homomorphic domain will always have worst case complexity independent of the nature of input. In addition, we show that combining different sorting algorithms to sort encrypted data does not give any performance gain when compared to the application of sorting algorithms individually.

Note: This paper has been accepted in the 3rd International Conference on Cloud Computing Research and Innovation (Cloud Asia R&D 2015) (http://www.ngp.org.sg/ICCCRI2015/?q=2015programlist).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. 3rd International Conference on Cloud Computing Research and Innovation (Cloud Asia R&D 2015)
Keywords
Fully Homomorphic EncryptionCloud ComputingSorting
Contact author(s)
praveen gauravaram @ qut edu au
History
2015-10-14: received
Short URL
https://ia.cr/2015/995
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/995,
      author = {Nitesh Emmadi and Praveen Gauravaram and Harika Narumanchi and Habeeb Syed},
      title = {Updates on Sorting of Fully Homomorphic Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2015/995},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/995}},
      url = {https://eprint.iacr.org/2015/995}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.