New Algorithms for Secure Outsourcing of Modular Exponentiations

Modular exponentiations have been considered the most expensive operation in discrete-logarithm based cryptographic protocols. In this paper, the authors propose a new secure outsourcing algorithm for exponentiation modular a prime in the one-malicious model. Compared with the state-of-the-art algorithm, the proposed algorithm is superior in both efficiency and checkability. They, then utilize this algorithm as a subroutine to achieve outsource-secure Cramer-Shoup encryptions and Schnorr signatures. Besides, they propose the first outsource-secure and efficient algorithm for simultaneous modular exponentiations. Moreover, they prove that both the algorithms can achieve the desired security notions.