Cloud computation enables users with computationally weak devices to outsource their computation to a server (aka the cloud). The recent widespread use of the cloud computation services provided by companies such as Microsoft , Amazon etc. has led cryptographers to focus on the security aspects of outsourcing computation. In particular, there have been a number of proposals for verifiable computation that allow a weak client to obtain the correct outcome of a computation, without revealing anything about the client's inputs to the server. However, all proposed solutions are highly inefficient in practice (from the client's perspective), due to their reliance on fully homomorphic encryption.