Evaluating performance of homomorphic encryption applied on delta encoding

Abstract: Homomorphic encryption is an encryption scheme that allows for simple operations on encrypted data. These operations are mainly boolean circuits combined into more complexarithmetic operations, rotations, and others. Homomorphic encryption was first implemented in 2009, and in the following decade, many different versions emerged. The early schemes were mainly proof of concepts. In contrast, the later schemes have been used in practical applications such as databases where queries were done without any decryption on the server. Another practical example is genome sequencing which benefits from utilizing supercomputers but the data is very sensitive. With the help of homomorphic encryption it was shown that this could be done without having any unencrypted data on the server. While these applications have different success rates, a field that have not been investigated is the use of homomorphic encryption with delta encoding. Delta encoding is a method of encoding a set (e.g., a set of characters) such that the set is expressed as an original (a starting point) with deltas (changes). A typical use case for delta encoding is: A user wants to edit a file located on the cloud and to save bandwidth, the user could encode a delta locally. This delta could then be sent to the cloud service and decoded together with the original version to create the updated version on the cloud. However, there is a privacy infringement risk with this. When standard encryption is used, the delta and the original must be decrypted to perform the decoding. If a malicious actor gains access to the data on the cloud machine, they would then have access to unencrypted data. For example, the cloud provider could snoop on its customers or have a policy that lets them use the users’ data. Homomorphic encryption would make it much harder since the data would still be encrypted while the decoding is performed. However, homomorphic encryption comes with a great overhead and is complex to tune, even with today’s libraries.To investigate the combination of homomorphic encryption and delta encoding, a testbed is created where a client and server act as user and cloud provider. Thetest bed consists of different configurations of delta encodings and homomorphic encryption schemes running different test cases. The configurations range from non-encrypted to homomorphically encrypted with different kinds of delta encodings to investigate the performance overhead of utilizing homomorphic encryption. The different tests are created to show what kind of overhead can be expected in different scenarios and which operations take the most time. With this testbed and these test cases, the results showed a substantial overhead with using homomorphic encryption. However, many optimizations could be done to increase efficiency and make homomorphic encryption a viable solution. For example, the decoding algorithm could be optimized to use homomorphic operations more efficiently. The tests showed that most of the runtime, when using homomorphic encryption, is on the server. Most of the runtime for the client are one-time operations, which consist of creating keys that can be reused.