This paper proposes a secure routing protocol based on an ad-hoc on-demand distance vector (AODV) that successfully achieves both security and communication efficiency. Although many studies have previously discussed such a secure protocol, the conventional methods significantly degrade the communication efficiency because of large packets and complex communication procedures. The proposed method allows the intermediate node to generate a route reply (RREP). This is impossible in conventional methods due to the restriction of digital signatures in route requests (RREQ). In the proposed method, each intermediate node holds a packet received from a specific node in the past, and appends the held packet to the RREQ of another node and generates its own signed RREP. This procedure guarantees that the third party holds the route to the destination. It is shown that the proposed method outperforms conventional secure protocols in terms of network load.