One method to reduce the computational costs of generating public key signatures on constrained devices is to get help from a verifiable server. In this paper, we propose a (verifiable) server assisted signature protocol which is the first one that totally elliminates public key operations for the ordinary user. Our protocol is also more efficient and flexible in terms of storage since unlike previous ones the user does not need to save the server?s signatures to prove its cheating.