Sistema de prova de conhecimento nulo baseado em isomorfismo de subgrafos

Alexandre Marques Albano da Silveira, Joseph Soares Alcantara, José Cláudio do Nascimento

DOI: 10.14209/sbrt.2015.139

Evento: XXXIII Simpósio Brasileiro de Telecomunicações (SBrT2015)

Keywords: encryption subgraph isomorphism problem zero knowledge proof.

Abstract

Sabe-se que o problema do isomorfismo de grafos (GI) tem um perfeito sistema de prova de conhecimento, mas uma analise de seguranc¸a para determinar se o problema de ´ isomorfismo de subgrafo (SGI) satisfaz as tres condic¸ ˆ oes de ˜ sistema de prova de conhecimento nulo ainda nao foi proposta. Se ˜ o problema GI fosse mais geral que o SGI, esta analise n ´ ao seria ˜ necessaria. Mas esse n ´ ao˜ e o caso. O problema ´ SGI e mais geral ´ do que o problema GI, requerendo uma investigac¸ao detalhada. ˜ Portanto, esse trabalho traz os detalhes da analise de seguranc¸a ´ para o sistema de prova de conhecimento nulo constru´ıdo a partir do problema de isomorfismo de subgrafos.

Download