The border gateway protocol (BGP) has been used for internet interdomain routing since 1989. However, this protocol has many security vulnerabilities, and is therefore the focus of ongoing research. A fast and efficient protocol, with strong security features, including signature based authentication is ideal. Some alternatives to BGP have previously been proposed for implementation, but these are yet to be adopted. Computational overheads and infrastructure requirements on the network system, or the absence of some key security features are preventing their adoption. In this paper, we introduce a protocol with significant improvements to BGP, addressing its three major security vulnerabilities. We propose a newprotocol from a concept within in the append only signature (AOS) scheme, but in a more realistic broadcast model. Our protocol has better efficiency and security, by using pre-computation of signatures, and server aided verification. We also include signature aggregation features to minimise signature size, to further improve efficiency.