Some active attacks on fast server-aided secret computation protocols for modular exponentiation

Abstract

Four server-aided secret computation protocols, Protocols 1, 2, 3, and 4, for modular exponentiation were proposed by Kawamura and Shimbo in 1993. By these protocols, the client can easily compute the modular exponentiation M(d) mod N with the help of a powerful server, where N is the product of two large primes. To enhance the security, the client was suggested to use a verification scheme and a slight modification on each proposed protocol. In this paper, we propose two new active attacks to break Protocols 3 and 4, respectively. Even if Protocols 3 and 4 have included the slight modification and verification, the untrusted server can still obtain the secret data d. The client cannot detect these attacks by the proposed verification. To adopt these new attacks, the difficulty of finding the value of the secret data d will be decreased drastically.