Fast server-aided secret computation protocols for modular exponentiation

Four efficient server-aided computation protocols for the modular exponentiation operation are proposed. The server-aided computation protocol is a two-party protocol between the client and the server. This protocol has two objectives. The first is to allow the client to borrow the computational power from the server to reduce the computation time. Note that the server is powerful, but restricted to polynomial time. The second objective is to keep the client´s exponent secret from the server. Efficient and secure protocols which disclose no knowledge about the secret exponent are proposed. The protocols are based on efficient exponentiation algorithms. The computation time depends on the server´s power and the speed of the channel between the client and the server. The normalized computation time is introduced and used to evaluate the protocols. It is shown that, for typical parameters, the protocol is the most efficient one ever proposed to provide the highest security level