Sorting problem in fully homomorphic encrypted data

Official URL: http://risc01.sabanciuniv.edu/record=b1589812 (Table of Contents)

Fully Homomorphic Encryption (FHE) schemes allow users to perform computations over encrypted data without decrypting the ciphertext. This is possible via two operations which are bitwise addition and multiplication, namely logical XOR and logical AND operations, which can be applied over the bits individually encrypted under the fully homomorphic encryption scheme. Since any Boolean circuit can be realized using only AND and XOR gates, they can be used to build circuits for the computation of even more complicated operations over encrypted data. This property of FHE cryptosystems is especially useful in cloud computing applications, since data owners who use cloud computing for storage and computation, usually tend not to trust servers and for security reasons, they prefer storing their data in encrypted form. By using FHE cryptographic primitives, now servers are allowed to perform any desired task over the encrypted user data without the knowledge of secret key or plaintext. In this thesis, we focus on solving one such task that cloud server performs over encrypted data; sorting the elements of an integer array. We introduce two sorting schemes, both of which are capable of e ciently sorting data in fully homomorphic encrypted form. The technique is obtained by focusing on the minimization of the depth of the sorting circuit in addition to more traditional metrics such as the number of comparisons. The reduced depth of the sorting network allows a slower growth in the noise of encrypted bits and thereby makes it possible to select smaller parameter sizes for the underlying homomorphic encryption scheme resulting in much faster computation of homomorphic sorting. We present a leveled/batched implementation for the proposed sorting algorithms, using an NTRU based homomorphic encryption library, which yields significant improvements over classical sorting algorithms.