Sistema de prova de conhecimento nulo baseado em isomorfismo de subgrafos

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.