  As the cloud computing paradigm has gained prominence, the need for
verifiable computation has grown increasingly urgent. The concept of verifiable
computation enables a weak client to outsource difficult computations to a
powerful, but untrusted, server. Protocols for verifiable computation aim to
provide the client with a guarantee that the server performed the requested
computations correctly, without requiring the client to perform the
computations herself. By design, these protocols impose a minimal computational
burden on the client. However, existing protocols require the server to perform
a large amount of extra bookkeeping in order to enable a client to easily
verify the results. Verifiable computation has thus remained a theoretical
curiosity, and protocols for it have not been implemented in real cloud
computing systems.
  Our goal is to leverage GPUs to reduce the server-side slowdown for
verifiable computation. To this end, we identify abundant data parallelism in a
state-of-the-art general-purpose protocol for verifiable computation,
originally due to Goldwasser, Kalai, and Rothblum, and recently extended by
Cormode, Mitzenmacher, and Thaler. We implement this protocol on the GPU,
obtaining 40-120x server-side speedups relative to a state-of-the-art
sequential implementation. For benchmark problems, our implementation reduces
the slowdown of the server to factors of 100-500x relative to the original
computations requested by the client. Furthermore, we reduce the already small
runtime of the client by 100x. Similarly, we obtain 20-50x server-side and
client-side speedups for related protocols targeted at specific streaming
problems. We believe our results demonstrate the immediate practicality of
using GPUs for verifiable computation, and more generally that protocols for
verifiable computation have become sufficiently mature to deploy in real cloud
computing systems.
