SILVEIRA, Alexandre Marques Albano da. Prova de conhecimento nulo baseada em isomorfismo de subgrafos. 2016. 71 f. - Dissertação - Universidade Federal do Ceará, Programa de Pós-Graduação em Engenharia Elétrica e da Computação, Sobral, 2016. / Submitted by Ana Márcia Sousa (marciasousa@ufc.br) on 2016-09-27T19:19:26Z No. of bitstreams: 1 2016_dis_amasilveira.pdf: 2117310 bytes, checksum: 6b88cca547d0bba5997848623e044f37 (MD5) / Approved for entry into archive by Ana Márcia Sousa (marciasousa@ufc.br) on 2016-09-27T19:43:52Z (GMT) No. of bitstreams: 1 2016_dis_amasilveira.pdf: 2117310 bytes, checksum: 6b88cca547d0bba5997848623e044f37 (MD5) / Made available in DSpace on 2016-09-27T19:43:52Z (GMT). No. of bitstreams: 1 2016_dis_amasilveira.pdf: 2117310 bytes, checksum: 6b88cca547d0bba5997848623e044f37 (MD5) Previous issue date: 2015-12-03 / 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. / Sabe-se que o problema de isomorfismo de grafos tem um perfeito sistema de prova de conhecimento nulo, mas uma análise de segurança para saber se o problema de isomorfismo de subgrafo satisfaz as três condições de sistema de prova de conhecimento nulo ainda não foi proposta. Neste trabalho foi realizada uma análise de sistema de prova de conhecimento nulo baseado em isomorfismo de subgrafos, que é um problema mais árduo de se resolver computacionalmente por estar na classe N P-completo. Neste trabalho foi verificado que o sistema de prova de conhecimento nulo baseado em isomorfismo de subgrafos satisfaz as três condições: completude, validade e perfeita prova de conhecimento nulo. Também foi apresentado um gerador de subgrafos isomorfos que cria instâncias de grafos e subgrafos com alta probabilidade de não serem uma instância que possa ser resolvida em tempo polinomial pelos algoritmos conhecidos atualmente.