Provas de conhecimento-zero

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em criptografia uma prova de conhecimento-zero ou protocolo de conhecimento-nulo é um método interativo que possibilita uma parte provar para outra que uma declaração (geralmente matemática) é verdadeira, sem contudo revelar qualquer coisa além da veracidade da declaração.

Exemplo abstrato[editar | editar código-fonte]

Zkip alibaba1.png
Zkip alibaba2.png
Zkip alibaba3.png

Existe uma história muito conhecida, que apresenta algumas das ideias da prova de conhecimento-zero, publicada primeiramente por Jean-Jacques Quisquater e outros no artigo "Como Explicar Protocolos de Conhecimento-Zero para suas Crianças".1 É prática comum rotular as duas partes em uma prova de conhecimento-zero como Priscila (a provadora da declaração) e Victor (o verificador da declaração).

Nesta história, Priscila descobriu a palavra secreta usada para abrir uma porta mágica em uma caverna. A caverna de formato circular, tem a entrada por um lado e a porta mágica bloqueando o lado oposto. Victor diz que vai pagar-lhe pelo segredo, mas não até que ele esteja certo de que ela realmente saiba o segredo. Priscila diz que vai contar-lhe o segredo, mas não até que ela receba o dinheiro. Eles bolam um esquema no qual Priscila pode provar que conhece o segredo, sem contudo contá-lo para Victor.

Primeiro, eles rotulam de A e B os caminhos à esquerda e à direita da entrada da caverna. Victor espera do lado de fora, enquanto Priscila entra na caverna, tomando o caminho A ou B aleatoriamente. Victor, então, entra na caverna e grita o nome do caminho A ou B, escolhido aleatoriamente, que ele deseja que ela use para retornar. Se Priscila realmente sabe a palavra mágica, isso é fácil: ela abre a porta, se necessário, e retorna ao longo do caminho desejado. Note-se que Victor não sabe por qual caminho ela entrou na caverna..

No entanto, supondo que ela não soubesse a palavra-mágica, ela só seria capaz de voltar pelo caminho escolhido por Victor se este fosse o mesmo caminho escolhido por ela para entrar. Uma vez que Victor iria escolher A ou B de forma aleatória, Priscila teria 50% de chance de adivinhar corretamente. Se fossem repetir este truque muitas vezes, por exemplo, 20 vezes seguidas, a chance de Priscila ser bem sucedida, prevendo todos os pedidos de Victor, se tornaria muito pequena.

Assim, se Priscila consegue sair da caverna pelos caminhos escolhidos por Victor, ele pode concluir que, muito provavelmente, ela conhece a palavra secreta.

Definição[editar | editar código-fonte]

A prova de conhecimento-zero deve satisfazer três propriedades:

  1. Integralidade: se a afirmação é verdadeira, um verificador honesto (isto é, aquele que segue o protocolo corretamente) vai ser convencido deste fato por um provador honesto.
  2. Corretude: se a afirmação é falsa, nenhum falso provador poderá convencer o verificador honesto de que a afirmação é verdadeira, exceto com alguma pequena probabilidade.
  3. Conhecimento-zero: se a afirmação é verdadeira, nenhum verificador simulado aprende outra coisa senão o fato de que a afirmação é verdadeira. Isto é formalizado mostrando-se que cada verificador enganoso tem algum simulador que, dado somente a instrução a ser provada (e sem acesso ao provador), pode produzir uma transcrição que "parece" uma interação entre o provador honesto e verificador enganoso.

As duas primeiras propriedades são também características dos sistemas de prova interativa. A terceira propriedade é o que faz a prova de conhecimento-nulo.

Provas de conhecimento-zero não são provas no sentido matemático do termo, porque existe uma probabilidade pequena, o erro da corretude, de que um provador fraudulento seja capaz de convencer o verificador com uma declaração falsa. Em outras palavras, elas são probabilísticas e não determinísticas. No entanto, existem técnicas para reduzir o erro de corretude a valores insignificantemente pequenos.

Exemplo prático[editar | editar código-fonte]

Podemos estender estas ideias para uma aplicação mais real de criptografia. Neste cenário, Priscila conhece o ciclo hamiltoniano para uma grande grafo, G. Victor conhece G, mas não o caminho (por exemplo Priscila gerou G e revelou a ele.) Priscila provará que sabe o caminho sem revelá-lo. Um ciclo hamiltoniano em um grafo é apenas uma maneira de implementar a prova de conhecimento-zero; de fato, qualquer problema NP-completo pode ser usado, como também outros problemas difíceis, como por exemplo, fatoração.2 Entretanto, Priscila não deseja simplesmente revelar o ciclo hamiltonianao ou qualquer outra informação para Victor; ela deseja manter o caminho em segredo (talvez Victor esteja interessado em comprá-lo, mas deseja, antes, obter verificação, ou talvez Priscila é a única a conhecer esta informação e está provando sua identidade para Victor).

Priscila, para mostrar que conhece o caminho hamiltoniano, joga várias rodadas do jogo com Victor.

  • No começo de cada rodada, Priscila cria H, um grafo isomórfico de G (isto é, H é semelhante a G, exceto que todos os vértices possuem nomes diferentes). Uma vez que é trivial traduzir um ciclo hamiltoniano entre grafos isomórficos, se Priscila conhece o ciclo hamiltoniano para G, ela também deve conhecer um para H.
  • Priscila compromete-se a H. Ela pode fazê-lo usando um esquema de compromisso. Alternativamente ela pode numerar os vértices de H e, para cada aresta de H, escrever uma pequena nota contendo os dois vértices da aresta e então colocar estas notas de cabeça para baixo sobre uma mesa. O propósito deste compromisso é que Priscila não seja capaz de modificar H, enquanto Victor ainda não tiver informação sobre H.
  • Victor, então, escolhe aleatoriamente uma ou duas questões para perguntar a Priscila. Ele tanto pode pedir a ela para mostrar o isomorfismo entre H e G ( ver problema do isomorfismo gráfico) ou o ciclo hamiltoniano em H.
  • Se Priscila é convidada a mostrar que os dois grafos são isomórficos, ela primeiramente revela todo H (por exemplo, virando as notas que ela colocou sobre a mesa) e então fornece os vértices que mapeiam G to H. Victor pode verificar que eles são realmente isomórficos.
  • Se Priscila é questionada a provar que conhce um ciclo hamiltoniano em H, ela traduz seu ciclo hamiltoniano de G para H e só revela as bordas sobre o ciclo hamiltoniano. Isto é suficiente para Victor verificar que H contém efectivamente um ciclo hamiltoniano.


Integridade:

Durante cada rodada, Priscila não sabe qual pergunta lhe será solicitada, até que forneça H a Victor. Portanto, para ser capaz de responder a ambos, H deve ser isomorfo a G e deve ter um ciclo hamiltoniano em H. Porque só alguém que conhece um ciclo hamiltoniano em G seria sempre capaz de responder a ambas as perguntas, Victor (depois de um número suficiente de rodadas) se convence de que Priscila realmente conhece essa informação.


Conhecimento-Zero:

As respostas de Priscila não revelam o ciclo hamiltoniano original em G. A cada rodada, Victor aprenderá apenas sobre o isomorfismo de H G ou um ciclo hamiltoniano em H. Ele precisaria de ambas as respostas para um único H a fim de descobrir o ciclo em G; assim, a informação permanece desconhecida, enquanto Priscila puder gerar um únicoH para cada rodada. Se Priscila desconhecesse um ciclo hamiltoniano em G, mas de alguma forma soubess de antemão que Victor pediria para ver cada rodada, então ela poderia enganar. Por exemplo, se Priscila sabia de antemão que Victor pediria para ver o ciclo hamiltoniano em H, então ela poderia gerar um ciclo hamiltoniano para um gráfico não relacionado. Da mesma forma, se Priscila sabia de antemão que Victor iria pedir para ver o isomorfismo, então ela poderia simplesmente gerar um grafoo isomórfico H(no qual ela também desconhece um ciclo hamiltoniano). Victor poderia simular o protocolo por si mesmo (sem Priscila) porque ele sabe o que vai pedir para ver. Assim, Victor não ganha informação alguma sobre o ciclo hamiltoniano em G a partir da informação revelada em cada rodada.


Corretude:

Se Priscila não sabe a informação, ela pode adivinhar qual questão Victor vai perguntar e gerar tanto um grafo isomórfico paraG como um ciclo hamiltoniano para um gráfico independente, mas uma vez que ela não sabe um ciclo hamiltoniano para G, ela não pode fazer ambos. Com este exercício de adivinhação, sua chance de enganar Victor é de 2n, onde n é o número de rodadas. Para todos os propósitos reais, é praticamente difícil derrotar uma prova de conhecimento-zero com um número razoável de rodadas desta forma.

Variantes do conhecimento-zero[editar | editar código-fonte]

Distintas variantes do conhecimento-zero podem ser definidas formalizando-se o conceito intuitivo do que se entende por a saída do simulador "parecendo" com a execução do protocolo de prova real das seguintes formas:

  • Fala-se de perfeito conhecimento-zero, se as distribuições produzidas pelo simulador e o protocolo de prova são distribuídos exatamente da mesma forma. Este é, por exemplo, o caso do primeiro exemplo acima.
  • Falamos de conhecimento-nulo computacional, se nenhum algoritmo eficiente pode distinguir as duas distribuições.

Aplicações[editar | editar código-fonte]

Pesquisas em provas de conhecimento-zero tem sido motivadas por sistemas de autenticação, onde uma parte quer provar a sua identidade a uma segunda parte através de alguma informação secreta (como uma senha), mas não quer a segunda parte aprenda nada sobre este segredo. Isso é chamado de "prova de conhecimento-nulo do conhecimento". No entanto, uma senha é normalmente muito pequena ou insuficientemente aleatória para ser usada em muitos esquemas para provas de conhecimento-zero de conhecimento. Uma prova de zero-conhecimento de senhas é um tipo especial de prova de conhecimento-zero do conhecimento que aborda o tamanho limitado de senhas.

Um dos mais fascinantes usos das provas de conhecimento-zero dentro de protocolos de criptografia é impor um comportamento honesto, enquanto preserva a privacidade. Grosso modo, a ideia é forçar um usuário a provar, usando uma prova de conhecimento-zero, que seu comportamento é correto de acordo com o protocolo. Por causa da propriedade de correture, sabemos que o usuário deve realmente agir com honestidade, a fim de ser capaz de fornecer uma prova válida. Devido ao conhecimento-zero, sabemos que o usuário não compromete a privacidade dos seus segredos durante o processo de fornecer a prova. Esta aplicação de provas de conhecimento-nulo foi utilizado pela primeira vez no documento inovador de Goldreich, Micali e Wigderson em computação multipartidárias segura.

Notas[editar | editar código-fonte]

  1. Jean-Jacques Quisquater, Louis C. Guillou, Thomas A. Berson. How to Explain Zero-Knowledge Protocols to Your Children. Advances in Cryptology - CRYPTO '89: Proceedings, v.435, p.628-631, 1990. pdf (em inglês)
  2. http://www.bennetyee.org/ucsd-pages/ZKP.html (em inglês)


Ligações externas[editar | editar código-fonte]