Na criptografia, uma prova de conhecimento zero (também conhecida como prova ZK ou ZKP, do inglês zero-knowledge proof) é um protocolo no qual uma parte (o provador) pode convencer outra parte (o verificador) de que uma determinada afirmação é verdadeira, sem transmitir ao verificador qualquer informação além do mero fato de que a afirmação é verdadeira. A intuição por trás da não trivialidade das provas de conhecimento zero é que é trivial provar a posse de uma informação relevante simplesmente revelando-a; a parte difícil é provar essa posse sem revelar a informação (ou qualquer aspecto dela).
Considerando que alguém deve ser capaz de gerar uma prova de alguma afirmação apenas quando estiver de posse de certa informação secreta conectada à afirmação, o verificador, mesmo após ter se convencido da veracidade da afirmação por meio de uma prova de conhecimento zero, deve, no entanto, permanecer incapaz de provar a afirmação a terceiros.
As provas de conhecimento zero podem ser interativas, o que significa que o provador e o verificador trocam mensagens de acordo com algum protocolo, ou não interativas, o que significa que o verificador é convencido por uma única mensagem do provador e nenhuma outra comunicação é necessária. No modelo padrão, a interação é exigida, exceto para provas triviais de problemas BPP. Nos modelos de string aleatória comum e oráculo aleatório, existem provas de conhecimento zero não interativas. A Heurística de Fiat–Shamir pode ser usada para transformar certas provas de conhecimento zero interativas em não interativas.
Exemplos abstratos
A prova da carta vermelha Um exemplo de prova de conhecimento zero sem matemática é se Peggy quiser provar a Victor que ela tirou uma carta vermelha de um baralho padrão de 52 cartas, sem revelar qual carta vermelha específica ela possui. Victor observa Peggy tirar uma carta ao acaso do baralho embaralhado, mas ela mantém a carta virada para baixo para que ele não possa vê-la.
Para provar que sua carta é vermelha sem revelar sua identidade, Peggy pega as 51 cartas restantes do baralho e mostra sistematicamente a Victor todas as 26 cartas pretas (as 13 de espadas e 13 de paus) uma a uma, colocando-as viradas para cima na mesa. Como um baralho padrão contém exatamente 26 cartas vermelhas e 26 pretas, e Peggy demonstrou que todas as cartas pretas permanecem no baralho, Victor pode concluir com certeza que a carta escondida de Peggy deve ser vermelha.
Esta prova é de conhecimento zero porque Victor aprende apenas que a carta de Peggy é vermelha, mas não obtém informações sobre se é de copas ou ouros, ou qual carta vermelha específica ela possui. A prova seria igualmente convincente se Peggy estivesse com o Ás de Copas ou o Dois de Ouros. Além disso, mesmo que a interação fosse gravada, a gravação não revelaria a carta específica de Peggy a observadores futuros, mantendo a propriedade de conhecimento zero.
Se Peggy estivesse mentindo e na verdade tivesse uma carta preta, ela seria incapaz de produzir todas as 26 cartas pretas do restante do baralho, tornando a decepção impossível. Isso demonstra a solidez do sistema de prova. Este tipo de prova física de conhecimento zero usando cartas de baralho padrão pertence a uma classe mais ampla de protocolos criptográficos baseados em cartas que permitem aos participantes realizar computações seguras usando objetos cotidianos.
Onde está o Wally?
Outro exemplo bem conhecido de prova de conhecimento zero é o exemplo "Onde está o Wally?". Neste exemplo, o provador quer provar ao verificador que sabe onde Wally está em uma página de um livro Onde está Wally?, sem revelar sua localização ao verificador.
O provador começa pegando uma grande cartolina preta com um pequeno buraco, do tamanho do Wally. A cartolina tem o dobro do tamanho do livro em ambas as direções, para que o verificador não possa ver em que parte da página o provador a está colocando. O provador então posiciona a cartolina sobre a página de modo que Wally apareça no buraco.
O verificador pode agora olhar pelo buraco e ver o Wally, mas não consegue ver nenhuma outra parte da página. Portanto, o provador provou ao verificador que sabe onde Wally está, sem revelar qualquer outra informação sobre sua localização.
Este exemplo não é uma prova de conhecimento zero perfeita, porque o provador revela algumas informações sobre a localização de Wally, como a posição de seu corpo. No entanto, é uma ilustração decente do conceito básico de uma prova de conhecimento zero.
A caverna de Ali Babá
Existe uma história bem conhecida que apresenta as ideias fundamentais das provas de conhecimento zero, publicada pela primeira vez em 1990 por Jean-Jacques Quisquater e outros em seu artigo "Como explicar protocolos de conhecimento zero para seus filhos". As duas partes na história são Peggy como a provadora da afirmação, e Victor, o verificador da afirmação.
Nesta história, Peggy descobriu a palavra secreta usada para abrir uma porta mágica em uma caverna. A caverna tem o formato de um anel, com a entrada de um lado e a porta mágica bloqueando o lado oposto. Victor quer saber se Peggy conhece a palavra secreta; mas Peggy, sendo uma pessoa muito reservada, não quer revelar seu conhecimento (a palavra secreta) a Victor nem revelar o fato de seu conhecimento ao mundo em geral.
Eles rotulam os caminhos da entrada como A e B. Primeiro, Victor espera do lado de fora da caverna enquanto Peggy entra. Peggy segue pelo caminho A ou B; Victor não tem permissão para ver qual caminho ela toma. Então, Victor entra na caverna e grita o nome do caminho que deseja que ela use para retornar, seja A ou B, escolhido ao acaso. Desde que ela realmente conheça a palavra mágica, isso é fácil: ela abre a porta, se necessário, e retorna pelo caminho desejado.
No entanto, suponha que ela não soubesse a palavra. Então, ela só seria capaz de retornar pelo caminho nomeado se Victor desse o nome do mesmo caminho pelo qual ela entrou. Como Victor escolheria A ou B ao acaso, ela teria 50% de chance de adivinhar corretamente. Se eles repetissem esse truque muitas vezes, digamos 20 vezes seguidas, a chance de ela antecipar com sucesso todos os pedidos de Victor seria reduzida para 1 em 220, ou 9,54 × 10−7.
Assim, se Peggy aparece repetidamente na saída que Victor nomeia, ele pode concluir que é extremamente provável que Peggy, de fato, conheça a palavra secreta.
Observação externa Em relação a observadores terceiros: mesmo que Victor esteja usando uma câmera escondida que grave toda a transação, a única coisa que a câmera registrará é, em um caso, Victor gritando "A!" e Peggy aparecendo em A ou, no outro caso, Victor gritando "B!" e Peggy aparecendo em B. Uma gravação desse tipo seria trivial para quaisquer duas pessoas falsificarem (bastando que Peggy e Victor concordem previamente com a sequência de As e Bs que Victor gritará). Tal gravação certamente nunca será convincente para ninguém além dos participantes originais. Na verdade, até mesmo uma pessoa que esteve presente como observadora no experimento original não deveria se convencer, já que Victor e Peggy poderiam ter orquestrado todo o "experimento" do início ao fim.
Além disso, se Victor escolher seus As e Bs jogando uma moeda diante da câmera, este protocolo perde sua propriedade de conhecimento zero; o lançamento da moeda na câmera provavelmente seria convincente para qualquer pessoa que assistisse à gravação mais tarde. Assim, embora isso não revele a palavra secreta a Victor, torna possível para Victor convencer o mundo em geral de que Peggy possui esse conhecimento — contrariando os desejos declarados de Peggy. No entanto, a criptografia digital geralmente "joga moedas" baseando-se em um gerador de números pseudoaleatórios, que é semelhante a uma moeda com um padrão fixo de caras e coroas conhecido apenas pelo proprietário da moeda. Se a moeda de Victor se comportasse dessa maneira, então novamente seria possível que Victor e Peggy tivessem forjado o experimento, portanto, usar um gerador de números pseudoaleatórios não revelaria o conhecimento de Peggy ao mundo da mesma forma que usar uma moeda lançada.
Peggy poderia provar a Victor que conhece a palavra mágica, sem revelá-la a ele, em uma única tentativa. Se Victor e Peggy forem juntos à entrada da caverna, Victor pode observar Peggy entrar por A e sair por B. Isso provaria com certeza que Peggy conhece a palavra mágica, sem revelá-la a Victor. No entanto, tal prova poderia ser observada por um terceiro ou gravada por Victor, e tal prova seria convincente para qualquer pessoa. Em outras palavras, Peggy não poderia refutar tal prova alegando que coludiu com Victor e, portanto, ela não teria mais controle sobre quem está ciente de seu conhecimento.
Duas bolas e o amigo daltônico
Imagine que Victor seja daltônico para vermelho e verde (enquanto Peggy não é) e Peggy tenha duas bolas: uma vermelha e uma verde, mas idênticas em todos os outros aspectos. Para Victor, as bolas parecem completamente idênticas. Victor está cético de que as bolas sejam realmente distinguíveis. Peggy quer provar a Victor que as bolas são de cores diferentes, mas nada mais. Em particular, Peggy não quer revelar qual bola é a vermelha e qual é a verde.
Aqui está o sistema de prova: Peggy entrega as duas bolas para Victor e ele as coloca atrás das costas. Em seguida, ele pega uma das bolas, traz para a frente e a exibe. Depois, ele a coloca atrás das costas novamente e escolhe revelar apenas uma das duas bolas, escolhendo uma das duas ao acaso com probabilidade igual. Ele perguntará a Peggy: "Eu troquei a bola?". Todo esse procedimento é repetido quantas vezes for necessário.
Ao olhar para as cores das bolas, Peggy pode, é claro, dizer com certeza se ele as trocou ou não. Por outro lado, se as bolas fossem da mesma cor e, portanto, indistinguíveis, a capacidade de Peggy de determinar se ocorreu uma troca não seria melhor do que um palpite aleatório. Como a probabilidade de Peggy ter tido sucesso aleatório em identificar cada troca/não troca é de 50%, a probabilidade de ter tido sucesso aleatório em todas as trocas/não trocas aproxima-se de zero.
Ao longo de várias tentativas, a taxa de sucesso convergiria estatisticamente para 50%, e Peggy não conseguiria obter um desempenho significativamente melhor do que o acaso. Se Peggy e Victor repetirem esta "prova" várias vezes (por exemplo, 20 vezes), Victor deverá ficar convencido de que as bolas são de fato cores diferentes.
A prova acima é de conhecimento zero porque Victor nunca aprende qual bola é verde e qual é vermelha; de fato, ele não obtém conhecimento sobre como distinguir as bolas.
Definição
Uma prova de conhecimento zero de alguma afirmação deve satisfazer três propriedades:
Completude (Completeness): se a afirmação for verdadeira, um verificador honesto (ou seja, aquele que segue o protocolo corretamente) será convencido desse fato por um provador honesto. Solidez (Soundness): se a afirmação for falsa, nenhum provador trapaceiro pode convencer um verificador honesto de que ela é verdadeira, exceto com uma pequena probabilidade. Conhecimento zero (Zero-knowledge): se a afirmação for verdadeira, nenhum verificador aprende nada além do fato de que a afirmação é verdadeira. Em outras palavras, apenas conhecer a afirmação (e não o segredo) é suficiente para imaginar um cenário que mostre que o provador conhece o segredo. Isso é formalizado mostrando que cada verificador possui algum simulador que, recebendo apenas a afirmação a ser provada (e sem acesso ao provador), pode produzir uma transcrição que "pareça" uma interação entre um provador honesto e o verificador em questão.
As duas primeiras propriedades são de sistemas de provas interativas mais gerais. A terceira é o que torna a prova de conhecimento zero.