Foto: Katherine Taylor/Quanta MagazineQUANTA - Yael Tauman Kalai é uma cientista da computação pioneira que atua no campo da ciência da computação teórica, já ganhou prêmios impressionantes e mudou a forma como as pessoas pensam sobre a internet. Mas quando era uma criança, ela não era exatamente uma aluna exemplar.
“Eu era uma encrenqueira”, disse ela. “Basicamente fui – não exatamente, mas praticamente – expulsa no ensino médio.”
Yael nasceu e cresceu em Tel Aviv, Israel, numa família de pesquisadores. O pai dela, Yair Tauman, é economista e pesquisa teoria dos jogos. As aulas no ensino médio a entediavam – um boletim registrou algo em torno de 150 faltas, lembra, pois ela preferia gastar seu tempo praticando esqui aquático e socializando. Mas as habilidades analíticas dela sempre estiveram presentes.
“Quando meus pais não me deixavam sair, muitas vezes a única maneira de fazer com que meu pai deixasse era dizer a ele: ‘Ok, me dê um problema de matemática para resolver. Com o grau de dificuldade que você quiser, mas se eu conseguir resolvê-lo, saio’.” E ela costumava conseguir.
O amor latente dela pela matemática finalmente despertou na faculdade, quando ela começou a reconhecer a beleza da área. Por fim, ela descobriu que poderia usar essa matemática com computadores e, especificamente, para proteger informações. Agora, o trabalho dela une as áreas de matemática e ciência da computação, e as ideias dela têm sido fundamentais para como protegemos e verificamos a computação na era digital. Nas últimas duas décadas, ela trabalhou para garantir a integridade de nossos smartphones, conexões em nuvem e até mesmo das criptomoedas. Hoje ela é pesquisadora da Microsoft e professora do Instituto de Tecnologia de Massachusetts, ganhou recentemente o prestigioso Prêmio ACM da Association for Computer Machinery, na categoria computação, pelos “avanços na delegação verificável da computação e contribuições fundamentais para a criptografia”. O trabalho mais recente dela também está de olho no futuro, já que ela analisa cuidadosamente como os computadores quânticos talvez afetem o cenário da segurança.
A Quanta conversou com Yael sobre o vazamento de segredos, a verificação na nuvem e a peculiaridade da computação quântica. A entrevista foi resumida e editada por questões de clareza.
Como você foi de encrenqueira no ensino médio a pesquisadora?
Sempre soube que amava matemática, mas a matemática no ensino médio não era interessante de jeito nenhum. Então fui estudar matemática na graduação e fiquei encantada. Foi a primeira vez na minha vida em que me sentei e estudei sem parar, o dia todo. Eu fiquei eufórica. E devo confessar ter ficado um pouco chateada, pois pensei: “Não acredito que poderia ter gostado disso quando era bem mais jovem!”.
O que foi que lhe encantou na matemática?
Ela é muito clara, elegante e abstrata. E alguns conceitos em matemática são contraintuitivos; lembro de sentir que estudá-la estava me fazendo mudar como pessoa. Você aprende a ser humilde, porque descobre inúmeras vezes que seu palpite estava errado.
Mas quando estava em busca de uma boa pergunta norteadora de pesquisa, tudo parecia incremental. Então comecei a ir para o lado da ciência da computação. E a criptografia era exatamente o que eu estava sentindo falta, porque ela lida com problemas do mundo real. Hoje ela é usada em todos os lugares. Ela é usada para garantir que as mensagens enviadas por nós sejam confidenciais e de confiança. Quando escrevo uma mensagem de texto para alguém, como eu sei que a mensagem recebida é a mensagem que foi enviada? Como sei que a pessoa que afirma ter enviado a mensagem é de fato quem a enviou? O que significa saber isso? Os conceitos são muito filosóficos e a forma como os modelamos matematicamente é muito bonita. Era exatamente o que eu precisava, tanto em relação à pureza da matemática como à aplicabilidade.
Com que tipo de problemas criptográficos você já trabalhou?
Minha dissertação de mestrado teve como título “Como vazar um segredo”. Eis o problema: sabemos como assinar algo digitalmente – para dizer, “fui eu que escrevi esta mensagem”. Mas digamos que eu deseje assinar algo como professora do MIT, porém não queira que as pessoas saibam que sou eu? Dessa forma, o segredo faz sentido porque você sabe que um professor do MIT assinou algo, mas não sabe quem foi.
Resolvemos isso com algo que chamamos de assinatura em anel, que foi inspirado pelo conceito em ciência da computação chamado “witness-indistinguishable proofs” (prova indistinguível de testemunha). Digamos que haja uma afirmação e duas maneiras diferentes de prová-la. Dizemos que há duas “testemunhas” para que a afirmação seja correta – cada uma das provas. Uma prova indistinguível de testemunha parece a mesma, não importa qual você use: ela oculta com qual testemunha você começou.
As assinaturas em anel são semelhantes. Em um grupo com possíveis vazadores de segredos, você pode imaginar cada pessoa como tendo uma senha secreta. E a assinatura em anel está basicamente provando que esta mensagem foi assinada por alguém com uma das senhas secretas, mas não revela qual delas foi. Ela oculta de quem é a senha secreta utilizada.
Será que uma instituição usaria mesmo esse sistema?
Essa é a parte bela e assustadora disso – posso fazer isso sem que ninguém mais esteja envolvido. Posso assinar como um integrante do grupo sem a permissão do grupo. Não está claro se isso é um recurso ou um bug, mas está claro que é uma descoberta científica. As assinaturas em anel vêm sendo usadas – há uma criptomoeda chamada Monero que diz usá-la para a privacidade das transações. Mas, sinceramente, não sei de verdade quem está usando nosso trabalho. A verdade é que estou ocupada demais para acompanhar isso.
Como seu trabalho evoluiu para a análise de segurança de nossos dispositivos?
No início dos anos 2000, estava terminando meu doutorado, sendo orientada por Shafi Goldwasser no MIT. As pessoas estavam começando a falar de computação em nuvem, que agora usamos todos os dias. Antes, você tinha um computador enorme onde fazia tudo. Com o aumento da coleta de dados, o processamento de dados se tornou mais caro e ele começou a ser feito remotamente. A ideia é que há uma nuvem poderosa que faz o processamento de dados para você. Mas você talvez não confie na plataforma na nuvem, então como saber se estão processando os dados corretamente? Talvez exista um incentivo para trapaças, pois o processamento de dados pode ser muito caro. Em algumas configurações, você pode ficar preocupado com erros aleatórios. Então, você realmente quer uma prova de que o processamento de dados está correto.
No entanto, as provas costumam ser muito longas e os dispositivos fracos não conseguem verificar provas longas. Mesmo no caso dos dispositivos que conseguem, isso sai muito caro. Então, existe uma forma de encurtar as provas? Do ponto de vista da teoria da informação, não. Mas descobrimos que, usando ferramentas criptográficas, podemos em vez disso gerar certificados sucintos que são muito, muito difíceis de se falsificar. Eles são chamados de argumentos sucintos e não interativos de conhecimento (SNARGs, na sigla em inglês). Na verdade, eles não são uma prova. Mas contanto que você não consiga resolver algum problema que nós, criptógrafos, acreditamos ser muito difícil, como fatorar números grandes, não é possível falsificar as provas sucintas.
Como surgiram essas provas?
Tudo começou em 1985 com Goldwasser, Silvio Micali e Charles Rackoff, que juntos apresentaram uma noção de provas interativas. Antes, quando as pessoas pensavam em provas, pensavam em escrever fileiras de dados, e conseguir ler e verificar se estavam corretas ou não. Goldwasser, Micali e Rackoff apresentaram uma maneira completamente diferente de provar algo: usando a interação. Há um provador e um verificador, e eles trocam mensagens entre si. Em seguida, o verificador decide se ambos estão convencidos ou não.
Vou dar um exemplo de algo que é mais fácil de se fazer com uma prova interativa do que com uma prova clássica. Faz de conta que estamos jogando xadrez. Agora, imagine que eu queira provar para você que tenho uma estratégia vencedora. Não importa quais movimentações você faça, eu ainda vou ganhar. Como provo isso para você?
Do ponto de vista clássico, trata-se de uma prova enorme, porque preciso provar que minha estratégia funciona contra todas as combinações possíveis de movimentações. Mas, acontece que, por meio da interação, posso fazer isso de forma muito sucinta. Se não acredita que tenho uma estratégia vencedora, vamos jogar então. Vou mostrar para você que vou ganhar. É claro que isso por si só não é convincente – só porque posso ganhar uma vez de você não significa que posso ganhar contra qualquer pessoa. Então me deixe jogar contra um grão-mestre. Ganharei do grão-mestre. Isso começa a demonstrar o poder da interação.
Mas a desvantagem de uma prova interativa é que ela não é transferível. Digamos que você me dê uma cédula de cem dólares e prove, por meio da interação, que ela de fato vale US$ 100. Quero poder transmitir isso. Quero dá-la para outra pessoa, que dará para outra pessoa. Mas se eu tivesse apenas uma prova interativa, isso não significa nada; não posso dá-la para mais ninguém. Portanto, a coisa boa dos SNARGs é que você pode repassá-los para outras pessoas.
Como um certificado de autenticidade?
Exatamente. As blockchains são o principal lugar onde eles são usados hoje, para verificar as transações. Quando a tecnologia blockchain surgiu, disse aos meus alunos que deveríamos mandar flores e chocolates para o criador do bitcoin, Satoshi Nakamoto, porque ele realmente tornou nosso trabalho muito relevante.
Então, como você remove a interação para criar esses certificados transferíveis?
Com criptografia. Vou tentar dar uma ideia de como isso funciona. Em nossas provas interativas, o verificador geralmente apenas envia aleatoriedade ao provador – podemos imaginar isso como o verificador aleatoriamente examinando a prova. Então Amos Fiat e Adi Shamir tiveram uma ideia: por que precisamos desse verificador se tudo que ele faz é enviar aleatoriedade? Talvez possamos substituir esse verificador por alguma função, como algo chamado de função hash – é uma função que parece aleatória e é um componente muito importante na criptografia.
E descobrimos que, sim, podemos fazer isso. Hoje, isso é feito o tempo todo. Se você tem um iPhone ou um celular com sistema Android, está usando o paradigma Fiat-Shamir quando seu telefone se conecta a servidores remotos, o que pode acontecer com frequência ao longo do dia. E é esse paradigma que usamos para criar as provas sucintas que certificam que o processamento de dados remoto está correto.
Você falou das máquinas que precisam ser “seguras pós-computadores quânticos”. O que isso significa?
Os computadores quânticos, se eles realmente vierem a existir em larga escala, serão muito mais poderosos do que os computadores clássicos. Os computadores clássicos funcionam com bits, que são 0 ou 1. Com os computadores quânticos, você tem os bits quânticos, que estão em sobreposição entre o 0 e o 1. E esses qubits estão emaranhados, o que significa que eles influenciam uns aos outros. É isso que realmente dá poder de processamento aos computadores quânticos.
No futuro, talvez nem todos tenham um computador desktop quântico. Pode ser que existam alguns dispositivos quânticos caros que façam o processamento de dados remoto para você. Suponhamos que você queira delegar um processamento de dados caro a um desses dispositivos quânticos e precise de algum certificado para verificar que o resultado é correto – como você certifica a precisão dos computadores quânticos? Agora que queremos usar bits quânticos e não bits clássicos, tudo muda, principalmente quando quero que o verificador seja um computador clássico.
Em 2018, houve um resultado revolucionário de uma estudante de Berkeley, Urmila Mahadev. Ela foi a primeira a mostrar uma prova clássica e, do ponto de vista computacional, segura para a verificação de processamento de dados quânticos.
No futuro, talvez nem todos tenham um computador desktop quântico.
Yael Tauman Kalai, cientista
Quer dizer que podemos usar um computador clássico para verificar processamento de dados quânticos? Isso parece impossível!
Não é incrível? Eu estava na comissão do programa quando Urmila publicou o artigo dela, e passei a noite toda analisando ele – você não faz ideia do tanto de café que tomei! Fiquei de queixo caído. A essa altura, estava me sentindo uma tonta em relação à computação quântica. Eu entendia a parte de criptografia, mas levou um tempo até entender como aquilo se conectava com a parte quântica. E foi lindo.
Passar da computação clássica para a computação quântica soa como uma curva de aprendizado brusca.
Sei disso. Na verdade, não sei nada de física, e há muito insight de física quântica envolvido. Não entendo os conceitos mais básicos, como energia e temperatura. Às vezes trabalho com estudantes e assim que começamos a falar de computação quântica, eu me transformo em aluna. Estou começando a ter um pouco mais de ideia do assunto. E confesso que estou gostando bastante disso, ficar sentada com um livro sobre teoria da informação quântica. Não há nada melhor do que ser uma estudante!
História original republicada com permissão da Quanta Magazine, uma publicação editorialmente independente apoiada pela Simons Foundation. Leia o conteúdo original em The Cryptographer Who Ensures We Can Trust Our Computers.
