A New Transitively Closed Undirected Graph Authentication Scheme for Blockchain-Based Identity Management Systems

Blockchain can potentially be deployed in a wide range of applications due to its capability to ensure decentralization, transparency, and immutability. In this paper, we design a cryptographic membership authentication scheme (i.e., authenticating graph data) to support blockchain-based identity management systems (BIMS). Such a system is designed to bind a digital identity object to its real-world entity. Specifically, we introduce a new transitively closed undirected graph authentication (TCUGA) scheme, which only needs to use node signatures (e.g., certificates for identifying nodes). The trapdoor hash function used in our scheme allows the signer to efficiently update the certificates without the need to re-sign the nodes. In other words, our scheme is efficient even though the graph dynamically adds or deletes vertices and edges. Moreover, our proposal can efficiently provide a proof when the edge between two vertices does not exist, thus solving the existing intractability issue in transitive signature (the main tool for authenticating graph data). Finally, we prove the security of our proposed TCUGA in the standard model and evaluate its performance to show its feasibility for BIMS.