  In an emerging computing paradigm, computational capabilities, from
processing power to storage capacities, are offered to users over communication
networks as a cloud-based service. There, demanding computations are outsourced
in order to limit infrastructure costs. The idea of verifiable computing is to
associate a data structure, a proof-of-work certificate, to the result of the
outsourced computation. This allows a verification algorithm to prove the
validity of the result, faster than by recomputing it. We talk about a Prover
(the server performing the computations) and a Verifier. Goldwasser, Kalai and
Rothblum gave in 2008 a generic method to verify any parallelizable
computation, in almost linear time in the size of the, potentially structured,
inputs and the result. However, the extra cost of the computations for the
Prover (and therefore the extra cost to the customer), although only almost a
constant factor of the overall work, is nonetheless prohibitive in practice.
Differently, we will here present problem-specific procedures in computer
algebra, e.g. for exact linear algebra computations, that are Prover-optimal,
that is that have much less financial overhead.
