Na criptografia, uma prova de conhecimento (proof of knowledge) é um sistema de prova interativa no qual o provador consegue "convencer" um verificador de que detém uma determinada informação. O significado de uma máquina abstrata "saber algo" é definido em termos computacionais: uma máquina "sabe algo" se essa informação puder ser computada tomando a própria máquina como entrada. Como o programa do provador não necessariamente revela o conhecimento em si (como ocorre nas provas de conhecimento zero), introduz-se uma máquina com um programa distinto, chamada de extrator de conhecimento, para formalizar essa ideia. Esse conceito restringe-se principalmente ao que pode ser provado por máquinas limitadas a tempo polinomial. Nesse contexto, o conjunto de elementos de conhecimento limita-se a um conjunto de testemunhas de alguma linguagem formal em NP.
Seja uma afirmação da linguagem em NP, e o conjunto de testemunhas para que devem ser aceitas na prova. Isso permite definir a seguinte relação: .
Uma prova de conhecimento para a relação com erro de conhecimento é um protocolo de duas partes entre um provador e um verificador que satisfaz as duas propriedades a seguir:
Esta é uma definição mais rigorosa de Validade:
Seja uma relação de testemunha, o conjunto de todas as testemunhas para o valor público e o erro de conhecimento. Uma prova de conhecimento é -válida se existir uma máquina de tempo polinomial , com acesso de oráculo a , tal que, para todo , tenha-se e
O símbolo indica que a máquina de Turing não chegou a uma conclusão (ou falhou na extração).
O erro de conhecimento representa a probabilidade de o verificador aceitar mesmo quando o provador, na verdade, não conhece uma testemunha . O extrator de conhecimento é utilizado para formalizar o que se entende pelo conhecimento de uma máquina de Turing: se conseguir extrair a partir de , dizemos que conhece o valor de .
Essa definição da propriedade de validade combina os conceitos de validade e validade forte. Para erros de conhecimento negligenciáveis , como ou , ela pode ser considerada mais forte do que a solidez (soundness) de provas interativas comuns.
Para especificar uma prova de conhecimento, é necessário definir não apenas a linguagem, mas também as testemunhas que o provador deve conhecer. Em alguns casos, provar a pertinência a uma linguagem pode ser fácil, enquanto computar uma testemunha específica é computacionalmente difícil. O exemplo a seguir ilustra essa diferença:
Seja um grupo cíclico com gerador no qual se presume que o problema do logaritmo discreto seja difícil. Decidir a pertinência à linguagem é trivial, já que todo elemento pertence a ela. No entanto, encontrar a testemunha tal que equivale a resolver o problema do logaritmo discreto.
Uma das provas de conhecimento mais simples e amplamente utilizadas, a prova de conhecimento de um logaritmo discreto, foi proposta por Claus Schnorr. O protocolo é definido sobre um grupo cíclico de ordem com gerador .
Para provar o conhecimento de , o provador interage com o verificador em três etapas:
O verificador aceita a prova se .
Podemos confirmar que se trata de uma prova de conhecimento válida porque existe um extrator que opera da seguinte maneira:
Como , a saída do extrator é exatamente .
Este protocolo também é uma prova de conhecimento zero, embora essa propriedade não seja um requisito obrigatório para uma prova de conhecimento.
Protocolos que seguem essa estrutura de três movimentos (compromisso, desafio e resposta) são denominados protocolos sigma. O nome deriva da letra grega Sigma (), cujo formato em zigue-zague simboliza os três passos da interação, ou ainda de Sig (assinatura) e MA, abreviação de "Merlin-Arthur". Existem protocolos sigma para provar diversas afirmações, especialmente aquelas relacionadas a logaritmos discretos. Por meio dessas provas, o provador pode demonstrar não apenas o conhecimento do logaritmo discreto, mas também que ele satisfaz determinadas restrições algébricas. Por exemplo, é possível provar que dois logaritmos de e nas bases e são iguais ou obedecem a alguma relação linear. Para elementos e de , dizemos que o provador demonstra o conhecimento de e tais que e . A igualdade corresponde ao caso particular em que e . Como pode ser computado de forma trivial a partir de , isso equivale a provar o conhecimento de um tal que .
Essa é a intuição por trás da seguinte notação, amplamente usada na literatura para expressar o que está sendo demonstrado em uma prova de conhecimento:
que afirma que o provador conhece um valor que satisfaz a relação especificada.
As provas de conhecimento são ferramentas fundamentais para a construção de protocolos de identificação e, em sua variante não interativa, de esquemas de assinatura digital, como a Assinatura de Schnorr.
Elas também são amplamente empregadas na construção de sistemas de assinatura de grupo e de credenciais digitais anônimas.