Two efficient server-aided secret computation protocols based on the addition sequence

A server-aided secret computation protocol (SASC) is a method that allows a client (e.g. smart card) to compute a function efficiently with the aid of a powerful server (e.g. computer) without revealing the client's secrets to the server. Matsumoto et al. proposed a solution to the problem which is suitable for the RSA cryptosystem. Kawamura et al. have shown that a client, with a 105 times more powerful server's aid, can compute an RSA signature 50 times faster than the case without a server if the communication cost can be ignored. In this paper, we propose two SASC protocols based on the addition sequence to improve the efficiency. In the first protocol, since the addition sequence is determined by the server, it can improve the computational efficiency of the server only and it is suitable for the low speed communication link (e.g. 9.6 Kbps). It is expected that a client, with an 8982 times more powerful server's aid, can compute an RSA signature 50 times faster than the case without a server. In the second protocol, since the addition sequence is determined by the client, it can improve the computational efficiency of the client and server simultaneously but takes more communication time and it is suitable for the high speed communication link (e.g. above 10 Mbps). It is expected that a client, with a 3760 times more powerful server's aid, can compute an RSA signature 200 times faster than the case without a server.