Virtual Outsourcing of Verifiable Computation with Function Hiding

Abstract

For thousands of years, humans have utilized machinery to solve computational problems out of the reach of the human mind. While the problems have become more and more complex, the machines that are used to solve these problems have become smaller and smaller. This has paved the road for a concept known as computation outsourcing which is based on having small devices send the problem to larger machines that are better equipped to solve the problems of the users. This concept however, raises the questions of whether the solutions received in such a outsourcing process can be trusted or not and how to be able to outsource the computations without disclosing any private information. This thesis analyses the state-of-the-art of the cryptographic primitives for verifying data received from outsourced computations and strategies for hiding the input data and functions. The thesis further looks at different solutions that combine the analysed concepts in order to create a verifiable outsourced hidden computation scheme. An implementation of such methods in the form of a python program called SimpleUCEvaluator which evaluates universal circuits using a Yao’s garbled circuit evaluator implementation is created and the performance of the program is analysed. The result indicates that current state-of-the-art techniques are not quite efficient enough to truly be used in practice. The process of transforming a program into a universal circuit and the process of generating a garbled circuit is very computationally expensive and, since there is no efficient way of using a garbled circuit more than once, this process can not be amortized over multiple evaluations. In some cases, SimpleUCEvaluator is slower by a factor of ten thousand when compared to the evaluation of a native version of the program. While in some cases, where the function must be kept hidden at all costs, this might be acceptable, in most cases this is too slow to be usable.