Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/19802
Título: Prova de conhecimento nulo baseada em isomorfismo de subgrafos
Título em inglês: Zero-knowledge proof based in subgraph isomorphism
Autor(es): Silveira, Alexandre Marques Albano da
Orientador(es): Nascimento, José Cláudio do
Palavras-chave: Isomorfismo de subgrafos
Gerador de subgrafos
Data do documento: 3-Dez-2015
Editor: Universidade Federal do Ceará
Citação: SILVEIRA, A. M. A. DA
Resumo: 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.
Descrição: 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
Aparece nas coleções:PPGEEC - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2016_dis_amasilveira.pdfArquivo principal2,61 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.