Sistema de prova de conhecimento nulo baseado em isomorfismo de subgrafos

Abstract

It is known that the graphs isomorphism problem (GI) has a perfect system of proof of knowledge, but a security analysis to determine if the subgraph isomorphism problem (SGI) meets the three conditions of zero-knowledge proof system was not proposed. If the GI problem was more general than the SGI, this analysis would not be necessary. But this is not the case. The SGI problem is more general than the GI problem, requiring a security analysis in the proposed of a zero-knowledge proof system. Therefore, this paper presents the details of safety analysis for the zero-knowledge proof system built from the subgraphs isomorphism problem.