Sorting method for fully homomorphic encrypted data using the cryptographic single-instruction multiple-data operation

Abstract

As the amount of data in the cloud grows, the challenge of protecting data privacy of stored data in cloud is of significant importance. Data privacy can be achieved by storing data in encrypted form, but there are some technical issues performing operations over encrypted data. Therefore, Fully homomorphic encryption(FHE) scheme is a very suitable approach to delegate the ability to perform arbitrary operations securely without any exposure of the data privacy. Moreover, owing to the cloud server performing storage service mainly, sorting on encrypted data using FHE is a very important operation. In this dissertation, we focus on encrypted data processing and analyze security requirements. First, we present a new similarity-based multi-keyword search scheme for encrypted data without sorting method for encrypted data, and we provide the security and performance analysis of the scheme. Since the computed statistic values for search are not encrypted form in this scheme, we indicate security concerns in search process. Second, to complement the security problems, we suggest a faster (wall-clock time) sorting method for numerical data subjected to FHE. The proposed algorithm utilizes the cryptographic single-instruction multiple-data (SIMD) operation, which is supported by most existing FHE algorithms. We also provide an analytic method for FHE applications by the estimation of the number of required recryption operations, which are the computationally dominant operations in FHE, and verify the method.