Prova de conhecimento nulo baseada em isomorfismo de subgrafos

Abstract

It is known that the problem of graph isomorphism has a perfect zero-knowledge proof system, but a security analysis to determine if the problem of subgraph isomorphism satisfies the three conditions of zero-knowledge proof system has not yet been proposed. In this work was done an analysis of zero knowledge proof system based on subgraphs isomorphism,which is a harder problem to solve computationally to be in class N P-complete. In this paper it’s verified that the zero-knowledge proof system based on subgraphs isomorphism satisfies the three conditions: completeness, validity and perfect zero-knowledge proof. It was also submitted an isomorphic subgraphs generator that creates instances of graphs and subgraphs with high probability of not being an instance that can be solved in polynomial time by algorithms currently known.