Multi-round passive attacks on server-aided RSA protocols
Johannes Merkle · 2000
At Crypto'88, Matsumoto, Kato, and Imai presented two server-aided RSA protocols, RSA-S1 and RSA-S2, which speed up a clients RSA signature generation by interacting with a computationally strong but untrusted server. These protocolls are quite attractive by their efficiency, but unfortunately they are susceptible to multi-round active attacks. Therefore, on Eurocrypt'92, Pfitzmann and Waidner suggested to renew the decomposition of the secret key after each signature generation. In this paper we show that in this case the non-binary version of RSA-S1 becomes totally insecure. Our experiments show that the secret key can be reconstructed very efficiently by lattice reduction using the data obtained by the server during some executions of the protocol. On the other hand we show that if the decomposition of the secret key is slightly modified, our attacks become inefficient. This modification does not significantly affect the efficiency of the protocol. Furthermore, we present a very sim...