Active trial-and-error attack on SASC protocols

SASC (Server-Aided Secret Computation) protocols enable a client (a smart card) to borrow computing power from a server (e.g., an untrustworthy auxiliary device like an ATM) without revealing its secret information. In this paper, we propose a new active attack on server-aided secret computation protocols. We describe our attack by using Beguin and Quisquater's protocol. (We modify the protocol in order to immunize it against Nguyen and Stern's lattice reduction attack.) The proposed attack reduces the search space P to 1/p + pP, where 0 < p < 1. It is 2√ P for optimal p. Practically, it effectively threatens SASC protocols because an attacker can choose an appropriate value p according to the situation. Therefore, the security parameters in the existing SASC protocols must be reconsidered.