In this paper we investigate the security of the server aided
RSA protocols
RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai resp.~Matsumoto,
Imai,
Laih and Yen. There a smart card wishes to calculate an RSA signature
and wants computational assistance from a untrusted powerful
server. We focus on generic attacks, that is, attacks that
do not exploit any special properties of the encoding of the group
elements.
The notion of generic attacks has been introduced by Shoup.
We prove lower bounds for the complexity of generic attacks on these two
protocols and show that the bounds are sharp by describing attacks that
almost
match our lower bounds. To the best of our knowledge these are the first
security proofs for efficient server aided RSA protocols.

In this paper we investigate the security of the server aided
RSA protocols RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai
resp. Matsumoto, Imai, Laih and Yen. We prove lower bounds for the
complexity of attacks on these protocols and show that the bounds are
sharp by describing attacks that almost match our lower bounds. To the
best of our knowledge these are the first lower bounds for efficient
server aided RSA protocols.