  Discrete exponential operation, such as modular exponentiation and scalar
multiplication on elliptic curves, is a basic operation of many public-key
cryptosystems. However, the exponential operations are considered prohibitively
expensive for resource-constrained mobile devices. In this paper, we address
the problem of secure outsourcing of exponentiation operations to one single
untrusted server. Our proposed scheme (ExpSOS) only requires very limited
number of modular multiplications at local mobile environment thus it can
achieve impressive computational gain. ExpSOS also provides a secure
verification scheme with probability approximately 1 to ensure that the mobile
end-users can always receive valid results. The comprehensive analysis as well
as the simulation results in real mobile device demonstrates that our proposed
ExpSOS can significantly improve the existing schemes in efficiency, security
and result verifiability. We apply ExpSOS to securely outsource several
cryptographic protocols to show that ExpSOS is widely applicable to many
cryptographic computations.
