Secure Server-Aided Signature Generation

(Title was Secure Outsourcing of Signature Generation) We study how to reduce the local computational cost associated with performing exponentiation. This involves transforming a large computational task into a large set of small computational tasks that are to be performed by a set of external servers who may all be controlled by one and the same adversary. In order to attach our problem, we introduce and employ the three principles of duplication, distribution and delegation. We apply our exponentiation scheme - which we show to be secure relative to the hidden subset sum problem - to performing inexpensive outsourcing of signature generation.