Outsourcing computation of modular exponentiations in cloud computing

Cloud computing is an emerging computing paradigm in which IT resources and capacities are provided as services over the Internet. Promising as it is, this paradigm also brings forth new challenges for security when users want to securely outsource the computation of cryptographic operations to the untrusted cloud servers. As we know, modular exponentiation is one of the basic operations among most of current cryptosystems. In this paper, we present the generic secure outsourcing schemes enabling users to securely outsource the computations of exponentiations to the untrusted cloud servers. With our techniques, a batch of exponentiations (e.g. t exponentiations) can be efficiently computed by the user with only O(n+t) multiplications, where n is the number of bits of the exponent. Compared with the state-of-the-art algorithm, the proposed schemes are superior in both efficiency and verifiability. Furthermore, there are not any complicated pre-computations on the user side. Finally, the schemes are proved to be secure under the Subset Sum Problem.