Speeding up Exponentiation using an Untrusted Computational Resource

We present protocols for speeding up fixed-base variable-exponent exponentiation and variable-base fixed-exponent exponentiation using an untrusted computational resource. In the fixed-base protocols, the exponent may be blinded. In the variable-base protocols, the base may be blinded. The protocols are described for exponentiation in a cyclic group. We describe how to extend them to exponentiation modulo an integer where the modulus is the product of primes with single multiplicity. The protocols provide a speedup of over the square-and-multiply algorithm, where k is the bitlength of the exponent. One application of the protocols is to speed up exponentiation-based verification in discrete log-based signature and credential schemes. The protocols also allow signature verifiers to dynamically choose, for each message, the amount of work it would like to perform to verify the signature. This results in a work-security tradeoff. We introduce a fifth protocol to perform variable-base variable- exponent exponentiation, which also has this feature. Our model allows the trusted resource to perform computations in its idle time. The protocols facilitate the offloading of work to the offline stage, such that the work the trusted resource performs when it has to do an exponentiation is smaller. Our protocols are unconditionally secure.