Nishanth Chandran

How to Delegate Secure Computation to the Cloud


We study the problem of multi-client verifiable computation, where multiple 
clients wish to securely outsource an arbitrary polynomial-time computation over 
their private inputs to a computationally powerful, yet untrusted, ``cloud'' server. 
We adopt the model of ``on-the-fly'' verifiable computation by Lopez-Alt, Tromer, and 
Vaikuntanathan [STOC 2012]. In this model, the clients can non-interactively 
upload their encrypted inputs to the cloud, independent of each other, and then 
later jointly decrypt the encrypted output received from the server. The complexity 
of each client is independent of the function being computed; yet, at the end, 
the clients will be assured that the result of the computation is correct, while at 
the same time protecting their data from the server and each other. 

In this work, we construct the first multi-client verifiable computation 
protocol that achieves simulation-based security against malicious clients and 
server who may be colluding with each other, while relying only on standard 
cryptographic hardness assumptions. In contrast, all prior works (including 
Lopez et al.) either rely on non-standard assumptions (such as non-falsifiable 
assumptions) or only provide security in weaker adversarial models such as 
non-colluding and/or semi-honest adversaries.

Joint work with Rosario Gennaro, Abhishek Jain, and Amit Sahai.