Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/19802
Title in Portuguese: Prova de conhecimento nulo baseada em isomorfismo de subgrafos
Title: Zero-knowledge proof based in subgraph isomorphism
Author: Silveira, Alexandre Marques Albano da
Advisor(s): Nascimento, José Cláudio do
Keywords: Isomorfismo de subgrafos
Gerador de subgrafos
Issue Date: 3-Dec-2015
Publisher: Universidade Federal do Ceará
Citation: SILVEIRA, A. M. A. DA
Abstract in Portuguese: 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.
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.
Description: 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.
URI: http://www.repositorio.ufc.br/handle/riufc/19802
metadata.dc.type: Dissertação
Appears in Collections:PPGEEC - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2016_dis_amasilveira.pdfArquivo principal2,61 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.