Performance Analysis of Server-Aided Secret Computation Protocols for the RSA Cryptosystem

Shin-ichi KAWAMURA  Atsushi SHIMBO  

IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.7   pp.1073-1080
Publication Date: 1990/07/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Cryptography and Information Security)
Category: Public-Key Systems

Full Text: PDF(609.8KB)>>
Buy this Article

Server-aided secret computation (SASC) protocols were proposed as methods to allow a not-so-powerful computer (a client) to compute a function efficiently with the aid of a powerful computer (a server) without revealing the client's secret to the server. A smart card system is considered to be the most promising application for SASC protocols. Matsumoto et al. proposed a class of protocols, called S2, which is suitable for RSA secret computation. It includes many variations, such as binary S2, non-binary S2, and KS schemes. Although it is expected that the non-binary S2 will be the most efficient scheme, performances for these protocols have not been fully analyzed, except for the KS scheme. This paper discusses how to determine appropriate parameters for non-binary S2. Performance was generally analyzed by using normalized variables. It is shown that a client can compute a signature 50 times faster, with a 105 times more powerful server's aid, than in the case without a server, provided that communication cost can be ignored. The SASC protocol performance is also discussed under the practical condition that a server is an 8-bit CPU and that the communication rate is 9.6 kbps. The client can sign a message in about 10 seconds, with the aid of a 32-bit CPU. This analysis coincides well with the experimental result. It is estimated that a client with a 16-bit CPU will accomplish a less that 2 second processing time with a 4.6 kbps server.