Prova de conhecimento zero: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 03h59min de 28 de junho de 2021

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 conhece um valor x sem transmitir qualquer informação além do fato de que eles conhecem o valor x. 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 não o conhecimento em si. 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).

Exemplo abstrato

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".^[4] É 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

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

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.
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.
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.

Exemplos práticos

Logaritmo discreto de um determinado valor

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.^[5]

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

O protocolo procede da seguinte forma: em cada rodada, Peggy gera um número aleatório $r$ , calcula $C=g^{r}{\bmod {p}}$ e divulga isso para Victor. Depois de receber $C$ , Victor aleatoriamente emite uma das seguintes duas solicitações: ele solicita que Peggy divulgue o valor de $r$ ou o valor de $(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 $r$ , ele pode então calcular $g^{r}{\bmod {p}}$ e verificar se corresponde a $C$ . Se ele solicitou $(x+r){\bmod {(p-1)}}$ , ele pode verificar que $C$ é consistente com isso, calculando $g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}$ e verificando se ele corresponde a $C\cdot y{\bmod {p}}$ . Se Peggy realmente conhece o valor de $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 $x$ quando ela não conhece. Se ela sabe que Victor vai solicitar $r$ , então ela procede normalmente: ela escolhe $r$ , calcula $C=g^{r}{\bmod {p}}$ , divulga $C$ para Victor e será capaz de responder ao desafio. Por outro lado, se ela souber que Victor solicitará $(x+r){\bmod {(p-1)}}$ , então ela escolhe um valor aleatório $r'$ , calcula $C'=g^{r'}\cdot \left(g^{x}\right)^{-1}{\bmod {p}}$ , e divulga $C'$ para Victor como o valor de $C$ que ele está esperando. Quando Victor a desafia a revelar $(x+r){\bmod {(p-1)}}$ , ela revela $r'$ , para o qual Victor verificará a consistência, pois ele por sua vez calculará $g^{r'}{\bmod {p}}$ , que corresponde a $C'\cdot y$ , desde que Peggy tenha multiplicado pelo inverso multiplicativo modular de $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 $r$ e divulgou $C=g^{r}{\bmod {p}}$ , será incapaz de produzir um $(x+r){\bmod {(p-1)}}$ válido que passaria pela verificação de Victor, visto que não conhece $x$ . E se escolheu um valor $r'$ que se apresenta como $(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.

Breve resumo

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

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

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

Ciclo hamiltoniano para um grande gráfico

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.^[6] 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 2⁻ⁿ, 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

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.

Conhecimento-zero estatístico significa que as distribuições não são exatamente as mesmas, mas são estatisticamente próximas, o que significa que a sua diferença estatística é uma função desprezível.

Falamos de conhecimento-nulo computacional, se nenhum algoritmo eficiente pode distinguir as duas distribuições.

Aplicações

Sistemas de autenticação

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?]}

Comportamento ético

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.^[7]^[8] 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?]}

Desarmamento nuclear

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.^[9]

Notas

↑ ^a ^b «What is a zero-knowledge proof and why is it useful?» [O que é uma prova de conhecimento zero e por que é útil?] (em inglês). 16 de novembro de 2017. Consultado em 27 de junho de 2021
↑ Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). Non-interactive zero-knowledge and its applications [Conhecimento zero não interativo e suas aplicações]. Procedimentos do vigésimo simpósio anual da ACM sobre teoria da computação (STOC 1988) (em inglês). [S.l.: s.n.] pp. 103 à 112. ISBN 978-0897912648. doi:10.1145/62212.62222. Consultado em 27 de junho de 2021 ^{[ligação inativa]}
↑ Wu, Huixin; Wang, Feng (2014). «A survey of noninteractive zero knowledge proof system and its applications» [Um levantamento do sistema de prova de conhecimento zero não interativo e suas aplicações]. O jornal científico mundial (em inglês). 2014: 560484. PMC 4032740. PMID 24883407. doi:10.1155/2014/560484 |acessodata= requer |url= (ajuda)
↑ 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)
↑ Chaum, David; Evertse, Jan-Hendrik; van de Graaf, Jeroen (1987). An improved protocol for demonstrating possession of discrete logarithms and some generalizations [Um protocolo melhorado para demonstrar a posse de logaritmos discretos e algumas generalizações]. Avanços em criptologia - EuroCrypt '87: procedimentos. Col: Lecture notes in computer science (em inglês). 304. [S.l.: s.n.] pp. 127 à 141. ISBN 978-3-540-19102-5. doi:10.1007/3-540-39118-5_13
↑ http://www.bennetyee.org/ucsd-pages/ZKP.html (em inglês)
↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), «The knowledge complexity of interactive proof systems» [A complexidade do conhecimento dos sistemas de prova interativa] (PDF), Jornal SIAM sobre computação, ISSN 1095-7111 (em inglês), 18 (1): 186 à 208, doi:10.1137/0218012, consultado em 27 de junho de 2021
↑ Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de outubro de 2020). «Is the classical GMW paradigm practical? The case of non-interactive actively secure 2PC» [O paradigma GMW clássico é prático? O caso do 2PC ativamente seguro não interativo]. Evento virtual, E.U.A.: Associação para máquinas de computação. Procedimentos da conferência ACM SIGSAC sobre segurança de computadores e comunicações 2020. CCS '20 (em inglês): 1591 à 1605. ISBN 978-1-4503-7089-9. doi:10.1145/3372297.3423366. Consultado em 27 de junho de 2021
↑ «PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab» [PPPL e Princeton demonstram nova técnica que pode ter aplicabilidade em futuras palestras de desarmamento nuclear - Laboratório de física de plasma de Princeton]. www.pppl.gov (em inglês). Consultado em 27 de junho de 2021

Ligações externas

Applied Kid Cryptography – 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 eficiente e não-interativo de prova de conhecimento-zero estatística para produtos primos quasi-seguros (em inglês)
Totorial por Oded Goldreich sobre provas de conhecimento-zero (em inglês)
Salil Vadhan, Tese de Ph.D. de Vadhan sobre conhecimento-zero estatístico (em inglês)
Theory of Computing Course, Cornell University 2009, Zero knowledge proofs (em inglês)

[:0-1] «What is a zero-knowledge proof and why is it useful?» [O que é uma prova de conhecimento zero e por que é útil?] (em inglês). 16 de novembro de 2017. Consultado em 27 de junho de 2021

[noninteractive-2] Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). Non-interactive zero-knowledge and its applications [Conhecimento zero não interativo e suas aplicações]. Procedimentos do vigésimo simpósio anual da ACM sobre teoria da computação (STOC 1988) (em inglês). [S.l.: s.n.] pp. 103 à 112. ISBN 978-0897912648. doi:10.1145/62212.62222. Consultado em 27 de junho de 2021 ^{[ligação inativa]}

[noninteractive2-3] Wu, Huixin; Wang, Feng (2014). «A survey of noninteractive zero knowledge proof system and its applications» [Um levantamento do sistema de prova de conhecimento zero não interativo e suas aplicações]. O jornal científico mundial (em inglês). 2014: 560484. PMC 4032740. PMID 24883407. doi:10.1155/2014/560484 |acessodata= requer |url= (ajuda)

[4] 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)

[5] Chaum, David; Evertse, Jan-Hendrik; van de Graaf, Jeroen (1987). An improved protocol for demonstrating possession of discrete logarithms and some generalizations [Um protocolo melhorado para demonstrar a posse de logaritmos discretos e algumas generalizações]. Avanços em criptologia - EuroCrypt '87: procedimentos. Col: Lecture notes in computer science (em inglês). 304. [S.l.: s.n.] pp. 127 à 141. ISBN 978-3-540-19102-5. doi:10.1007/3-540-39118-5_13

[6] ttp://www.bennetyee.org/ucsd-pages/ZKP.html (em inglês)

[knowledgecomplexity-7] Goldwasser, S.; Micali, S.; Rackoff, C. (1989), «The knowledge complexity of interactive proof systems» [A complexidade do conhecimento dos sistemas de prova interativa] (PDF), Jornal SIAM sobre computação, ISSN 1095-7111 (em inglês), 18 (1): 186 à 208, doi:10.1137/0218012, consultado em 27 de junho de 2021

[8] Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de outubro de 2020). «Is the classical GMW paradigm practical? The case of non-interactive actively secure 2PC» [O paradigma GMW clássico é prático? O caso do 2PC ativamente seguro não interativo]. Evento virtual, E.U.A.: Associação para máquinas de computação. Procedimentos da conferência ACM SIGSAC sobre segurança de computadores e comunicações 2020. CCS '20 (em inglês): 1591 à 1605. ISBN 978-1-4503-7089-9. doi:10.1145/3372297.3423366. Consultado em 27 de junho de 2021

[9] «PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab» [PPPL e Princeton demonstram nova técnica que pode ter aplicabilidade em futuras palestras de desarmamento nuclear - Laboratório de física de plasma de Princeton]. www.pppl.gov (em inglês). Consultado em 27 de junho de 2021

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Linha 1: / Linha 1: @@
-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.
+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 conhece um valor ''x'' sem transmitir qualquer informação além do fato de que eles conhecem o valor ''x''. 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.<ref name=":0" />
+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 não o conhecimento em si. 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.<ref name=":0">
+{{citar web
+|url=https://www.expressvpn.com/blog/zero-knowledge-proofs-explained/
+|title=What is a zero-knowledge proof and why is it useful?
+|títulotrad=O que é uma prova de conhecimento zero e por que é útil?
+|língua=en
+|date=16-11-2017
+|acessodata=27-06-2021}}
+</ref>
+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 <!-- [[:en:Non-interactive zero-knowledge proof]] -->provas de conhecimento zero não interativas, <ref name="noninteractive">
+{{citar livro
+|nome1=Manuel
+|sobrenome1=Blum
+|nome2=Paul
+|sobrenome2=Feldman
+|nome3=Silvio
+|sobrenome3=Micali
+|título=Non-interactive zero-knowledge and its applications
+|títulotrad=Conhecimento zero não interativo e suas aplicações
+|língua=en
+|periódico=Procedimentos do vigésimo simpósio anual da ''ACM'' sobre teoria da computação (STOC 1988)
+|páginas=103 à 112
+|ano=1988
+|doi=10.1145/62212.62222
+|url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA222698
+|urlmorta=sim
+|isbn=978-0897912648
+<!-- |s2cid=7282320 -->
+|acessodata=27-06-2021}}
+</ref><ref name=noninteractive2>{{citar periódico
+|sobrenome1=Wu
+|nome1=Huixin
+|sobrenome2=Wang
+|nome2=Feng
+|título=A survey of noninteractive zero knowledge proof system and its applications
+|títulotrad=Um levantamento do sistema de prova de conhecimento zero não interativo e suas aplicações
+|língua=en
+|journal=O jornal científico mundial
+|ano=2014
+|volume=2014
+|página=560484
+|doi=10.1155/2014/560484
+|pmid=24883407
+|pmc=4032740
+|acessodata=27-06-2021}}
+</ref> mas a validade da prova depende de suposições computacionais (normalmente as suposições de uma [[Função hash criptográfica|função de dispersão criptográfica]] ideal).
 == Exemplo abstrato ==
@@ Linha 33: / Linha 85: @@
 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.
-== Exemplo prático ==
+== Exemplos práticos ==
+=== Logaritmo discreto de um determinado valor ===
+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 [[Teoria dos grupos|grupo]].<ref>
+{{citar livro
+|nome1=David
+|sobrenome1=Chaum
+|nome2=Jan-Hendrik
+|sobrenome2=Evertse
+|nome3=Jeroen
+|sobrenome3=van de Graaf
+|título=An improved protocol for demonstrating possession of discrete logarithms and some generalizations
+|títulotrad=Um protocolo melhorado para demonstrar a posse de logaritmos discretos e algumas generalizações
+|língua=en
+|journal=Avanços em criptologia - EuroCrypt '87: procedimentos
+|volume=304
+|páginas=127 à 141
+|ano=1987
+|doi=10.1007/3-540-39118-5_13 |series=Lecture notes in computer science
+|isbn=978-3-540-19102-5}}
+</ref>
+Por exemplo, dado um valor <math>y</math>, um grande [[Número primo|primo]] <math>p</math> e um gerador <math>g</math>, ela quer provar que conhece um valor <math>x</math> tal que <math>g^x \bmod{p} = y</math>, sem revelar <math>x</math>. De fato, o conhecimento de <math>x</math> poderia ser usado como prova de identidade, pois Peggy poderia ter tal conhecimento porque escolheu um valor aleatório <math>x</math> que ela não revelou a ninguém, calculado <math>y = g^x \bmod{p}</math> e distribuiu o valor de <math>y</math> para todos os verificadores potenciais, de forma que, mais tarde, provar conhecimento de <math>x</math> é equivalente a provar sua identidade como Peggy.
+O protocolo procede da seguinte forma: em cada rodada, Peggy gera um número aleatório <math>r</math>, calcula <math>C = g^r \bmod{p}</math> e divulga isso para Victor. Depois de receber <math>C</math>, Victor aleatoriamente emite uma das seguintes duas solicitações: ele solicita que Peggy divulgue o valor de <math>r</math> ou o valor de <math>(x + r) \bmod{(p - 1)}</math>. 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 <math>r</math>, ele pode então calcular <math>g^r \bmod{p}</math> e verificar se corresponde a <math>C</math>. Se ele solicitou <math>(x + r) \bmod{(p - 1)}</math>, ele pode verificar que <math>C</math> é consistente com isso, calculando <math>g^{(x + r) \bmod{(p - 1)}} \bmod{p}</math> e verificando se ele corresponde a <math>C \cdot y \bmod{p}</math>. Se Peggy realmente conhece o valor de <math>x</math>, 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 <math>x</math> quando ela não conhece. Se ela sabe que Victor vai solicitar <math>r</math>, então ela procede normalmente: ela escolhe <math>r</math>, calcula <math>C = g^r \bmod{p}</math>, divulga <math>C</math> para Victor e será capaz de responder ao desafio. Por outro lado, se ela souber que Victor solicitará <math>(x + r) \bmod{(p - 1)}</math>, então ela escolhe um valor aleatório <math>r'</math>, calcula <math>C' = g^{r'} \cdot \left(g^x\right)^{-1} \bmod{p}</math>, e divulga <math>C'</math> para Victor como o valor de <math>C</math> que ele está esperando. Quando Victor a desafia a revelar <math>(x + r) \bmod{(p - 1)}</math>, ela revela <math>r'</math>, para o qual Victor verificará a consistência, pois ele por sua vez calculará <math>g^{r'} \bmod{p}</math>, que corresponde a <math>C' \cdot y</math>, desde que Peggy tenha multiplicado pelo <!-- [[:en:Modular multiplicative inverse]] -->
+inverso multiplicativo modular de <math>y</math>.
+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 <math>r</math> e divulgou <math>C = g^r \bmod{p}</math>, será incapaz de produzir um <math>(x + r) \bmod{(p - 1)}</math> válido que passaria pela verificação de Victor, visto que não conhece <math>x</math>. E se escolheu um valor <math>r'</math> que se apresenta como <math>(x + r) \bmod{(p - 1)}</math>, 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.
+==== Breve resumo ====
+Peggy prova saber o valor de x (por exemplo, sua senha).
+#Peggy e Victor concordam em um primo <math>p</math> e um gerador <math>g</math> do grupo multiplicativo do campo <math>\mathbb{Z}_{p}</math>.
+#Peggy calcula o valor <math>y = g^x \bmod{p}</math> e transfere o valor para Victor.
+#As duas etapas a seguir são repetidas um (grande) número de vezes.
+##Peggy escolhe repetidamente um valor aleatório <math>r\in U[0, p-1]</math>, calcula <math>C = g^r \bmod{p}</math> e transfere o valor <math>C</math> para Victor.
+##Victor pede a Peggy que calcule e transfira o valor <math>(x + r) \bmod{(p-1)}</math> ou o valor <math>r</math>. No primeiro caso, ele verifica <math>(C \cdot y) \bmod{p}\equiv g^{(x + r) \bmod{(p - 1)}} \bmod{p}</math>. Já no segundo caso, ele verifica <math>C \equiv g^{r} \bmod{p}</math>.
+O valor <math>(x + r) \bmod (p-1)</math> pode ser visto como o valor criptografado de <math>x \bmod (p-1)</math>. Se <math>r</math> é verdadeiramente aleatório, igualmente distribuído entre zero e <math>(p-1)</math>, isso não vaza nenhuma informação sobre <math>x</math> (verifique o artigo [[One-time pad|cifra de uso único ou chave de uso único (''OTP'')]]).
+=== Ciclo hamiltoniano para um grande gráfico  ===
 Podemos estender estas ideias para uma aplicação mais real de criptografia. Neste cenário, Priscila conhece o [[Caminho hamiltoniano|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.<ref>http://www.bennetyee.org/ucsd-pages/ZKP.html (em inglês)</ref> 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).
@@ Linha 72: / Linha 172: @@
 == Aplicações ==
+=== Sistemas de autenticação ===
-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 [[prova de conhecimento|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.
+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 "<!-- [[:en:Proof of knowledge]]-->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 <!-- [[:en:Zero-knowledge password proof]] -->prova de senha de conhecimento zero é um tipo especial de prova de conhecimento de conhecimento zero que aborda o tamanho limitado das senhas. {{citation needed|data=06-2021}}
+=== Comportamento ético ===
+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.<ref name="knowledgecomplexity">
+{{Citation
+|last1=Goldwasser
+|first1=S.
+|last2=Micali
+|first2=S.
+|last3=Rackoff
+|first3=C.
+|title=The knowledge complexity of interactive proof systems
+|títulotrad=A complexidade do conhecimento dos sistemas de prova interativa
+|língua=en
+|url=http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf
+|acessodata=27-06-2021
+|doi=10.1137/0218012
+|year=1989
+|journal=Jornal ''SIAM'' sobre computação
+|issn=1095-7111
+|volume=18
+|issue=1
+|pages=186 à 208}}
+</ref><ref>
+{{Cite journal
+|last=Abascal
+|first=Jackson
+|last2=Faghihi Sereshgi
+|first2=Mohammad Hossein
+|last3=Hazay
+|first3=Carmit
+|last4=Ishai
+|first4=Yuval
+|last5=Venkitasubramaniam
+|first5=Muthuramakrishnan
+|date=30-10-2020
+|title=Is the classical GMW paradigm practical? The case of non-interactive actively secure 2PC
+|títulotrad=O paradigma ''GMW'' clássico é prático? O caso do ''2PC'' ativamente seguro não interativo
+|língua=en
+|url=https://doi.org/10.1145/3372297.3423366
+|journal=Procedimentos da conferência ''ACM'' ''SIGSAC'' sobre segurança de computadores e comunicações 2020
+|series=CCS '20
+|location=Evento virtual, E.U.A.
+|publisher=Associação para máquinas de computação
+|pages=1591 à 1605
+|doi=10.1145/3372297.3423366
+|isbn=978-1-4503-7089-9
+|acessodata=27-06-2021}}
+</ref> 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.{{citation needed|date=06-2021}}
+=== Desarmamento nuclear ===
+Em 2016, o <!-- [[:en:Princeton Plasma Physics Laboratory]] -->
-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 corretude, 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 [[Oded Goldreich|Goldreich]], [[Silvio Micali|Micali]] e Wigderson em [[computação multipartidárias segura]].
+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.<ref>
+{{cite web
+|url=http://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear
+|língua=en
+|title=PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab
+|títulotrad=''PPPL'' e ''Princeton'' demonstram nova técnica que pode ter aplicabilidade em futuras palestras de desarmamento nuclear - Laboratório de física de plasma de ''Princeton''
+|website=www.pppl.gov
+|acessodata=27-06-2021}}
+</ref>
 ==Notas==