As provas de conhecimento zero permitem que os pesquisadores comprovem seus conhecimentos sem divulgar o conhecimento em si.
Imagine que você tenha algum conhecimento útil – talvez uma receita secreta ou a chave para uma cifra. Você poderia provar a um amigo que tinha esse conhecimento, sem revelar nada sobre isso? Cientistas da computação provaram há mais de 30 anos que você poderia, se usasse o que é chamado de prova de conhecimento zero.
Para uma forma simples de entender essa ideia, vamos supor que você queira mostrar ao seu amigo que sabe como passar por um labirinto, sem divulgar nenhum detalhe sobre o caminho. Você poderia simplesmente atravessar o labirinto dentro de um limite de tempo, enquanto seu amigo estava proibido de assistir. (O limite de tempo é necessário porque, com tempo suficiente, qualquer um pode encontrar a saída por tentativa e erro.) Seu amigo saberia que você poderia fazer isso, mas não saberia como.
Provas de conhecimento zero são úteis para criptógrafos, que trabalham com informações secretas, mas também para pesquisadores de complexidade computacional, que lidam com a classificação da dificuldade de diferentes problemas. “Muita criptografia moderna se baseia em suposições de complexidade – na suposição de que certos problemas são difíceis de resolver, então sempre houve algumas conexões entre os dois mundos”, disse Claude Crépeau, cientista da computação da Universidade McGill. “Mas [essas] provas criaram todo um mundo de conexão.”
As provas de conhecimento zero pertencem a uma categoria conhecida como provas interativas, portanto, para aprender como as primeiras funcionam, ajuda a entender as últimas. Descritas pela primeira vez em um artigo de 1985 pelos cientistas da computação Shafi Goldwasser, Silvio Micali e Charles Rackoff, as provas interativas funcionam como um interrogatório: por meio de uma série de mensagens, uma parte (o provador) tenta convencer a outra (o verificador) de que uma determinada afirmação é verdadeira. Uma prova interativa deve satisfazer duas propriedades. Primeiro, uma afirmação verdadeira sempre convencerá um verificador honesto. Em segundo lugar, se a afirmação dada é falsa, nenhum provador – mesmo aquele que finge possuir certo conhecimento – pode convencer o verificador, exceto com probabilidade desprezível.
As provas interativas são probabilísticas por natureza. O provador pode responder a uma ou duas perguntas corretamente simplesmente por sorte, então é preciso um número suficientemente grande de desafios, todos os quais o provador deve acertar, para que o verificador fique confiante de que o provador de fato sabe que a afirmação é verdadeira.
Essa ideia de interações surgiu quando Micali e Goldwasser – então estudantes de pós-graduação da Universidade da Califórnia, Berkeley – ficaram intrigados com a logística de jogar pôquer em uma rede. Como todos os jogadores podem verificar que quando um deles recebe uma carta do baralho virtual, o resultado é aleatório? Provas interativas podem abrir o caminho. Mas então, como os jogadores podem verificar se todo o protocolo – o conjunto completo de regras – foi seguido corretamente, sem revelar a mão de cada jogador ao longo do caminho?
Para atingir esse objetivo, Micali e Goldwasser acrescentaram uma terceira propriedade às duas necessárias para uma prova interativa: a prova não deve revelar nada sobre o conhecimento em si, apenas a veracidade da afirmação. “Há uma noção de passar por um protocolo, no final do qual você acredita que [os jogadores de poker] não sabem nada além do que deveriam saber”, disse Goldwasser.
Vamos considerar o exemplo clássico. Alice quer provar a Bob que um certo grafo G – uma coleção única de vértices (pontos) conectados por arestas (linhas) – tem um “ciclo hamiltoniano”. Isso significa que o gráfico tem um caminho que visita cada ponto exatamente uma vez e termina no mesmo ponto em que começou. Alice poderia fazer isso simplesmente mostrando a Bob o caminho que faz isso, mas é claro que ele também conheceria o caminho.
Veja como Alice pode convencer Bob de que ela sabe que esse caminho existe, sem mostrá-lo a ele. Primeiro, ela desenha um novo grafo, H, que não se parece com G, mas é semelhante de uma maneira crucial: tem o mesmo número de vértices, conectados da mesma maneira. (Se G realmente tiver um ciclo hamiltoniano, essa semelhança significa que H também terá.) Então, depois de cobrir todas as arestas de H com fita adesiva, ela prende H em uma caixa e entrega a caixa a Bob. Isso o impede de vê-lo diretamente, mas também impede que ela o altere. Então Bob faz uma escolha: ou ele pode pedir a Alice para mostrar que H realmente é semelhante a G, ou ele pode pedir a ela que lhe mostre o ciclo hamiltoniano em H. Ambas as solicitações devem ser fáceis para Alice, supondo que H realmente seja suficientemente semelhante para G, e que ela realmente conhece o caminho.
Claro, mesmo que Alice não conheça o ciclo hamiltoniano em G, ela pode tentar enganar Bob, desenhando gráficos que não são semelhantes a G, ou enviando gráficos para os quais ela não conhece o caminho. Mas depois que eles jogaram várias rodadas, a chance de Alice enganar Bob toda vez se torna muito pequena. Se ela acertar tudo, Bob acabará se convencendo de que Alice conhece um ciclo hamiltoniano no grafo G, sem que Bob nunca o tenha visto.
Após o artigo inicial que descreveu essas provas pela primeira vez, Micali e dois matemáticos – Oded Goldreich e Avi Wigderson – descobriram uma consequência inesperada com efeitos de longo alcance. Tem a ver com uma categoria principal de problemas de dificuldade aproximadamente igual, conhecida como NP. Esses problemas são difíceis de resolver, mas suas soluções são fáceis de verificar. Os três pesquisadores descobriram que, se a criptografia realmente segura for possível, a solução para todos os problemas em NP também pode ser comprovada com uma prova de conhecimento zero. Este estudo ajudou os pesquisadores a conceber variantes de provas de conhecimento zero que nem exigem criptografia segura em primeiro lugar; estas são conhecidas como provas interativas multi-provador.
E em 1988, Micali e outros mostraram que se um provador e um verificador compartilham uma pequena sequência de bits aleatórios, nenhuma interação é necessária. Isso teoricamente significava que as provas de conhecimento zero não precisam ser interativas, o que implicaria que a comunicação constante entre duas partes não é necessária. Isso os tornaria muito mais úteis para os pesquisadores, mas não foi até a virada do século 21 que essas provas decolaram.
“No final dos anos 2000, começamos a ver a evolução de técnicas eficientes para construir provas de conhecimento zero”, disse Matthew D. Green, criptógrafo da Universidade John Hopkins. “Chegamos ao ponto em que percebemos: ‘Espere um segundo, pode realmente haver uma maneira de usar isso na prática.'”
Agora, um provador pode enviar uma única mensagem para um verificador sem que ambos precisem estar online, e os pesquisadores podem criar uma prova muito curta que pode ser verificada rapidamente, mesmo para problemas muito complicados. Isso levou a vários usos práticos, como a capacidade de verificar rapidamente o blockchain após uma transação de criptomoeda enquanto oculta os detalhes da transação. E em 2016, um grupo de físicos mostrou como as provas de conhecimento zero podem ajudar no desarmamento nuclear: sem revelar nenhum segredo sobre o design de sua ogiva nuclear, um país agora pode provar aos inspetores nucleares se a ogiva está ativa ou inativa.
Mais recentemente, os avanços na computação quântica obrigaram Crépeau a testar pesquisas anteriores para garantir que os protocolos de conhecimento zero ainda sejam viáveis. Em 2021, ele ajudou a demonstrar que as provas interativas de vários provadores mantêm seu sigilo mesmo quando computadores quânticos estão envolvidos, mas alcançar o mesmo nível de segurança torna o protocolo muito mais lento. A descoberta foi uma boa notícia, disse ele, mas novas preocupações surgirão à medida que a tecnologia avançar.
“Todo tipo de computação que podemos fazer no futuro envolverá computadores quânticos”, disse Crépeau. “Então, como bons criptógrafos paranóicos, sempre que avaliamos a segurança de um sistema, queremos ter certeza de que nosso sistema é seguro.”
Publicado em 12/10/2022 10h27
Artigo original: