In [7] we have proposed a model for the robust and private evaluation of a function within a group of cooperating mobile agents, called an agent Alliance. The model has been given abstractly and is based on a cryptographic protocol for secure multi-party computation. This paper aims on the investigation of the complexity of a threshold signature performed within the Alliance model. The goal is to achieve a practical security model in which agents can be allowed to act fully autonomously in their users name without relying on a trusted authority.