AbstractThe edge authentication of graphs has been studied in the literature because graphs are one of the most widely used data organization structures. The majority of such schemes cannot be used to authenticate general directed graphs (GDGs); other schemes cannot be used for addressing either the issue of dynamic update or the issue of information leakage (such as the existence of nodes/edges and structural relationship of the graph). Also, all the existing schemes do not consider the forward security: if the signer’s secret key has been compromised, all previously generated signatures remain valid. This property provides high-level security protection for authentication schemes. To address these issues, in this work, we propose a forward-secure edge authentication scheme for GDGs. Observe that existing such schemes can only give a proof such that ‘there is an edge between nodes $u$ and $v$’. Our scheme, however, can directly give a proof such that ‘there is no edge between nodes $u$ and $v$’, which makes the function of edge authentication schemes more diverse. Moreover, our proposed scheme is proven to be secure against an adaptive chosen-message adversary in the random oracle model. To show its desirable performance, we analyze the computational costs of our scheme and compare it with other related schemes in terms of features.