Como Explicar Protocolos Zero-Knowledge para Seus Filhos

A Caverna Estranha de Ali Babá
Saibam, crianças, que há muito tempo atrás, a leste de Bagdá, vivia um senhor chamado Ali Babá. Todos os dias Ali Babá ia ao bazar comprar e vender coisas. Esta história é um pouco sobre Ali Babá e um pouco sobre uma caverna. Uma caverna estranha cujo segredo e encanto existem até hoje. Mas, eu vou me antecipar…

Um dia, no bazar de Bagdá, um ladrão pegou uma bolsa de Ali Babá, que imediatamente começou a correr atrás dele. O ladrão se refugiou numa caverna cuja entrada se bifurcava em duas passagens escuras e sinuosas: uma para a esquerda e outra para a direita.

Ali Babá não viu em qual passagem o ladrão entrou. Ali Babá tinha que escolher qual caminho seguir. E decidiu ir pela passagem da esquerda. A passagem da esquerda acabou em um beco sem saída. Ali Babá procurou por todo o beco sem saída, mas não encontrou o ladrão. Ali babá pensou consigo mesmo que o ladrão talvez tivesse na outra passagem. Então ele foi para lá, mas este também era um beco sem saída. De novo, ele não encontrou o ladrão. “Esta caverna é bem estranha”, falou consigo mesmo. “Para onde o ladrão foi?”

No dia seguinte, outro ladrão pegou a cesta do Ali Babá e se refugiou, como o outro ladrão fez, na caverna estranha. Ali babá o perseguiu e de novo não viu qual caminho o ladrão pegou. Dessa vez Ali babá decidiu procurar pela direita. Ele foi por todo o trecho da passagem da direita, mas não encontrou o ladrão. Ele pensou consigo mesmo que, como o primeiro ladrão, o segundo também teve sorte em ir pela passagem diferente da que Ali Babá escolheu para a busca. Isto fez com que, sem dúvida, o ladrão pudesse sair de novo e se misturar calmamente ao bazar congestionado.

Os dias se passaram, e cada dia trouxe seu ladrão. Ali Babá sempre correu atrás do ladrão, mas nunca pegou nenhum deles. No quadragésimo dia, um quadragésimo ladrão pegou o turbante do Ali Babá e se refugiou, como os outros trinta e nove ladrões anteriores a ele, na caverna estranha. Ali Babá, de novo, não viu para qual caminho o ladrão foi. Dessa vez, Ali babá resolveu ir pelo caminho da esquerda, mas de novo, ele não conseguiu achar o ladrão no final da passagem. Ali Babá estava muito confuso.

Ele poderia pensar, como fez anteriormente, que o ladrão tivesse tido sorte, como os outros trinta e nove ladrões. Mas, essa explicação era tão inverossímil que mesmo Ali Babá não acreditava nela. A sorte dos quarenta ladrões era muito boa para ser uma questão do acaso. Havia apenas uma chance em milhões de milhões que todos os quarenta escapariam! Então Ali Babá falou consigo mesmo que deveria haver uma explicação mais provável. Ele começou a suspeitar de que a caverna guardava um segredo!

E Ali Babá partiu para descobrir o segredo da caverna estranha. Ele decidiu se esconder debaixo de uns sacos no final da passagem da direita. Depois de uma espera bastante desconfortável ele viu um ladrão entrar que, percebendo que estava sendo perseguido por sua vítima, sussurrou as palavras mágicas: “Abra-te sésamo”. Ali Babá ficou espantado de ver a parede da caverna deslizar e abrir. O ladrão correu pela abertura. Então, a parede se fechou deslizando de novo. O perseguidor chegou e ficou perturbado de ver apenas Ali Babá debaixo dos sacos no beco sem saída da passagem. O ladrão havia escapado. Mas, Ali Babá estava todo feliz porque ele tinha descoberto o Segredo da Caverna Estranha.

Ali Babá experimentou as palavras mágicas. Ele descobriu, para sua surpresa, que quando a parede deslizou abrindo a passagem da direita era conectada com a passagem da esquerda. Agora Ali Babá sabia como os quarenta ladrões haviam escapado dele.
Ali Babá trabalhou e trabalhou com as palavras mágicas e ele finalmente conseguiu substituí-las por novas palavras mágicas, um pouco como se muda a combinação de alguns cadeados. No dia seguinte um ladrão foi pego. Ali Babá gravou essa história num lindo manuscrito iluminado. Ele não escreveu as novas palavras mágicas, mas ele incluiu algumas pistas sutis sobre elas.

O Destino do Manuscrito

O lindo manuscrito iluminado de Ali Babá chegou na Itália na Idade Média. Hoje, está nos Estados Unidos, perto de Boston. Lá ele recentemente chamou toda a atenção de alguns pesquisadores curiosos. Por meio da descrição de pistas sutis, esses pesquisadores recuperaram as novas palavras mágicas!

Depois de algumas escavações nas ruínas do antigo bazar de Bagdá, a caverna estranha foi localizada. Não era uma lenda! E, apesar dos séculos, as palavras mágicas ainda funcionavam. Todos inquietos, os pesquisadores curiosos passaram pelo beco sem saída entre as duas passagens.

As redes de televisão logo tomaram conhecimento dos eventos incomuns que estavam acontecendo em Bagdá. Uma enorme rede americana até conseguiu exclusividade da história. Um dos pesquisadores, Mick Ali, talvez um descendente de Ali babá, quis demonstrar que conhecia o segredo. Mas, ele não queria revelar o segredo. Eis o que ele fez.

Primeiramente, uma equipe de televisão filmou um tour detalhado da caverna com as duas passagens sem saída. Então, todos entraram na caverna. Mick Ali entrou sozinho e pegou uma das passagens. Então o repórter, acompanhado da câmera, entrou apenas até a bifurcação. Depois ele lançou uma moeda para escolher entre esquerda e direita. Se a moeda caísse cara, ele iria pedir ao Mick para sair à direita. Se a moeda caísse coroa, ele pediria a Mick para sair à esquerda. Caiu cara, então o repórter falou bem alto: “Mick saia pela direita”. E o Mick fez exatamente isso.

Em memória aos quarenta ladrões, essa cena de demonstração foi repetida quarenta vezes. Cada uma das vezes, todos voltaram para fora da caverna e o Mick entrou sozinho todo o caminho para uma das passagens. Então, o repórter e a câmera iam até a bifurcação onde ele escolhia lançando uma moeda qual seria a ordem a dar para o Mick. Mick obteve sucesso em todas as quarenta cenas.

Qualquer um que não conhecesse o segredo da caverna estaria exposto na primeira falha. Cada novo teste dividia em duas as chances de obter sucesso de alguém que não tivesse o segredo. Por outro lado, o segredo permitiu que Mick surgisse, todas as vezes, na saída selecionada.

O Repórter Invejoso

Contratado de uma outra rede de televisão, um repórter invejoso, também queria filmar uma história na caverna estranha. Mick se
recusou a participar porque ele tinha dado exclusividade de direitos sobre a história para a primeira rede.

Mas Mick, maliciosamente, sugeriu ao repórter invejoso que a história poderia ser filmada sem a posse do segredo. O repórter invejoso pensou e pensou e finalmente compreendeu. Ele disse para si mesmo: “Eu até conheço um ator de palco que se parece com Mick Ali e que poderia se passar por ele”.

E a segunda história foi filmada. No decorrer da filmagem metade das cenas foram estragadas porque o dublê do Mick não sabia como passar de um lado para o outro! O repórter invejoso editou a gravação e manteve apenas as cenas bem sucedidas até que tivesse quarenta delas.

As duas histórias foram transmitidas na mesma hora da mesma tarde pelas duas redes americanas concorrentes. O caso foi levado a tribunal. Ambas as fitas de vídeo foram colocadas em evidência. Mas, os juízes e experts não conseguiram diferenciá-las. Qual delas era falsificada e qual original? As fitas por si só não eram suficientes para o julgamento.

A simulação, com certeza, não forneceu o conhecimento do segredo. Mas a simulação e a fita genuína não conseguiram ser distinguidas. Assim, a fita genuína não forneceu o conhecimento do segredo também. O repórter que conseguiu a exclusividade da história se convenceu naquele momento de que Mick Ali possuía o segredo, mas o repórter não pôde passar sua convicção para os juízes na corte nem para a audiência de televisão também.

Mick Ali atingiu seu objetivo real. Ele queria, de fato, mostrar que é possível convencer sem revelar e, portanto, sem desvendar o segredo.

Os Testes em Paralelo

Enquanto isso, outros pesquisadores em Israel observaram que usando alguns segredos e fazendo testes em paralelo, poderiam reduzir o número de cenas no filme. Em outras palavras, a duração da autenticação.

Eles imaginaram um prédio de apartamentos com uma caverna em cada andar, cada uma possuindo suas palavras mágicas. O que eles precisavam era de um ator para cada caverna. Todos os andares poderiam ser filmados de uma vez para ver de onde o autor surgiria em cada andar.

Eles até propuseram uma solução aritmética onde uma réplica, com um único número como prova, poderia substituir vários atores.

Ainda, um meio-termo entre o número de segredos e o número de cenas para filmar pode não ser sempre otimizado. Seria muito melhor ter um único segredo e uma única cena.

Além disso, a simulação com sucessivas tentativas torna-se cada vez menos prática à medida que o número de segredos aumenta.

O Acordo Prévio

Tudo isso realmente intrigou os pesquisadores europeus. Eles fizeram uma observação que se aplica igualmente para a versão serial e a versão paralela. Para economizar tempo na filmagem, o repórter invejoso e o dublê do Mick Ali teriam sido bastante espertos em pensar em concordar antecipadamente com uma lista de quarenta seleções randomizadas entre direita e esquerda. Durante a filmagem, o repórter invejoso teria, então, fingido escolher as questões ao acaso em sua mente, e o dublê, que já conhecia antecipadamente, as questões que teria que responder, não precisaria conhecer o segredo e poderia passar em todos os testes um após o outro.

Consequentemente, à técnica de simulação de tentativas sucessivas em que somente as cenas bem-sucedidas são conservadas, foi acrescentada a técnica de simulação de acordo prévio entre o provador e o verificador.

Um Único Teste, um Único Segredo

Em resposta a essa observação uma nova caverna foi construída com mais passagens terminando numa bifurcação (A Caverna Revisada).

Certamente a construção física da caverna torna-se problemática quando o número de passagens aumenta. Não é possível construir uma caverna com um milhão de milhões de passagens. Mas qualquer que seja o número de passagens, pode-se simular com acordo prévio. Um esquema mais aritmético permitiria que o verificador pudesse escolher uma questão de uma série de milhões e milhões de questões. Com um único teste você poderia diretamente alcançar o nível de segurança obtido por quarenta testes sucessivos na caverna com duas passagens.

A corte é completamente incapaz de distinguir entre os videotapes: um retratando uma demonstração, o outro uma simulação por acordo prévio. Consequentemente, mesmo quando o tamanho da questão é grande, a demonstração não mostra conhecimento do valor do segredo.

Epílogo

Então, crianças, vocês acabaram de ouvir como Ali Babá aprendeu o segredo da caverna estranha e como seu descendente, o pesquisador esperto Mick Ali foi capaz de convencer um repórter de televisão de que ele conhecia o segredo sem ter que contar para ele qual seria o segredo. Incontável número de pessoas viu Mick Ali na televisão e ele se tornou famoso e se aventurou pelo mundo. Ele ainda não revelou o segredo da caverna estranha, mas convenceu muitas outras pessoas, inclusive eu, que ele conhece o segredo. Guardar segredos me lembra de uma história de Merkle Hellman e sua mochila super-increasing. Mas, já é tarde. Essa é uma outra história, para um outro momento.

Reconhecimentos - Agradeço ao Gilles Brassard por seu contínuo interesse e suporte.

Este artigo foi escrito por: QUISQUATER Jean-Jacques(1), Myriam, Muriel, Michaël GUILLOU Louis(2), Marie Annick, Gaïd, Anna, Gwenolé, Soazig in collaboration with Tom BERSON(3)
(1)Philips Research Laboratory, Avenue Van Becelaere,2, B-1170 Brussels, Belgium.
(2)CCETT/EPT, BP 59, F-35512 Cesson Sévigné, France,
(3)Anagram Laboratories, P.O. Box 791, Palo Alto CA 94301, USA., e traduzido por Fátima Lima. Seu original pode ser lido aqui