. Awell-known cryptographic scenario is the following: a smart card wishes to compute an RSA signature with the help of an untrusted powerful server. Several protocols have been proposed to solve this problem, and many have been broken. There exist two kinds of attacks against such protocols: passive attacks (where the server follows the instructions) and active attacks (where the server may return false values). An open question in this field is the existence of efficient protocols (without expensive precomputations) provably secure against both passive and active attacks. At Crypto '95, B'eguin and Quisquater tried to answer this question by proposing an efficient protocol which was resistant against all known passive and active attacks. In this paper, we present a very effective lattice-based passive attack against this protocol. An implementation is able to recover the secret factorization of an RSA-512 or RSA-768 key in less than 5 minutes once the card has produced about 50 signa...