Abstract:
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.

Abstract:
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.