Susan Hohenberger, Anna Lysyanskaya. “How to Securely Outsource Cryptographic Computations.” TCC 2005.

“We address the problem of using untrusted (potentially malicious) cryptographic helpers.(…) We present two practical outsource-secure schemes. Specifically, we show how to securely outsource modular exponentiation, which presents the computational bottleneck in most public-key cryptography on computationally limited devices. Without outsourcing, a device would need O(n) modular multiplications to carry out modular exponentiation for n-bit exponents. The load reduces to O(log²n) for any exponentiation-based scheme where the honest device may use two untrusted exponentiation programs; we highlight the Cramer-Shoup cryptosystem and Schnorr signatures as examples.”