Anonymous routing where data packets can be routed efficiently while hiding the topology of the network from all nodes is a crucial part of achieving anonymity in an efficient anonymous network. Traditional routing protocols leak network topology information to nodes while existing anonymous routing protocols do not provide authentication for routing information. A malicious node can arbitrarily reduce the path cost value carried in an anonymous route announcement message for the purpose of negatively influencing routing efficiency or facilitating launching various attacks such as eavesdropping or man-in-the-middle attacks. In this paper we propose a generic scheme and a concrete instantiation to transform a routing protocol into an authenticated one in the sense that the path cost cannot be reduced by a malicious node.