Em criptografia, uma prova de conhecimento zero ou protocolo de conhecimento zero é um método pelo qual uma parte (o provador) pode provar à outra parte (o verificador) que uma determinada afirmação é verdadeira, sem transmitir qualquer informação além do fato de que a afirmação é realmente verdadeira. A essência das provas de conhecimento zero é que é trivial provar que alguém possui conhecimento de certas informações simplesmente revelando-as. O desafio é provar tal posse sem revelar a própria informação ou qualquer informação adicional.^[1]

Se a prova de uma afirmação requer que o provador possua algumas informações secretas, então o verificador não será capaz de provar a afirmação a ninguém sem possuir as informações secretas. A declaração sendo provada deve incluir a afirmação de que o provador possui tal conhecimento, mas sem incluir nem transmitir o próprio conhecimento na afirmação. Caso contrário, a declaração não seria provada em conhecimento zero porque fornece ao verificador informações adicionais sobre a declaração ao final do protocolo. Uma prova de conhecimento de conhecimento zero é um caso especial quando a afirmação consiste apenas no fato de que o provador possui a informação secreta.

Provas interativas de conhecimento zero requerem interação entre o indivíduo (ou sistema de computador) que prova seu conhecimento e o indivíduo que está validando a prova.^[1]

Um protocolo que implementa provas de conhecimento de conhecimento zero deve necessariamente exigir uma entrada interativa do verificador. Esta entrada interativa é geralmente na forma de um ou mais desafios, de modo que as respostas do provador convencerão o verificador se e somente se a afirmação for verdadeira, ou seja, se o provador possuir o conhecimento alegado. Se esse não for o caso, o verificador pode registrar a execução do protocolo e reproduzi-la para convencer outra pessoa de que possui as informações secretas. A aceitação da nova parte é justificada pelo fato de o reprodutor possuir as informações (o que implica que o protocolo vazou informações e, portanto, não foi provado em conhecimento zero) ou a aceitação é espúria, ou seja, foi aceita por alguém que na verdade não possue as informações.

Existem algumas formas de provas de conhecimento zero não interativas,^[2][3] mas a validade da prova depende de suposições computacionais (normalmente as suposições de uma função de dispersão criptográfica ideal).

Peggy escolhe aleatoriamente o caminho A ou B, enquanto Victor espera do lado de fora

Victor escolhe um caminho de saída

Peggy aparece de forma confiável na saída escolhida por Victor

Há uma história bem conhecida, publicada pela primeira vez por Jean-Jacques Quisquater e outros em seu artigo "Como explicar protocolos de conhecimento zero para seus filhos", que apresenta as idéias fundamentais das provas de conhecimento zero.^[4] É prática comum rotular as duas partes em uma prova de conhecimento zero como Peggy (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 a forma 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 ou revelar o fato de seu conhecimento para o mundo em geral.

Eles rotulam os caminhos direito e esquerdo da entrada A e B. Primeiro, Victor espera do lado de fora da caverna enquanto Peggy entra. Peggy pega o caminho A ou B e Victor não tem permissão para ver qual caminho ela segue. Então, Victor se aproxima da entrada da caverna e grita o nome do caminho pelo qual ele quer que ela retorne (A ou B, escolhidos ao acaso). É fácil, se ela realmente conhece a palavra mágica: ela abre a porta, se necessário, e retorna pelo caminho desejado.

No entanto, suponha que ela não conhecesse a palavra. Então, ela só poderia retornar pelo caminho nomeado se Victor desse o nome do mesmo caminho pelo qual ela havia entrado. Visto que Victor escolheria A ou B aleatoriamente, ela teria 50% de chance de acertar. Se eles repetissem esse truque muitas vezes (digamos, 20 vezes seguidas), a chance de antecipar com sucesso todos os pedidos de Victor se tornaria extremamente pequena (cerca de uma em um milhão).

Assim, se Peggy aparecer repetidamente na saída solicitada por Victor, ele pode concluir que é extremamente provável que Peggy conheça, de fato, a palavra secreta.

Uma observação lateral a respeito de observadores terceirizados: mesmo que Victor esteja usando uma câmera oculta que registra toda a transação, a única coisa que a câmera gravará é 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 falsificar (exigindo apenas que Peggy e Victor concordassem de antemão sobre a sequência de A e B que Victor gritaria). Essa gravação certamente nunca será convincente para ninguém, exceto os participantes originais. Na verdade, mesmo uma pessoa que estava presente como observador no experimento original não ficaria convencida, já que Victor e Peggy podem ter orquestrado todo o "experimento" do início ao fim.

Além disso, observe que se Victor escolher seus As e Bs jogando uma moeda na frente da câmera, este protocolo perderá sua propriedade de conhecimento zero mas o cara ou coroa na câmera provavelmente seria convincente para qualquer pessoa que assistir à gravação mais tarde. Assim, embora isso não revele a palavra secreta para Victor, torna possível para Victor convencer o mundo em geral de que Peggy tem esse conhecimento (contrariando os desejos declarados de Peggy). No entanto, a criptografia digital geralmente "vira moedas" ao contar com um gerador de números pseudo-aleatórios, que é semelhante a uma moeda com um padrão fixo de cara e coroa conhecido apenas pelo dono da moeda. Se a moeda de Victor se comportasse dessa maneira, seria possível que Victor e Peggy falsificassem o "experimento", portanto, usar um gerador de números pseudoaleatórios não revelaria o conhecimento de Peggy para o mundo da mesma forma que usar uma moeda lançada seria.

Observe que Peggy pode provar a Victor que conhece a palavra mágica, sem revelá-la a ele, em uma única tentativa. Se Victor e Peggy forem juntos para a entrada da caverna, Victor pode assistir Peggy entrar por A e sair por B. Isso provaria com certeza que Peggy conhece a palavra mágica, sem revelar a palavra mágica a Victor. No entanto, tal prova poderia ser observada por um terceiro ou registrada por Victor e, tal prova, seria convincente para qualquer pessoa. Em outras palavras, Peggy não poderia refutar tal prova alegando que ela conspirou com Victor e, portanto, ela não está mais no controle de quem está ciente de seu conhecimento.

Imagine que você tem um amigo daltônico (enquanto você não é) ​e, por causa disso, ele tem dificuldade em distinguir a cor verde da cor vermelha e você tem duas bolas idênticas mas uma é vermelha e a outra é verde. Para seu amigo, elas parecem completamente idênticas e ele é cético quando você diz que elas realmente são distinguíveis. Você quer provar para ele que elas são de fato de cores diferentes e nada mais. Em particular, você não quer revelar qual é a vermelha e qual é a verde.

Aqui está o sistema de prova. Você dá as duas bolas para o seu amigo e ele as coloca nas costas. Em seguida, ele pega uma das bolas, mostra pra você, coloca atrás das costas novamente e depois escolhe revelar apenas uma das duas bolas. Ele vai te perguntar: "Eu troquei a bola?" e todo este procedimento é repetido quantas vezes for necessário.

Ao olhar para suas cores, você pode dizer com certeza se ele as trocou ou não. Por outro lado, se fossem da mesma cor (indistinguíveis), não haveria como adivinhar corretamente com probabilidade superior à 50%.

Como a probabilidade de que você conseguiria aleatoriamente identificar cada alternância (ou não-alternância) é de 50%, a probabilidade você de ter conseguido aleatoriamente identificar todas as alternâncias (ou não-alternâncias) se aproxima de zero ("solidez"). Se vocês repetem essa "prova" várias vezes (100 vezes, por exemplo), seu amigo deve ficar convencido ("completude") de que as bolas são coloridas e, de fato, não são indistinguíveis.

A prova acima é de conhecimento zero porque seu amigo não discerne (ou aprende) qual bola é a verde e qual bola é a vermelha. De fato, ele não ganha conhecimento sobre como distinguir as bolas.^[5]

Onde está Wally? (intitulado onde está Waldo? Na América do Norte) é um livro de imagens onde o leitor é desafiado a encontrar um pequeno personagem chamado Wally escondido em algum lugar em uma página de dupla propagação que é preenchida com muitos outros personagens. As imagens são projetadas para que seja difícil encontrar Wally.

Imagine que você seja um profissional em solucionar "Onde está Wally?". Uma empresa chega a você com um livro "Onde está Wally?" que eles precisam solucionar. A empresa quer que você prove ser, realmente, um profissional em "Onde está Wally?" e, portanto, pede que você encontre Wally em uma imagem do livro mas você não quer trabalhar para eles sem ser pago.

Você e a empresa (ambos) querem cooperar, mas vocês não confiam um no outro. Não parece ser possível satisfazer a demanda da empresa sem fazer alguns trabalhos gratuitos para ela, mas na verdade, há uma prova de conhecimento zero que permite que você prove para a empresa que você sabe onde está Wally na imagem (sem revelar como você o encontrou, ou onde ele está).

A prova vai da seguinte forma: você pede ao representante da empresa que se vire e, então, você coloca um pedaço muito grande de papelão sobre a imagem, de modo que no centro do papelão esteja posicionado Wally. Você cortou uma pequena "janela" no centro do papelão de tal forma que Wally é visível. Agora você pode pedir ao representante da empresa que novamente se vire, veja o grande pedaço de papelão com o buraco no meio e observe que Wally é visível através do orifício. O papelão é grande o suficiente para que ele não possa determinar a posição do livro, sob o papelão, em que Wally está. Você então pede que o representante vire-se novamente para que você possa remover o papelão e devolver o livro.

Como descrito, esta prova (não completamente rigorosa) é apenas uma ilustração. O representante da empresa precisaria ter certeza de que você não trapeceou (com uma imagem de Wally já conhecida por você escondida no quarto) enquanto ele não observava. Algo como uma caixa de luva à prova de adulteração pode ser usada em uma prova mais rigorosa. A prova acima também resulta no "vazamento" da posição do corpo de Wallypara o representante da empresa, que pode ajudá-la a encontrar Wally se sua posição corporal muda em cada quebra-cabeça "Onde está Wally?".

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. Solidez: 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 insignificantes.

Uma definição formal de conhecimento zero tem que usar algum modelo computacional, sendo o mais comum que o de uma máquina de Turing. Sendo ${\displaystyle P}$, ${\displaystyle V}$, e ${\displaystyle S}$ máquinas de Turing, um sistema de prova interativa com ${\displaystyle (P,V)}$ para uma linguagem ${\displaystyle L}$ é de conhecimento zero se para qualquer tempo polinomial probabilístico (PPT) verificador ${\displaystyle {\hat {V}}}$ existe um simulador PPT ${\displaystyle S}$ tal que

${\displaystyle \forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z)}$

onde ${\displaystyle \operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]}$ é um registro das interações entre ${\displaystyle P(x)}$ e ${\displaystyle {\hat {V}}(x,z)}$. O provador ${\displaystyle P}$ é modelado como tendo poder de computação ilimitado (na prática, ${\displaystyle P}$ normalmente é uma máquina de Turing probabilística). Intuitivamente, a definição afirma que um sistema de prova interativo ${\displaystyle (P,V)}$ é de conhecimento zero se para qualquer verificador ${\displaystyle {\hat {V}}}$ existe um simulador eficiente ${\displaystyle S}$ (dependendo de ${\displaystyle {\hat {V}}}$) que pode reproduzir a conversa entre ${\displaystyle P}$ e ${\displaystyle {\hat {V}}}$ em qualquer entrada. A string auxiliar ${\displaystyle z}$ na definição desempenha o papel do "conhecimento prévio" (incluindo os aleatórios inventados de ${\displaystyle {\hat {V}}}$). A definição implica que ${\displaystyle {\hat {V}}}$ não pode usar qualquer string de conhecimento prévio ${\displaystyle z}$ para minerar informações fora de sua conversa com ${\displaystyle P}$, porque se a ${\displaystyle S}$ também é dado este conhecimento prévio, ele pode reproduzir a conversa entre ${\displaystyle {\hat {V}}}$ e ${\displaystyle P}$ exatamente como antes.

A definição dada é a de perfeito conhecimento zero. O conhecimento zero computacional é obtido exigindo que as exibições do verificador ${\displaystyle {\hat {V}}}$ e o simulador são apenas computacionalmente indistinguíveis, dada a string auxiliar.

Podemos aplicar essas idéias a uma aplicação de criptografia mais realista. Peggy quer provar a Victor que conhece o logaritmo discreto de um determinado valor em um determinado grupo.^[6]

Por exemplo, dado um valor ${\displaystyle y}$, um grande primo ${\displaystyle p}$ e um gerador ${\displaystyle g}$, ela quer provar que conhece um valor ${\displaystyle x}$ tal que ${\displaystyle g^{x}{\bmod {p}}=y}$, sem revelar ${\displaystyle x}$. De fato, o conhecimento de ${\displaystyle x}$ poderia ser usado como prova de identidade, pois Peggy poderia ter tal conhecimento porque escolheu um valor aleatório ${\displaystyle x}$ que ela não revelou a ninguém, calculado ${\displaystyle y=g^{x}{\bmod {p}}}$ e distribuiu o valor de ${\displaystyle y}$ para todos os verificadores potenciais, de forma que, mais tarde, provar conhecimento de ${\displaystyle x}$ é equivalente a provar sua identidade como Peggy.

O protocolo procede da seguinte forma: em cada rodada, Peggy gera um número aleatório ${\displaystyle r}$, calcula ${\displaystyle C=g^{r}{\bmod {p}}}$ e divulga isso para Victor. Depois de receber ${\displaystyle C}$, Victor aleatoriamente emite uma das seguintes duas solicitações: ele solicita que Peggy divulgue o valor de ${\displaystyle r}$ ou o valor de ${\displaystyle (x+r){\bmod {(p-1)}}}$. Com qualquer uma das respostas, Peggy está divulgando apenas um valor aleatório, de modo que nenhuma informação é divulgada pela execução correta de uma rodada do protocolo.

Victor pode verificar qualquer uma das respostas. Se ele solicitou ${\displaystyle r}$, ele pode então calcular ${\displaystyle g^{r}{\bmod {p}}}$ e verificar se corresponde a ${\displaystyle C}$. Se ele solicitou ${\displaystyle (x+r){\bmod {(p-1)}}}$, ele pode verificar que ${\displaystyle C}$ é consistente com isso, calculando ${\displaystyle g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}$ e verificando se ele corresponde a ${\displaystyle C\cdot y{\bmod {p}}}$. Se Peggy realmente conhece o valor de ${\displaystyle x}$, ela pode responder a qualquer um dos possíveis desafios de Victor.

Se Peggy soubesse ou pudesse adivinhar qual desafio Victor vai lançar, então ela poderia facilmente trapacear e convencer Victor de que ela conhece ${\displaystyle x}$ quando ela não conhece. Se ela sabe que Victor vai solicitar ${\displaystyle r}$, então ela procede normalmente: ela escolhe ${\displaystyle r}$, calcula ${\displaystyle C=g^{r}{\bmod {p}}}$, divulga ${\displaystyle C}$ para Victor e será capaz de responder ao desafio. Por outro lado, se ela souber que Victor solicitará ${\displaystyle (x+r){\bmod {(p-1)}}}$, então ela escolhe um valor aleatório ${\displaystyle r'}$, calcula ${\displaystyle C'=g^{r'}\cdot \left(g^{x}\right)^{-1}{\bmod {p}}}$, e divulga ${\displaystyle C'}$ para Victor como o valor de ${\displaystyle C}$ que ele está esperando. Quando Victor a desafia a revelar ${\displaystyle (x+r){\bmod {(p-1)}}}$, ela revela ${\displaystyle r'}$, para o qual Victor verificará a consistência, pois ele por sua vez calculará ${\displaystyle g^{r'}{\bmod {p}}}$, que corresponde a ${\displaystyle C'\cdot y}$, desde que Peggy tenha multiplicado pelo inverso multiplicativo modular de ${\displaystyle y}$.

No entanto, se em qualquer um dos cenários acima, Victor emite um desafio diferente daquele que ela esperava e para o qual ela fabricou o resultado, então ela será incapaz de responder ao desafio sob a suposição de inviabilidade de resolver o logaritmo discreto para esse grupo. Se ela escolheu ${\displaystyle r}$ e divulgou ${\displaystyle C=g^{r}{\bmod {p}}}$, será incapaz de produzir um ${\displaystyle (x+r){\bmod {(p-1)}}}$ válido que passaria pela verificação de Victor, visto que não conhece ${\displaystyle x}$. E se escolheu um valor ${\displaystyle r'}$ que se apresenta como ${\displaystyle (x+r){\bmod {(p-1)}}}$, então teria que responder com o logaritmo discreto do valor que ela divulgou. Mas Peggy não conhece esse logaritmo discreto, já que o valor C que ela divulgou foi obtido por meio de aritmética com valores conhecidos e não calculando uma potência com um expoente conhecido.

Assim, um provador de trapaça tem 0,5 probabilidade de trapacear com sucesso em uma rodada. Ao executar um número grande o suficiente de rodadas, a probabilidade de sucesso de um provador de trapaça pode ser arbitrariamente baixa.

Peggy prova saber o valor de x (por exemplo, sua senha).

1. Peggy e Victor concordam em um primo ${\displaystyle p}$ e um gerador ${\displaystyle g}$ do grupo multiplicativo do campo ${\displaystyle \mathbb {Z} _{p}}$.
2. Peggy calcula o valor ${\displaystyle y=g^{x}{\bmod {p}}}$ e transfere o valor para Victor.
3. As duas etapas a seguir são repetidas um (grande) número de vezes.
   1. Peggy escolhe repetidamente um valor aleatório ${\displaystyle r\in U[0,p-1]}$, calcula ${\displaystyle C=g^{r}{\bmod {p}}}$ e transfere o valor ${\displaystyle C}$ para Victor.
   2. Victor pede a Peggy que calcule e transfira o valor ${\displaystyle (x+r){\bmod {(p-1)}}}$ ou o valor ${\displaystyle r}$. No primeiro caso, ele verifica ${\displaystyle (C\cdot y){\bmod {p}}\equiv g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}$. Já no segundo caso, ele verifica ${\displaystyle C\equiv g^{r}{\bmod {p}}}$.

O valor ${\displaystyle (x+r){\bmod {(}}p-1)}$ pode ser visto como o valor criptografado de ${\displaystyle x{\bmod {(}}p-1)}$. Se ${\displaystyle r}$ é verdadeiramente aleatório, igualmente distribuído entre zero e ${\displaystyle (p-1)}$, isso não vaza nenhuma informação sobre ${\displaystyle x}$ (verifique o artigo cifra de uso único ou chave de uso único (OTP)).

O esquema a seguir é devido a Manuel Blum.^[7]

Neste cenário, Peggy conhece um ciclo hamiltoniano para um grande grafo G. Victor conhece G, mas não o ciclo (por exemplo, Peggy gerou G e o revelou a ele). Encontrar um ciclo hamiltoniano dado um grande gráfico é considerado computacionalmente inviável. , uma vez que sua versão de decisão correspondente é conhecida como NP-completa. Peggy, simplesmente, provará que conhece o ciclo sem revelá-lo (talvez Victor esteja interessado em comprá-lo mas queira a verificação primeiro ou talvez Peggy seja a única que conhece essa informação e está provando sua identidade para Victor).

Para mostrar que Peggy conhece esse ciclo hamiltoniano, ela e Victor jogam várias rodadas.

• No início de cada rodada, Peggy cria H, um gráfico que é isomorfo a G (ou seja, H é igual a G, exceto que todos os vértices têm nomes diferentes). Como é trivial traduzir um ciclo hamiltoniano entre gráficos isomórficos com isomorfismo conhecido, se Peggy conhece um ciclo hamiltoniano para G, ela também deve conhecer um para H.
• Peggy se compromete com H. Ela poderia fazer isso usando um esquema de confirmação criptográfica. Alternativamente, ela poderia numerar os vértices de H, para cada aresta de H escrever em um pequeno pedaço de papel os dois vértices da aresta e então colocar esses pedaços de papel voltados para baixo em uma mesa. O objetivo deste compromisso é que Peggy não seja capaz de mudar H enquanto, ao mesmo tempo, Victor não tenha informações sobre H.
• Victor então escolhe aleatoriamente uma de duas solicitações para fazer à Peggy: ele pode pedir que ela mostre o isomorfismo entre H e G (veja problema de isomorfismo de grafos) ou um ciclo hamiltoniano em H.
• Se Peggy for solicitada a mostrar que os dois gráficos são isomórficos, ela primeiro descobre todo H (por exemplo, virando todos os pedaços de papel que colocou na mesa) e, em seguida, fornece as traduções dos vértices que mapeiam G para H. Victor pode, então, verificar que eles são realmente isomórficos.
• Se Peggy for solicitada a provar que conhece um ciclo hamiltoniano em H, ela traduzirá seu ciclo hamiltoniano em G em H e apenas descobrirá as arestas do ciclo hamiltoniano. Isso é o suficiente para Victor verificar se H realmente contém um ciclo hamiltoniano.

É importante que o comprometimento com o grafo seja tal que Victor possa verificar, no segundo caso, que o ciclo é realmente feito de arestas de H. Isso pode ser feito, por exemplo, comprometendo-se com cada aresta (ou falta dela) separadamente.

Se Peggy conhece um ciclo hamiltoniano em G, ela pode facilmente satisfazer a demanda de Victor para o isomorfismo de grafo que produz H a partir de G (com o qual ela se comprometeu na primeira etapa) ou um ciclo hamiltoniano em H (que ela pode construir aplicando o isomorfismo ao ciclo em G).

As respostas de Peggy não revelam o ciclo hamiltoniano original em G. A cada rodada, Victor aprenderá apenas o isomorfismo de H para G ou um ciclo hamiltoniano em H. Ele precisaria de ambas as respostas para um único H para descobrir o ciclo em G, então a informação permanece desconhecida, desde que Peggy possa gerar um H distinto a cada rodada. Se Peggy não souber de um ciclo hamiltoniano em G, mas de alguma forma souber de antemão o que Victor pediria para ver em cada rodada, ela poderia trapacear. Por exemplo, se Peggy soubesse com antecedência que Victor pediria para ver o ciclo hamiltoniano em H, ela poderia gerar um ciclo hamiltoniano para um grafo não relacionado. Da mesma forma, se Peggy soubesse de antemão que Victor pediria para ver o isomorfismo, ela poderia simplesmente gerar um grafo isomórfico H (no qual ela também não conhece um ciclo hamiltoniano). Victor poderia simular o protocolo sozinho (sem Peggy) porque ele sabe o que vai pedir para ver. Portanto, Victor não obtém nenhuma informação sobre o ciclo hamiltoniano em G a partir das informações reveladas em cada rodada.

Se Peggy não souber a informação, ela pode adivinhar qual pergunta Victor fará e gerar um grafo isomorfo para G ou um ciclo hamiltoniano para um grafo não relacionado, mas como ela não conhece um ciclo hamiltoniano para G, ela não pode fazer as duas coisas. Com essa suposição, sua chance de enganar Victor é 2⁻ⁿ, onde n é o número de rodadas. Para todos os propósitos realistas, é inviávelmente difícil derrotar uma prova de conhecimento zero com um número razoável de rodadas dessa maneira.

Diferentes variantes de conhecimento zero podem ser definidas formalizando o conceito intuitivo do que significa a saída do simulador "parecida com" a execução do protocolo de prova real das seguintes maneiras:

• Falamos de conhecimento zero perfeito se as distribuições produzidas pelo simulador e o protocolo de prova forem distribuídas exatamente da mesma forma. Este é, por exemplo, o caso do primeiro exemplo acima.
• O conhecimento estatístico zero^[8] significa que as distribuições não são necessariamente exatamente as mesmas, mas são estatisticamente próximas, o que significa que sua diferença estatística é uma função desprezível.
• Falamos de conhecimento zero computacional se nenhum algoritmo eficiente puder distinguir as duas distribuições.

• Prova de conhecimento: o conhecimento está oculto no expoente como no exemplo mostrado acima.
• Criptografia baseada em emparelhamento: dados f(x) e f(y), sem saber x e y, é possível calcular f(x×y).
• Prova indistinguível de testemunha: os verificadores não podem saber qual testemunha é usada para produzir a prova.
• Computação multipartidária: embora cada parte possa manter seu respectivo segredo, elas juntas produzem um resultado.
• Assinatura em anel: os estranhos não têm ideia de qual chave é usada para assinar.

A pesquisa em provas de conhecimento zero foi motivada por sistemas de autenticação em que uma parte deseja provar sua identidade a uma outra parte por meio de algumas informações secretas (como uma senha), mas não quer que a segunda parte saiba nada sobre esse segredo. Isso é chamado de "prova de conhecimento de conhecimento zero". No entanto, uma senha é normalmente muito pequena ou insuficientemente aleatória para ser usada em muitos esquemas para provas de conhecimento de conhecimento zero. Uma prova de senha de conhecimento zero é um tipo especial de prova de conhecimento de conhecimento zero que aborda o tamanho limitado das senhas. ^{[carece de fontes?]}

Em abril de 2015, o protocolo Sigma (uma de muitas provas) foi introduzido.^[9] Em agosto de 2021, a Cloudflare, uma empresa americana de segurança e infraestrutura da web, decidiu usar o mecanismo de uma de muitas provas para verificação da web privada usando hardware do fornecedor.^[10]

Um dos usos das provas de conhecimento zero nos protocolos criptográficos é impor um comportamento honesto enquanto mantém a privacidade. Grosso modo, a ideia é forçar um usuário a provar, usando uma prova de conhecimento zero, que seu comportamento está correto de acordo com o protocolo.^[11][12] Por causa da integridade, sabemos que o usuário deve realmente agir com honestidade para poder fornecer uma prova válida. Por não ter conhecimento, sabemos que o usuário não compromete a privacidade de seus segredos no processo de fornecimento da prova.^{[carece de fontes?]}

Em 2016, o laboratório de física de plasma e a universidade de Princeton demonstraram uma técnica que pode ter aplicabilidade em futuras palestras de desarmamento nuclear. Isso permitiria aos inspetores confirmar se um objeto é ou não uma arma nuclear sem registrar, compartilhar ou revelar o funcionamento interno que pode ser secreto.^[13]

As provas de conhecimento zero foram aplicadas nos protocolos Zerocoin e Zerocash que culminaram no nascimento do Zcoin^[14] (rebatizado como Firo em 2020)^[15] e das criptomoedas Zcash em 2016. O Zerocoin tem um modelo de mistura embutido que não confia quaisquer pares ou provedores de mistura centralizados para garantir o anonimato.^[14] Os usuários podem fazer transações em uma moeda base e podem circular a moeda dentro e fora da moeda Zerocoins.^[16] O protocolo Zerocash usa um modelo semelhante (uma variante conhecida como prova não interativa de conhecimento zero),^[17] exceto que pode obscurecer o valor da transação, enquanto o Zerocoin não pode. Dadas as restrições significativas de dados de transação na rede Zerocash, Zerocash é menos sujeito a ataques de sincronização de privacidade quando comparado ao Zerocoin. No entanto, essa camada adicional de privacidade pode causar hiperinflação potencialmente não detectada do fornecimento de Zerocash porque moedas fraudulentas não podem ser rastreadas.^[14][18]

Em 2018, os bulletproofs foram introduzidos. Os bulletproofs são uma melhoria da prova não interativa de conhecimento zero, onde a configuração confiável não é necessária.^[19] Posteriormente, foram implementados no protocolo Mimblewimble (em que as criptomoedas Grin e Beam são baseadas) e na criptomoeda Monero.^[20] Em 2019, o Firo implementou o protocolo Sigma, que é uma melhoria no protocolo Zerocoin sem configuração confiável.^[21][9] No mesmo ano, o Firo introduziu o protocolo Lelantus, uma melhoria no protocolo Sigma onde o antigo oculta a origem e o valor de uma transação.^[22]

As provas de conhecimento zero foram concebidas pela primeira vez em 1985 por Shafi Goldwasser, Silvio Micali e Charles Rackoff em seu artigo "A complexidade de conhecimento dos sistemas de prova interativos".^[11] Este artigo introduziu a hierarquia IP de sistemas de prova interativa (verifique o artigo sistema de prova interativa) e concebeu o conceito de complexidade do conhecimento, uma medida da quantidade de conhecimento sobre a prova transferida do provador para o verificador. Eles também forneceram a primeira prova de conhecimento zero para um problema concreto, o de decidir o ${\displaystyle {\bmod {m}}}$ de não-resíduos quadráticos. Junto com um artigo de László Babai e Shlomo Moran, este artigo marcante inventou sistemas de prova interativa, para os quais todos os cinco autores ganharam o primeiro Prêmio Gödel em 1993.

Em suas próprias palavras, Goldwasser, Micali e Rackoff dizem:

De particular interesse é o caso em que este conhecimento adicional é essencialmente ${\displaystyle 0}$ e mostramos que é possível provar interativamente que um número é quadrático não residual ${\displaystyle {\bmod {m}}}$ liberando ${\displaystyle 0}$ conhecimento adicional. Isso é surpreendente, pois nenhum algoritmo eficiente para decidir o ${\displaystyle {\bmod {m}}}$ de residuosidade quadrática é conhecido quando a fatoração de ${\displaystyle m}$ não é fornecida. Além disso, todas as provas NP conhecidas para este problema exibem a fatoração primária de ${\displaystyle m}$. Isso indica que adicionar interação ao processo de prova pode diminuir a quantidade de conhecimento que deve ser comunicada a fim de provar um teorema.

O problema quadrático não residual tem um algoritmo NP e um co-NP e, portanto, encontra-se na interseção de NP e co-NP. Isso também era verdade para vários outros problemas para os quais as provas de conhecimento zero foram descobertas posteriormente, como um sistema de prova não publicado por Oded Goldreich verificando que um módulo de dois primos não é um inteiro de Blum.^[23]

Oded Goldreich, Silvio Micali e Avi Wigderson deram um passo adiante, mostrando que, assumindo a existência de criptografia inquebrável, pode-se criar um sistema de prova de conhecimento zero para o problema de coloração de grafos com três cores NP-completo. Uma vez que todos os problemas em NP podem ser eficientemente reduzidos a este problema, isso significa que, sob essa suposição, todos os problemas em NP têm provas de conhecimento zero.^[24] A razão para a suposição é que, como no exemplo acima, seus protocolos requerem criptografia. Uma condição suficiente comumente citada para a existência de criptografia inquebrável é a existência de funções unilaterais, mas é concebível que alguns meios físicos também possam alcançá-la.

Além disso, eles também mostraram que o problema de não isomorfismo de grafos, o complemento do problema de isomorfismo de grafos, tem uma prova de conhecimento zero. Este problema está no co-NP, mas atualmente não se sabe se ele está no NP ou em qualquer classe prática. De forma geral, Russell Impagliazzo e Moti Yung, bem como Ben-Or et al. continuariam a mostrar que, também assumindo funções unilaterais ou criptografia inquebrável, existem provas de conhecimento zero para todos os problemas em IP = PSPACE, ou em outras palavras, tudo que pode ser provado por um sistema de prova interativo pode ser provado com conhecimento zero.^[25][26]

Não gostando de fazer suposições desnecessárias, muitos teóricos buscaram uma maneira de eliminar a necessidade de funções unilaterais. Uma maneira de fazer isso foi com sistemas de prova interativa multi-provador (veja sistema de prova interativa), que tem provadores independentes múltiplos ao invés de apenas um, permitindo ao verificador "interrogar" os provadores isoladamente para evitar ser enganado. Pode ser mostrado que, sem quaisquer suposições de intratabilidade, todas as linguagens em NP têm provas de conhecimento zero em tal sistema.^[27]

Acontece que em um ambiente semelhante ao da Internet, onde vários protocolos podem ser executados simultaneamente, construir provas de conhecimento zero é mais desafiador. A linha de pesquisa investigando provas de conhecimento zero concorrentes foi iniciada pelo trabalho de Dwork, Naor e Sahai.^[28] Um desenvolvimento particular ao longo dessas linhas foi o desenvolvimento de protocolos à prova de testemunhas indistinguíveis. A propriedade de indistinguibilidade de testemunha está relacionada àquela de conhecimento zero, embora os protocolos de testemunha indistinguível não sofram dos mesmos problemas de execução simultânea.^[29]

Outra variante das provas de conhecimento zero são as provas não interativas de conhecimento zero. Blum, Feldman e Micali mostraram que uma string aleatória comum compartilhada entre o provador e o verificador é suficiente para atingir o conhecimento computacional zero sem a necessidade de interação.^[2][3]

Os protocolos de prova de conhecimento zero interativos ou não interativos mais populares podem ser amplamente categorizados nas seguintes quatro categorias: argumentos de conhecimento não interativos sucintos (SNARK), argumento de conhecimento transparente escalonável (STARK), delegação polinomial verificável (VPD), e argumentos não interativos sucintos (SNARG). Uma lista de protocolos e bibliotecas de prova de conhecimento zero é fornecida abaixo, juntamente com comparações baseadas em transparência, universalidade, resiliência pós-quântica e paradigma de programação.^[30] Transparente é um protocolo que não requer nenhuma configuração confiável e usa aleatoriedade pública. Universal é um protocolo que não é específico do programa e não requer uma nova configuração para cada circuito. Finalmente, resiliente pós-quântico é um protocolo que não é suscetível a ataques conhecidos por computadores quânticos de grande escala.

Sistemas de prova de conhecimento zero (ZKP)

Sistema ZKP	Protocolo	Transparente	Universal	Resiliente pós-quântico	Paradigma de programação
Pinocchio[31]	zk-SNARK	Não	Não	Não	Processual
Geppetto[32]	zk-SNARK	Não	Não	Não	Processual
TinyRAM[33]	zk-SNARK	Não	Não	Não	Processual
Buffet[34]	zk-SNARK	Não	Não	Não	Processual
ZoKrates[35]	zk-SNARK	Não	Não	Não	Processual
xJsnark[36]	zk-SNARK	Não	Não	Não	Processual
vRAM[37]	zk-SNARG	Não	Sim	Não	Montagem
vnTinyRAM[38]	zk-SNARK	Não	Sim	Não	Processual
MIRAGE[39]	zk-SNARK	Não	Sim	Não	Circuitos aritméticos
Sonic[40]	zk-SNARK	Não	Sim	Não	Circuitos aritméticos
Marlin[41]	zk-SNARK	Não	Sim	Não	Circuitos aritméticos
PLONK[42]	zk-SNARK	Não	Sim	Não	Circuitos aritméticos
SuperSonic[43]	zk-SNARK	Sim	Sim	Não	Circuitos aritméticos
Bulletproofs[44]	Bulletproofs	Sim	Sim	Não	Circuitos aritméticos
Hyrax[45]	zk-SNARK	Sim	Sim	Não	Circuitos aritméticos
Halo[46]	zk-SNARK	Sim	Sim	Não	Circuitos aritméticos
Virgo[47]	zk-SNARK	Sim	Sim	Sim	Circuitos aritméticos
Ligero[48]	zk-SNARK	Sim	Sim	Sim	Circuitos aritméticos
Aurora[49]	zk-SNARK	Sim	Sim	Sim	Circuitos aritméticos
zk-STARK[50]	zk-STARK	Sim	Sim	Sim	Montagem
Zilch[30][51]	zk-STARK	Sim	Sim	Sim	Orientado a objeto

• Paradoxo da informação de Arrow
• Protocolo de segurança
• Prova de conhecimento

Referências

• Criptografia infantil aplicada – Uma simples explicação de provas de conhecimento zero usando Where's Waldo? como exemplo (em inglês)
• Uma introdução a provas de conhecimento zero com aplicações na criptografia (em inglês)
• Como construir sistemas de prova de conhecimento zero para NP (em inglês)
• Um sistema de prova de conhecimento zero estatístico e não interativo eficiente para produtos principais quase seguros (em inglês)
• Tutorial de Oded Goldreich sobre provas de conhecimento zero (em inglês)
• Tese de Ph.D. de Vadhan sobre conhecimento zero estatístico (em inglês)
• Curso de teoria da computação, universidade de Cornell (2009), Provas de conhecimento zero (em inglês)