Search

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 $$\frac{3}{2}((\log k)-1)$$over the square-and-multiply algorithm, where kis the bitlength of the exponent.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 $$\frac{3}{2}((\log k)-1)$$over the square-and-multiply algorithm, where kis the bitlength of the exponent.