O criptógrafo que garante que podemos confiar em nossos computadores | Revista Quanta

Yael Tauman Kalai é uma cientista da computação teórica pioneira que ganhou prêmios impressionantes e mudou a maneira como as pessoas pensam sobre a Internet. Mas quando criança, ela não era exatamente uma aluna modelo.

“Eu era uma encrenqueira”, disse ela. “Fui basicamente – não exatamente, mas basicamente – expulso do ensino médio.”

Kalai nasceu e cresceu em Tel Aviv, Israel, em uma família acadêmica. Seu pai, Yair Tauman, é economista e teórico dos jogos. Suas aulas do ensino médio a entediavam - um boletim documentava algo como 150 faltas escolares, ela lembra, já que preferia passar o tempo esquiando na água e socializando. Mas suas habilidades analíticas sempre estiveram lá.

“Quando meus pais não me deixavam sair, muitas vezes a única maneira de fazer meu pai concordar era dizer a ele: 'OK, me dê um enigma matemático. O quanto você quiser, mas se eu resolver, eu vou.'” Ela geralmente ia.

Seu amor adormecido pela matemática finalmente despertou na faculdade, quando ela começou a reconhecer sua beleza. Eventualmente, ela descobriu que poderia colocar essa matemática em uso com computadores e, especificamente, proteger informações. Agora, seu trabalho abrange os campos da matemática e da ciência da computação, e suas ideias foram fundamentais para proteger e verificar 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é criptomoedas. Agora pesquisadora da Microsoft e professora adjunta do Instituto de Tecnologia de Massachusetts, ela recentemente ganhou o prestigioso Prêmio ACM em Computação da Association for Computer Machinery por “avanços na delegação verificável de computação e contribuições fundamentais para a criptografia”. Seu trabalho mais recente também olha para o futuro, pois ela considera como os computadores quânticos podem afetar o cenário de segurança.

Quanta conversou com Kalai sobre vazamento de segredos, verificação da nuvem e a diversão da computação quântica. A entrevista foi condensada e editada para maior clareza.

Como você passou de encrenqueiro do ensino médio a acadêmico?

Sempre soube que adorava matemática, mas a matemática do ensino médio não era nada interessante. Então fui estudar matemática na graduação e fiquei maravilhado. É a primeira vez na minha vida que me sento e estudo sem parar, de manhã à noite. Eu estava em euforia. E devo dizer que fiquei um pouco chateado, porque pensei: “Não acredito que poderia ter gostado disso quando era muito mais jovem!”

O que foi sobre a matemática que cativou você?

É muito limpo, elegante e abstrato. E alguns conceitos em matemática são contra-intuitivos; Lembro-me de sentir que estudá-lo estava me mudando como pessoa. Você aprende a ser humilde, porque repetidamente aprende que suas intuições estão erradas.

Mas quando eu estava procurando uma boa pergunta de pesquisa, tudo parecia incremental. Então comecei a me mover para a ciência da computação. E a criptografia era exatamente o que eu estava perdendo, porque lida com problemas do mundo real. Hoje, a criptografia é usada em todos os lugares. Ele é usado para garantir que as mensagens que enviamos sejam confidenciais e autênticas. Quando envio uma mensagem de texto para alguém, como sei que a mensagem que recebi é a mensagem que foi enviada? Como sei que a pessoa que afirma ter enviado a mensagem é quem realmente a enviou? O que significa saber disso? Os conceitos são muito filosóficos e a forma como os modelamos matematicamente é muito bonita. Acertou em cheio para mim, tanto a pureza da matemática quanto a aplicabilidade.

Em que tipo de problemas criptográficos você trabalhou?

Minha tese de mestrado foi intitulada “Como vazar um segredo”. Aqui está o problema: sabemos como assinar digitalmente - para dizer: “Sou eu quem escreveu esta mensagem”. Mas digamos que eu queira assinar algo como professor do MIT, mas não quero que as pessoas saibam que sou eu? Dessa forma, o segredo retém um pouco de água porque você sabe que um professor do MIT o assinou, mas não sabe quem.

Resolvemos isso com algo que chamamos de assinaturas de anel, que foram inspiradas por uma noção da ciência da computação chamada provas indistinguíveis de testemunhas. Digamos que haja uma declaração e duas maneiras diferentes de prová-la. Dizemos que há duas “testemunhas” de que a afirmação está correta — cada uma das provas. Uma prova de testemunha indistinguível parece a mesma, não importa qual você use: ela oculta com qual testemunha você começou.

As assinaturas de anel são semelhantes. No grupo de potenciais vazadores de segredos, você pode pensar em cada pessoa como tendo uma chave secreta. E a assinatura do anel está essencialmente provando que esta mensagem foi assinada por alguém com uma das chaves secretas, mas não revela qual chave secreta eles conhecem. Ele esconde cuja chave secreta foi usada.

Uma instituição realmente usaria esse sistema?

Essa é a coisa bonita e assustadora sobre isso - eu posso fazer isso sem mais ninguém envolvido. Posso assinar como membro 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. Assinaturas de anel foram usadas - há uma criptomoeda chamada monero que diz que a usa para a privacidade das transações. Mas, francamente, não sei quem está usando nosso trabalho. A verdade é que estou muito ocupado para segui-lo.

Como seu trabalho evoluiu para analisar a segurança de nossos dispositivos?

No início dos anos 2000, eu estava terminando meu doutorado, trabalhando com Shafi Goldwasser no MIT. As pessoas começaram a falar sobre computação em nuvem, que agora usamos todos os dias. Antes, você tinha uma área de trabalho enorme onde tudo era feito. Com o aumento da grande coleta de dados, os cálculos ficaram mais caros e passaram a ser feitos remotamente. A ideia é que existe uma nuvem poderosa que faz cálculos para você. Mas você pode não confiar na plataforma de nuvem, então como saber se eles estão fazendo o cálculo corretamente? Às vezes, pode haver um incentivo para trapacear porque o cálculo pode ser muito caro. E então, em algumas configurações, você pode estar preocupado com erros aleatórios. Então você realmente quer uma prova de que esse cálculo está correto.

Mas normalmente as provas são muito longas e os dispositivos fracos não podem verificar provas longas. Mesmo para dispositivos que podem, é muito caro. Então, há uma maneira de encolher as provas? Informação - teoricamente, não. Mas acontece que, usando ferramentas criptográficas, podemos gerar certificados sucintos que são muito, muito difíceis de falsificar. Estes são chamados de argumentos não interativos sucintos, ou SNARGs. Não é uma prova, na verdade. Mas desde que você não consiga resolver algum problema que nós criptógrafos acreditamos ser muito difícil, como fatorar números grandes, então você não pode falsificar as provas sucintas.

Como surgiram essas provas?

Tudo começou em 1985 com Shafi Goldwasser, Silvio Micali e Charles Rackoff, que juntos introduziram uma noção de provas interativas. Antes, quando as pessoas pensavam em provas, pensavam em escrever linhas de dados, e você pode ler e verificar se estão corretas ou não. Goldwasser, Micali e Rackoff introduziram uma forma completamente diferente de provar algo: usando a interação. Há um provador e há um verificador, e eles trocam mensagens. Então o verificador decide se eles estão convencidos ou não.

Deixe-me dar um exemplo de algo que é mais fácil de fazer como uma prova interativa do que uma prova clássica. Suponha que estamos jogando xadrez. Agora suponha que eu queira provar a você que tenho uma estratégia vencedora. Não importa quais movimentos você faça, eu ainda vou vencer. Como posso provar isso para você?

Classicamente, é uma grande prova, porque preciso provar que minha estratégia funciona contra todas as combinações possíveis de movimentos. Mas acontece que, por meio da interação, posso fazer isso de forma muito sucinta. Se você não acredita que tenho uma estratégia vencedora, vamos jogar. Vou te mostrar que vou vencer. Claro, isso por si só não é convincente - só porque posso vencer uma vez contra você não significa que posso vencer qualquer um. Então me dê um grande mestre. Eu vou ganhar contra um grande 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 nota de cem dólares e prove, por meio da interação, que ela realmente vale $ 100. Eu quero ser capaz de transmiti-lo. Eu quero dar para outra pessoa, que dá para outra pessoa. Mas se eu tivesse apenas uma prova interativa, isso não significaria nada; Não posso dá-lo a mais ninguém. Portanto, o bom dos SNARGs é que você pode entregá-los a outra pessoa.

Como um certificado de autenticidade?

Exatamente. Blockchains são o principal lugar que eles são usados ​​hoje, para verificar transações. Quando surgiu o blockchain, eu disse aos meus alunos que devíamos enviar ao desenvolvedor do bitcoin, Satoshi Nakamoto, flores e chocolates, porque ele realmente tornou nosso trabalho tão relevante.

Então, como você remove a interação para criar esses certificados transferíveis?

Com criptografia. Deixe-me tentar dar-lhe uma intuição de como isso funciona. Em nossas provas interativas, o verificador geralmente apenas envia aleatoriedade para o provador - você pode pensar nisso como o verificador verificando aleatoriamente a prova. Então Amos Fiat e Adi Shamir tiveram uma ideia: por que você precisa desse verificador se tudo o que ele faz é enviar aleatoriedade? Talvez possamos substituir esse verificador por alguma função, como algo chamado função hash — é uma função que parece aleatória e é um bloco de construção muito importante na criptografia.

E acontece que sim, podemos. Hoje, isso é feito o tempo todo. Se você tem um iPhone ou um 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 construir as provas sucintas que certificam que as computações remotas estão corretas.

Você falou sobre máquinas que precisam ser “seguras pós-quânticas”. O que isso significa?

Os computadores quânticos, se realmente vierem a existir em grande escala, serão muito mais poderosos do que os computadores clássicos. Computadores clássicos trabalham em bits, que são 0 ou 1. Em computadores quânticos, você tem bits quânticos, que estão em superposição entre 0 e 1. E esses qubits são emaranhados, o que significa que eles se influenciam. Isso é o que realmente dá poder aos computadores quânticos.

No futuro, pode ser que nem todos tenham um desktop quântico. Pode haver alguns dispositivos quânticos caros que fazem cálculos remotos para você. Suponha que você queira delegar uma computação cara a um desses dispositivos quânticos e precise de algum certificado que verifique se a saída está correta - como você certifica a exatidã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 uma inovação resultar por um estudante de Berkeley, Urmila Mahadev. Ela foi a primeira a mostrar uma prova clássica e computacionalmente segura para verificar cálculos quânticos.

Então você pode usar um computador clássico para verificar cálculos quânticos? Isso parece impossível!

Isso não é incrível? Eu estava no comitê do programa quando Urmila publicou seu artigo e passei a noite toda olhando para ele - a quantidade de cafeína que bebi! Eu estava alucinado. Nesse ponto, eu era um boneco quântico completo. Eu entendi a parte criptográfica, mas demorei um pouco para entender como isso combinava com a parte quântica. E foi lindo.

Passar da computação clássica para a quântica soa como uma curva de aprendizado íngreme.

Eu sei. Na verdade, não sei nada sobre física e há muita intuição física quântica envolvida. Não entendo os conceitos mais básicos, como energia e temperatura. Às vezes eu trabalho com alunos e assim que falamos sobre computação quântica, eu me torno o aluno. Estou começando a ganhar um pouco mais de intuição. E devo dizer que estou gostando muito, sentado lá com um livro sobre informação quântica. Não há nada melhor do que ser um estudante.