Implementation and optimization of a somewhat homomorphic encryption scheme

As cloud service providers improve their infrastructure, it is becoming increasingly attractive for users to move their programs and data to the cloud. This carries security risks, however, as users trust the provider to handle their private data correctly, without disclosing it our using it for their own benefit. A solution to this problem is for all data to be encrypted at all times, including when used by running applications. Homomorphic encryption schemes make this possible by allowing users to perform basic mathematical operations by operating directly with encrypted information. We implement a library for a somewhat homomorphic encryption scheme, capable of evaluating arithmetic circuits of limited complexity containing additions and multiplications. We analyze the performance of the library and identify bottlenecks, and propose and evaluate a set of optimizations. For practical applications" we include an expression evaluation function that signals whether the desired circuit can be evaluated by the scheme, depending on selected security parameters.