How Practical is Homomorphically Encrypted Program Execution? An Implementation and Performance Evaluation

Homomorphic cryptography has received a lot of attention due to potentially ground breaking advances in cryptography. However it is also surrounded by a lot of hyperbole such as "ground breaking advances", "this will solve all Cloud computing problems" to "it is completely impractical" and "it will never work for real world problems". In previous work we showed how homomorphic encryption can be used to execute arbitrary programs in encrypted space, showing that at least in theory real world problems can be computed protected by homomorphic cryptography without losing generality. In this paper we expand our work to evaluate how practical current homomorphic cryptography based on the Smart-Vercauteren system is for executing arbitrary programs on untrusted resources. For this we present the implementation of a method to compute non-linear secret programs on an untrusted resource using encrypted circuits embedded in an encrypted virtual machine. We successively show how a processor architecture using encrypted circuits can be implemented so it can support read and write memory access, dynamic parameters and non-linear programs that render branch-decisions at runtime. The system comprises the runtime environment for program execution and an assembler to generate the encrypted machine code. We present performance evaluation of the sub-components as well as the complete system. The system represents a flexible prototype for homomorphic program execution in software and system architecture.