An exponentiation operation or other computational task associated with a cryptographic
protocol is performed in a secure distributed manner using multiple machines, e.g.,
a client device and multiple servers of a computer network. The computational task
is transformed by an originator machine before being sent to one or more external
servers for execution. The transformation may include replication and dependency
operations to provide robustness to errors in the computations performed by the
external servers, and blinding and permutation operations to provide privacy for
secret information associated with the computational task. The transformed computational
task is executed by the one or more external servers, and the results of the transformed
computational task are transmitted back to the originator machine. The originator
machine transforms the results of the transformed computational task in a manner
which permits verification that the one or more results are appropriate results
for a given input. Advantageously, the invention can operate with arbitrary inputs,
and provides improved computational efficiency relative to conventional techniques
for both small and large batches of cryptography-related computations.