Abstract: As graph structure is widely applied in science and engineering, it has good practical value to design graph encryption algorithm. Since it is difficult to directly design an encryption algorithm for a graph, two methods are introduced to solve this problem. First, the advantages of 2D Ising model, such as simplicity and locality, are introduced to the design of encryption. Second, the problem of graph encryption is transferred to several simple problems. Encryption algorithms for one-dimension data, two-dimension data, tree-structure are proposed based on the improved Ising model. Finally, the graph encryption algorithm is implemented. Analysis and simulation demonstrate that the proposed method can fulfill basic requirements of graph encryption, including reversibility, adaptability, efficiency, randomness and diffusion.

Key words: graph, Ising model, encryption, tree, parallel computing