Além do conhecimento zero: o que vem a seguir na criptografia programável?

Criptografia programável

Embora a criptografia já exista há milhares de anos, a criptografia programável é uma tecnologia moderna. Descrita como “criptografia de uso geral… [ou] uma linguagem expressiva para afirmações”, é a ideia de que uma primitiva criptográfica como uma prova ZK poderia ser flexível e adaptável o suficiente para que um desenvolvedor pudesse programar quase qualquer função sobre ela. Que pode existir uma cadeia ininterrupta de lógica, desde alguém clicar em um botão em um site até a prova matemática que garante a segurança de uma operação criptográfica.

https://youtu.be/qAfprVCBhdQ?t=1024

Enquanto a criptografia tradicional dependia de conjuntos fixos de funcionalidades, o que exigia um criptógrafo qualificado para construir um sistema especializado para cada novo mecanismo, a criptografia programável permite que os desenvolvedores implementem propriedades e funcionalidades criptográficas em uma linguagem mais próxima do que eles já entendem. Oferece aos desenvolvedores que não são especialistas em criptografia uma interface mais familiar.

As provas ZK foram concebidas pela primeira vez em 1989, mas permaneceram principalmente teóricas até 2012, quando um tipo de prova ZK chamada zk-SNARK foi descoberto. Esta nova primitiva permitiu que as provas ZK provassem ou autenticassem quase qualquer função ou cálculo arbitrário.

Desde que o zkSNARKS se tornou possível, recursos e talentos foram investidos na construção do zCash, zkRollups, zkEVMs e uma série de outros aplicativos que começam com a letra z. Descobriu-se que sistemas descentralizados como Ethereum e blockchains em geral eram a motivação perfeita para despertar o interesse das pessoas em criptografia, transformando um campo de pesquisa antes impraticável em um ecossistema ativo com aplicações reais para o usuário final.

Não há garantias de que a Computação Multipartidária (MPC), a Criptografia Totalmente Homomórfica (FHE) e a Ofuscação Indistinguível (iO) seguirão o mesmo caminho que o ZK, tornando-se mais práticos, otimizados e de uso geral com o passar do tempo. Mas nesta fase inicial, é certamente possível.

Se você pensar na criptografia programável como um tipo de computador digital, construído sobre certas suposições que permitem certas propriedades e garantias, então ainda estamos no estágio de hardware. Ainda estamos descobrindo ativamente a melhor maneira de construir portas lógicas ou circuitos para este novo computador.

Comparações relativamente intuitivas

Para entender melhor o cenário geral da criptografia programável, vamos começar aproximando aproximadamente a posição do MPC, FHE e IO em relação ao ZK e entre si. Nesta seção, e em todas as seções seguintes, trocaremos nuances, precisão e formalidade em favor da simplicidade e acessibilidade.

A maneira mais simples de raciocinar sobre criptografia é quais informações são mantidas ocultas ou secretas. E o que o sistema prova ou revela.

Você também pode pensar em cada um desses sistemas como um substituto de um amigo imaginário em comum. A Wikipedia chama esse amigo de “Tony”. Tony é infalível, incorruptível e totalmente confiável. O trabalho de Tony é guardar segredos. Na tabela abaixo, pense nos “Elementos Privados” como os segredos que Tony pode confiar para manter, nos “Casos de Uso” como tarefas que Tony poderia executar razoavelmente bem, e na “Praticidade” como a habilidade com que Tony poderia executar essas tarefas hoje.

As tabelas acima pretendem dar uma ideia aproximada para diferentes áreas da criptografia programável. Agora, vamos nos aprofundar um pouco mais e revisar o que MPC, FHE e iO fazem, juntamente com algumas informações interessantes sobre cada campo.

Computação Multipartidária (MPC)

A computação multipartidária (MPC) permite que muitas partes calculem em conjunto algumas funções acordadas sem revelar quaisquer dados aos outros participantes. Com o MPC, o mesmo cálculo é aplicado aos dados de todos, mas a contribuição de cada parte é mantida em segredo. Os valores intermediários também permaneceriam secretos. Apenas a saída é revelada no final.

Ao contrário do ZK, o MPC é colaborativo. Ele permite que diferentes partes colaborem na mesma computação, cada uma contribuindo com seus próprios dados, para obter algum resultado mútuo que todos desejam.

Podemos comparar ZK e MPC no contexto de um sistema de IA para obter mais contexto. ZK seria bom para autenticar ou verificar dados provenientes de uma pessoa real ou do telefone de uma pessoa. O MPC é melhor para treinar um sistema de IA porque diferentes indivíduos, grupos ou organizações podem compartilhar dados confidenciais com o sistema de IA, mas confiam que os dados não serão revelados a mais ninguém.

Problemas milionários

O MPC foi idealizado em 1982 por Andrew Yao para resolver um experimento mental chamado “O Problema do Milionário”, onde dois milionários querem saber quem é mais rico sem dizer um ao outro quanto dinheiro eles têm. A solução foi usar circuitos distorcidos, que, segundo Vitalik Buterin, frequente explicador de conceitos criptográficos, também é uma das maneiras mais básicas de entender o MPC.

[Antes de aprender sobre um circuito ilegível, você precisa saber o que é um circuito aritmético em geral. Se você é novo na ideia de circuitos, há uma explicação simples aqui.]

MPC é um processo interativo de várias etapas em que a milionária nº 1 (Alice, a Garbler) deve primeiro criar o circuito, inserir seu patrimônio líquido e, em seguida, transformá-lo em um formato distorcido ou criptografado antes de passá-lo para o milionário nº 2 (Bob, o Avaliador). ). Quando Bob coloca as mãos no circuito, seu trabalho é adicionar seu próprio patrimônio líquido e, em seguida, avaliar ou executar o circuito para ter certeza de que está correto. Finalmente, Bob descriptografa o resultado final e, por exemplo, descobre que Alice é mais rica, mas nunca descobre que Alice é, de fato, muito mais rica, e ele não deveria ter feito suposições.

O Problema do Milionário e os circuitos distorcidos como solução foram cruciais para o desenvolvimento inicial do MPC. Mas a sua aplicação foi limitada. Uma versão mais complexa e matizada do problema, chamada Problema do Milionário Socialista, verificava se os dois milionários eram igualmente ricos, em vez de revelar qual deles tinha mais dinheiro. Essa diferença sutil estendeu significativamente a funcionalidade do MPC, mas exigiu soluções e técnicas criptográficas mais complexas, além do escopo deste artigo.

Criptografia Totalmente Homomórfica (FHE)

A criptografia totalmente homomórfica (FHE) permite cálculos em dados criptografados. Ele pode executar uma função em dados criptografados como se permanecessem não criptografados. A saída da função só é descriptografada pela parte com a chave secreta. Se pensarmos na criptografia como uma caixa preta que esconde segredos, então o FHE garante que os dados e os cálculos desses dados permaneçam dentro dessa caixa preta.

Embora não existam experimentos mentais famosos como o Problema do Milionário para MPC, o FHE resolve uma fraqueza fundamental de segurança: “a necessidade de descriptografar antes de processar os dados”.

https://www.zama.ai/post/the-revolution-of-fhe

Num contexto de IA, a FHE manteria todos os dados entre o utilizador (detentor da chave secreta) e o sistema de IA encriptados. O usuário interage com o sistema normalmente, mas pode ter certeza de que a IA nunca “aprendeu” nada sobre os dados fornecidos. Toda a interação seria criptografada. A IA nunca aprende o que você digitou ou perguntou, quais fotos você enviou ou quem as enviou, mas ainda pode responder como se conhecesse a informação.

Se funcionar, o FHE será uma das tecnologias de preservação de privacidade mais poderosas disponíveis. E quem sabe? Em 10 anos, poderemos até ter FHE-EVMs.

Gerenciamento de ruído

Comparado ao MPC e ao ZK, o FHE está – neste momento – no extremo mais teórico ou menos prático do espectro. A tecnologia só foi considerada viável em 2009, quando Craig Gentry descobriu como lidar com o ruído.

As operações FHE são computacionalmente muito intensivas porque “ruído” é adicionado durante o processo de criptografia para aumentar a segurança. O ruído no FHE é um pequeno valor aleatório adicionado ao texto simples (dados não criptografados) antes de ser transformado em texto cifrado (dados criptografados). Cada operação aumenta o ruído. Embora as operações de adição e subtração causem um crescimento de ruído insignificante, a multiplicação é mais cara do ponto de vista computacional, o que resulta em um crescimento de ruído significativo. Assim, à medida que a complexidade de um programa aumenta, o ruído – o espaço necessário para acomodar o ruído e os recursos computacionais necessários para processar o ruído – acumula-se.

A descoberta de Gentry foi uma técnica chamada bootstrapping, que poderia reduzir o ruído e permitir mais computação em dados criptografados em sistemas FHE. Bootstrapping pega o texto cifrado e o descriptografa homomorficamente, o que significa reduzir o nível de ruído em um dado criptografado sem realmente revelar o que é. O resultado é um texto cifrado com ruído predefinido muito menor, permitindo-nos computar ainda mais o texto cifrado. O bootstrapping, em geral, nos permite contornar a necessidade de ter maior espaço para o crescimento do ruído à medida que a complexidade da computação aumenta. Podemos limitar o espaço a algumas operações e inicializar repetidamente para calcular cálculos arbitrariamente grandes sem comprometer os dados originais.

Dependendo do esquema FHE, a inicialização pode levar vários minutos ou milissegundos. Se o bootstrapping for mais lento, o custo computacional pode ser distribuído aplicando-o a vários textos cifrados de uma só vez. Se a inicialização for mais rápida, geralmente terá a desvantagem de trabalhar apenas com pequenos pedaços de texto simples (geralmente 8 bits) por vez para permanecer eficiente.

Ofuscação de indistinguibilidade (iO)

Se o FHE transforma todos os elementos do cálculo em uma caixa preta, então o iO transforma o próprio cálculo em uma caixa preta.

A Ofuscação de Indistinguibilidade (iO) é considerada o sistema criptográfico mais poderoso dentro do reino das possibilidades teóricas. Num artigo, o iO é descrito como uma “ferramenta mestre a partir da qual quase todos os outros protocolos criptográficos poderiam ser construídos” e referido pelos especialistas em criptografia como uma “jóia da coroa” e “um primitivo criptográfico para governar todos eles”.

De acordo com Amit Sahai, o professor conhecido por explicar as provas ZK para crianças, e um dos pesquisadores que desenvolveu uma maneira de construir o iO com base em suposições bem fundamentadas, o iO funciona em um paradigma fundamentalmente diferente dos sistemas criptográficos anteriores. IO assume que o adversário já pode ler sua mente (uma metáfora para o seu computador). Seus segredos já são conhecidos, então não podem ser escondidos. A única coisa que você pode fazer é ofuscar o que o adversário já pode ver.

https://youtu.be/v2RR_c5hn1E

O objetivo de iO é tornar duas funções ou cálculos igualmente obscuros. Se você transformar dois cálculos em um formato indistinguível um do outro, poderá ocultar o funcionamento do programa. Se você não consegue diferenciar dois programas, não sabe qual dos dois programas está sendo executado e nenhuma informação pode ser deduzida de nenhum deles, exceto que ambos executam a mesma função. Ambos os programas recebem as mesmas entradas e produzem as mesmas saídas, mas o iO faz com que ninguém consiga descobrir como.

Com o iO, você pode ocultar a estrutura de cada tipo de função, incluindo quase todas as funções que compõem a criptografia. Em outras palavras, ao ocultar quase tudo, você alcança a criptografia programável de uso mais geral sobre a qual outras primitivas podem ser programadas.

Tecnicamente, existe uma caixa preta maior que o iO. É literalmente chamado de ofuscação de caixa preta. Mas isso ainda é impossível.

Suposições bem fundamentadas

Ninguém sabia como construir o iO até 2013, quando mapas multilineares foram propostos por Garg, Gentry, Halevi, Raykova, Sahai, Waters. Um programa de computador pode ser dividido como peças de um quebra-cabeça e depois obscurecido por meio de mapas multilineares. As peças obscurecidas poderiam ser remontadas para obter a mesma funcionalidade do programa original, sem revelar seu funcionamento interno.

Os mapas multilineares são uma generalização dos mapas bilineares ou pares usados na criptografia de curvas elípticas (ECC). Embora os mapas bilineares sejam fundamentais para esquemas criptográficos existentes, como assinaturas BLS, eles não são complexos ou expressivos o suficiente para iO. E embora os mapas multilineares pudessem lidar com iO, essa estrutura algébrica recém-desenvolvida era facilmente atacável e não era segura, portanto, confiar em mapas multilineares era geralmente insatisfatório para os criptógrafos. O campo ficou preso novamente.

Então, em 2020, Jain, Lin e Sahai propuseram uma solução que, embora incomum e nova, era simples o suficiente para os criptógrafos raciocinarem e, em vez de depender de suposições recentemente desenvolvidas, como mapas multilineares, esta versão do iO poderia ser construída em mais suposições padrão e bem fundamentadas que têm sido estudadas há décadas, como Aprendizagem com Erros (LWE). Com esta última inovação, o iO tornou-se viável novamente. O Santo Graal ainda estava ao nosso alcance.

Região selvagem indomada

Cada sistema criptográfico é feito de diferentes suposições matemáticas e técnicas criptográficas. Nenhuma inovação resolve todos os problemas de um sistema. Em vez disso, as descobertas seguem uma série imprevisível de pequenos passos e grandes saltos que alteram os pressupostos e técnicas existentes, o que por sua vez conduz a mais avanços e descobertas. E para cada descoberta que funcionou, muitas outras não funcionaram.

Numa apresentação no iO, Sahai descreveu o campo como sendo um “deserto selvagem”, onde nem sequer estava claro o que não era compreendido e quais eram os problemas certos a resolver.

Equipes como a PSE trabalham principalmente no lado prático ou aplicado da criptografia programável, concentrando-se em primitivos como ZK e MPC com suposições bem fundamentadas que foram testadas em batalha, relativamente otimizadas e consideradas seguras e eficazes. Embora ainda existam muitas otimizações, o ZK agora está firmemente dentro do reino da praticidade. Mas também houve um tempo em que ZK estava confinado à natureza selvagem.

Para maximizar o número de ferramentas de preservação de privacidade, de garantia de segurança, de verificação de declarações e de criptografia às quais o mundo tem acesso, deveríamos manter, pelo menos, um olho semicerrado em direção ao horizonte do que está por vir, porque ninguém pode prever o que acontecerá. será prático em 10 anos.

A apresentação de Sahai inclui uma citação de um artigo de 2003 da Nature escrito por Steven Weinberg chamado Four Golden Lessons, que destaca outra razão para trabalhar no que é atualmente impraticável.

“Quando eu lecionava no Instituto de Tecnologia de Massachusetts, no final da década de 1960, um aluno me disse que queria estudar a relatividade geral, em vez da área em que eu estava trabalhando, física de partículas elementares, porque os princípios da primeira eram bem conhecidos. , enquanto o último parecia uma bagunça para ele. Ocorreu-me que ele tinha acabado de dar uma razão perfeitamente boa para fazer o oposto… Meu conselho é ir para a bagunça – é aí que está a ação.”

A criptografia programável está sendo explorada por uma variedade de equipes, incluindo PSE e 0xPARC, co-organizadores de um evento de 2 dias chamado Conferência de Criptografia Programável que acontecerá em Istambul, Turquia, nos dias 16 e 17 de novembro de 2023.

Venha dizer olá!

Ou encontre PSE online no Discord.

Isenção de responsabilidade:

1. Este artigo foi reimpresso de [Privacy and Scaling Explorations]. Todos os direitos autorais pertencem ao autor original [kichong]. Se houver objeções a esta reimpressão, entre em contato com a equipe do Gate Learn e eles cuidarão disso imediatamente.
2. Isenção de responsabilidade: As opiniões e pontos de vista expressos neste artigo são exclusivamente do autor e não constituem qualquer conselho de investimento.
3. As traduções do artigo para outros idiomas são feitas pela equipe do Gate Learn. A menos que mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.