- Combina Criptografia Homomórfica (Homomorphic Encryption) e CRDTs para manter a segurança de documentos colaborativos em software local-first
- Só a criptografia de ponta a ponta não permite que o servidor mescle os dados, o que impõe limitações à sincronização e à eficiência das atualizações
- A criptografia homomórfica é uma tecnologia que permite a execução de programas para que o servidor mescle atualizações de CRDT sem conhecer o conteúdo
- Porém, devido às limitações fundamentais da criptografia homomórfica (queda de desempenho, aumento de espaço e volume computacional, necessidade de comportamento de pior caso no código), há grandes dificuldades para aplicação prática
- Estão sendo pesquisadas várias abordagens para a coexistência entre CRDTs e computação segura, e ainda se busca uma solução completa
Local-first e o desafio da colaboração segura
- Na colaboração remota, a estrutura consiste em armazenar o documento como CRDT de forma local-first e, por meio da sincronização, oferecer uma experiência de edição colaborativa
- Quando há exigências de segurança em que o conteúdo do documento jamais pode ser exposto a terceiros, como desenvolvedores do app, a criptografia de ponta a ponta é um método frequentemente usado
- A criptografia de ponta a ponta tem funcionamento simples, mas como o servidor de sincronização não consegue mesclar os dados, trabalhar de forma assíncrona por longos períodos gera comunicação de dados ineficiente
O que é criptografia homomórfica?
- Criptografia homomórfica é um tipo especial de criptografia que permite executar algoritmos diretamente sobre dados criptografados
- Com isso, o servidor de sincronização pode realizar a mesclagem de atualizações de CRDT sem conhecer o conteúdo dos dados
- De acordo com os tipos de operação suportados pela criptografia homomórfica, ela é classificada em parcialmente homomórfica (apenas adição ou multiplicação), um pouco homomórfica/homomórfica em níveis (algumas vezes de ambos os lados) e totalmente homomórfica (sem restrições)
- Quanto mais operações são executadas, mais ruído se acumula no texto cifrado e mais difícil fica a decodificação, exigindo técnicas avançadas como bootstrapping
- No nível de bits criptografados (0/1), é possível implementar circuitos booleanos gerais apenas combinando portas lógicas básicas como XOR e AND
Exemplo real de implementação de CRDT com criptografia homomórfica
- Com a biblioteca TFHE-rs, baseada em Rust, foi implementado com criptografia homomórfica um CRDT representativo chamado Last Write Wins Register
- Os campos e métodos (criptografia/descriptografia) da struct em texto plano e da struct criptografada são quase idênticos, mas surge uma diferença importante na lógica real de mesclagem
- Como ramificações de caminho de execução como
if/else e match podem dar pistas para a decodificação do texto cifrado, no ambiente criptografado é essencial avaliar todas as ramificações e loops imediatamente
- As principais comparações condicionais e operações de mesclagem são tratadas com operadores bit a bit de FheBool e métodos como
select, tornando impossível para agentes externos detectar em que condição o valor mudou
Limitações fundamentais da criptografia homomórfica
- Desequilíbrio entre chave criptográfica e tamanho dos dados: no exemplo, para 32 bytes de dados são necessários 123 MB de chave de servidor (27 MB mesmo com compressão), o que torna a ineficiência de espaço severa
- Queda de desempenho: o merge de um CRDT com criptografia homomórfica foi medido em cerca de 1 segundo, aproximadamente 2 bilhões de vezes mais lento do que sem criptografia
- Se loops e ramificações variarem conforme os valores de entrada, ocorre vazamento de informação; por isso, é preciso sempre consumir operações e memória com base no pior caso
- Por exemplo, mesmo quando pares chave-valor são esparsos em algo como um last-write-wins map, ainda é necessário mesclar todas as chaves totalmente preenchidas em tamanho fixo, o que reduz a escalabilidade prática
- A estrutura do texto cifrado e o histórico de alterações devem ser projetados para que um observador externo não consiga inferir se um valor mudou nem qual parte foi atualizada
Conclusão e perspectivas
- CRDTs e criptografia homomórfica podem ser combinados de forma natural em teoria, mas na prática há restrições graves de eficiência de espaço/tempo e de estrutura do programa
- Até o momento, ainda não surgiu uma solução prática completa, mas os próprios CRDTs também são uma tecnologia relativamente nova e seguem em pesquisa contínua
- Ainda existe potencial para soluções inovadoras que equilibrem segurança e usabilidade em apps colaborativos local-first
1 comentários
Comentários do Hacker News
É verdade que a área de criptografia totalmente homomórfica é realmente lenta e ineficiente, mas vale mencionar que esse campo em si é relativamente novo, tendo surgido em 2009; o avanço nesses últimos 15 anos foi realmente impressionante. Os primeiros esquemas de criptografia homomórfica exigiam chaves na faixa de vários TB/PB, e o bootstrapping (uma operação essencial na criptografia homomórfica quando há muitas operações de multiplicação) levava milhares de horas. Agora, as chaves têm cerca de 30 MB, e o bootstrapping pode ser feito em menos de 0,1 segundo. Espero que continue evoluindo e que um dia se torne prático de usar.
Os CRDTs iniciais (CRDT: Conflict-free Replicated Data Type) também eram extremamente pouco práticos, como o WOOT, mas os bancos de dados CRDT mais modernos de hoje têm desempenho não tão distante de um LSM comum. Por exemplo, os CRDTs RDX funcionam com algoritmos parecidos com merge sort, então tudo é O(N). Na maioria das implementações, o overhead de metadados também é bem controlado. Veja WOOT, librdx, go-rdx.
Pela própria característica arquitetural dos CRDTs, eles inevitavelmente tendem a ser lentos, e até os melhores algoritmos têm um custo estrutural alto. Somando a isso a criptografia homomórfica, o nível de dificuldade sobe muito. É realmente impressionante, mas fico me perguntando se isso é de fato utilizável na prática. Como base para essa alegação, cita-se a explicação: "para o servidor calcular o novo mapa, ele precisa fazer merge de todas as chaves uma a uma e depois enviar o mapa inteiro para cada peer — porque, do ponto de vista do servidor, o mapa inteiro é diferente toda vez".
CRDT significa Conflict-free Replicated Data Type, um tipo especial de dado que permite sincronização distribuída sem conflitos. Veja o artigo da Wikipedia sobre CRDT.
O artigo menciona a falta de desempenho, e na prática, em um M4 MacBook Pro, ao rodar normalmente um registrador last write wins, o merge leva 0,52 nanossegundo, enquanto a versão com criptografia homomórfica leva 1,06 segundo. Ou seja, a velocidade de operação difere em 2 bilhões de vezes. É um número realmente chocante.
FHE (Full Homomorphic Encryption) é realmente muito lenta, mas houve avanços impressionantes desde 2009. Só a velocidade de bootstrapping já melhorou em dezenas de milhões de vezes. Com tfhe-rs, já demonstraram até AES-128 baseada em criptografia homomórfica. Acho que a possibilidade de adoção de FHE em tempo real para inferência/treinamento de IA está se tornando cada vez mais real. Veja o repositório tfhe-aes-128 no GitHub.
Não concordo com a ideia de que o servidor não consegue mais entender as alterações do cliente. O servidor envia apenas as mudanças que o usuário ainda não viu, e o usuário as descriptografa e faz o merge para produzir a versão mais recente do documento. A criptografia homomórfica é interessante, mas quase nunca é adequada em situações que exigem desempenho ou largura de banda razoáveis. Já vi um artigo sobre computação totalmente confidencial baseada em criptografia homomórfica (codificando uma CPU+RAM customizada como cifra e processando uma instrução a cada sinal de clock); funciona de verdade, mas em um nível de apenas 1 instrução de CPU virtual por segundo. Se uma velocidade e um custo desses são aceitáveis, é mais sensato simplesmente rodar localmente, ou, se você for realmente rico, comprar o hardware e processar tudo localmente.
Artigos de ciência da computação e criptografia muitas vezes trazem pesquisas bem distantes da praticidade, como reduzir a complexidade de um ataque de 2^250 para 2^230, algo absurdamente irrealista. Ainda assim, esse tipo de pesquisa tem valor para P&D real e para ampliar o que é possível.
Se o servidor não puder lidar diretamente com o conteúdo, ele não conseguirá mesclar o documento CRDT e terá que receber e reenviar o estado completo do CRDT toda vez. Se o seu amigo estiver online ao mesmo tempo, dá para enviar as operações e fazer merge em tempo real, mas, caso contrário, isso é muito ineficiente.
Fico em dúvida se seria confiável fazer os alunos executarem localmente em seus Chromebooks, com a combinação de JupyterLite e ottergrader, um código de correção em WASM ou JS criptografado com FHE. Também tenho curiosidade sobre a relação entre assinatura de código e o screensaver do SETI@home.
É melhor não usar o THFE-rs, porque o pessoal da Zama exige licença comercial para qualquer coisa além de protótipo, e os termos de licença são incômodos. Em vez disso, recomendo as bibliotecas openFHE (C++) e lattigo (golang), ambas livres para uso comercial.
Acho que FHE é, por natureza, a ferramenta errada para este caso. FHE é adequada para lidar com dados que pertencem ao servidor central ou que ele conhece. Aqui, vários usuários precisam processar conjuntamente dados distribuídos, então MPC (computação multipartidária: quando vários participantes realizam operações em conjunto, como somar seus dados secretos) é muito mais eficiente.
Não entendo muito bem a premissa apresentada no artigo. Eu conheço os conceitos de CRDT e criptografia homomórfica, mas me pergunto por que, para sincronizar, os dois lados precisariam estar online ao mesmo tempo. Em um modelo assíncrono de "store-and-forward", as atualizações poderiam ser trocadas de forma assíncrona, com os dados em trânsito permanecendo criptografados. Então por que o servidor precisaria manter estado (e ainda por cima em estado criptografado), e por que precisaria ser modificado como foi proposto?
É curioso ver a lentidão e a ineficiência do FHE combinadas com o desperdício de espaço de armazenamento dos CRDTs.