ZipPIR: High-throughput Single-server PIR without Client-side Storage

O ZipPIR é um protocolo de Recuperação de Informação Privada (PIR) de alta vazão para servidor único que elimina a necessidade de armazenamento no lado do cliente ao comprimir cifrados LWE em cifrados Paillier durante uma fase offline quase silenciosa, alcançando desempenho comparável aos melhores protocolos existentes sem os custos de comunicação ou armazenamento que os limitam.

O essencial

Imagine que você tem um arquivo gigante de segredos (um banco de dados) e quer pegar apenas uma página específica sem que o dono do arquivo saiba qual página você pegou. Isso é o que chamamos de PIR (Recuperação de Informação Privada).

O problema é que, até agora, fazer isso de forma rápida e segura exigia que você (o cliente) tivesse um computador superpoderoso ou muito espaço de armazenamento, ou que o servidor fosse extremamente lento.

O artigo "ZipPIR" apresenta uma solução brilhante para esse problema. Vamos explicar como funciona usando analogias do dia a dia.

1. O Problema: O "Encomenda Pesada"

Imagine que você quer pedir um livro específico em uma biblioteca gigante, mas não quer que o bibliotecário saiba qual livro é.

• Métodos antigos: Para garantir o sigilo, você tinha que pedir todos os livros de uma vez (muito lento) ou levar uma mala cheia de mapas secretos (muito espaço no seu bolso).
• O desafio: Se o banco de dados muda (novos livros entram), os mapas antigos ficam inúteis e você precisa baixar novos, o que é chato e demorado.

2. A Solução: O "ZipPIR" (O Mágico do Arquivo)

Os autores criaram o ZipPIR. A ideia central é como se eles tivessem encontrado uma maneira de encomendar um livro gigante e receber apenas uma folha de papel de volta, sem que o bibliotecário saiba qual folha você quer.

Eles fazem isso usando uma técnica de "compressão mágica":

A. A Técnica do "Desmonte e Reembalagem"

Normalmente, as mensagens criptografadas (os "segredos") são como caixas de madeira muito grandes e pesadas. Enviar uma caixa dessas pela internet é lento e caro.

• O Truque do ZipPIR: Eles usam uma técnica matemática para "desmontar" essa caixa grande e reembalá-la em um envelope pequeno e leve (como um e-mail comum).
• A Mágica: Eles conseguem fazer isso porque o dono do banco de dados (o servidor) ajuda a "desmontar" a caixa usando uma chave secreta que você já tinha combinado com ele antes. O resultado é que a resposta que chega até você é 99% menor do que antes.

B. A Divisão de Trabalho: "O Trabalho Chato vs. O Trabalho Rápido"

O segredo do ZipPIR é dividir o trabalho em duas fases:

1. Fase Offline (O "Trabalho Chato" no Escuro):

   • Imagine que o servidor é um cozinheiro que trabalha de madrugada, quando ninguém está olhando.
   • Ele prepara tudo o que é difícil e demorado (como descascar legumes e cortar carnes) antes de você fazer o pedido.
   • O grande diferencial: Ele faz isso sem te incomodar. Você não precisa estar online, nem gastar bateria do seu celular. O servidor apenas usa seu tempo livre para preparar os "envelopes prontos".

2. Fase Online (O "Pedido Rápido"):

   • Quando você finalmente quer o livro, você envia um pedido simples (como um bilhete de 2 linhas).
   • O servidor, que já preparou tudo de madrugada, apenas pega o bilhete, coloca a resposta no envelope pequeno e te entrega em milissegundos.
   • Resultado: É super rápido (como se você estivesse baixando 3 Gigabytes de dados por segundo!).

3. Por que isso é revolucionário?

• Sem "Mala de Mapas": Antigamente, você precisava guardar um "mapa" gigante no seu celular para conseguir fazer a busca. Com o ZipPIR, você não precisa guardar nada. Seu celular continua leve e rápido.
• Atualizações Fáceis: Se o banco de dados mudar (novos segredos), o servidor apenas reorganiza a despensa de madrugada. Você nem precisa saber que isso aconteceu. Não precisa baixar nada novo.
• Velocidade de Super-Herói: O sistema é tão rápido que consegue processar gigabytes de dados por segundo, algo que antes só era possível se você tivesse um servidor gigante ou se aceitasse guardar arquivos enormes no seu celular.

Resumo em uma frase

O ZipPIR é como um serviço de entrega que, em vez de te enviar um caminhão inteiro de caixas para você escolher uma, usa uma magia matemática para te entregar apenas o item que você quer, em um envelope minúsculo, preparado silenciosamente pelo entregador enquanto você dormia, sem que você precise ter espaço em casa para guardar nada.

Isso torna a privacidade na internet algo rápido, leve e acessível para qualquer pessoa, mesmo em celulares simples.

Resumo técnico

Resumo Técnico: ZipPIR

1. O Problema

A Recuperação de Informação Privada (PIR) permite que um cliente acesse um elemento de um banco de dados sem revelar ao servidor qual elemento foi consultado. Embora protocolos baseados em Learning With Errors (LWE) e Ring-LWE (RLWE) tenham demonstrado a viabilidade prática da PIR, eles enfrentam um dilema fundamental entre desempenho (throughput) e recursos do cliente:

• Protocolos de Alta Performance (ex: SimplePIR): Oferecem throughput extremamente alto (próximo à largura de banda da memória), mas exigem que o cliente armazene "dicas" (hints) grandes e dependentes do banco de dados (ex: 128 MB). Essas dicas precisam ser atualizadas sempre que o banco de dados muda, o que é impraticável para dispositivos com recursos limitados (como smartphones) e para bancos de dados dinâmicos.
• Protocolos sem Armazenamento no Cliente (ex: XPIR, PIR-with-keys): Não exigem armazenamento no cliente, mas sofrem de baixa throughput (centenas de MB/s) devido ao grande número de operações de chave pública necessárias online.
• Protocolos com Pré-processamento Offline (ex: Piano): Reduzem o trabalho online, mas exigem que o cliente baixe o banco de dados inteiro ou armazene grandes quantidades de dados durante a fase offline, violando as restrições de recursos.

O objetivo é criar um protocolo de PIR de único servidor que seja de alta taxa de transferência, não exija armazenamento no cliente e seja eficiente em bancos de dados dinâmicos.

2. Metodologia e Abordagem Técnica

O ZipPIR resolve esse problema através de uma combinação inovadora de técnicas de criptografia e uma arquitetura de fases offline/online.

A. Compressão de Cifras LWE/RLWE
O núcleo da proposta é uma técnica para comprimir cifras LWE/RLWE (que são grandes) em cifras de um esquema aditivo menor (como Paillier).

• Insight: A etapa de decifração do LWE envolve o cálculo de uma "fase" intermediária ($\mu^*$), que é uma operação linear.
• Mecanismo: O servidor utiliza uma chave de compressão (que é a chave secreta do LWE criptografada sob o esquema aditivo do cliente) para calcular homomorficamente essa fase.
• Resultado: O servidor retorna uma única cifra aditiva pequena (em vez de uma grande cifra LWE) ao cliente. Isso reduz o tamanho da resposta em até 99% (ex: de 6.8 KB para 768 B para uma única cifra).

B. Arquitetura Offline/Online (O "Pulo do Gato")
Operações com esquemas aditivos como Paillier são computacionalmente caras (exponenciação modular). Se feitas online, tornariam o protocolo lento. O ZipPIR contorna isso:

• Fase Offline (Silenciosa): O servidor realiza todas as operações caras de Paillier (multiplicações de matrizes com a chave de compressão) durante tempos ociosos.
  • O servidor gera as "dicas" comprimidas sem interação com o cliente.
  • O cliente apenas envia uma chave pública e uma semente criptográfica uma única vez.
  • Atualizações de Banco de Dados: Como o cliente não armazena estado, o servidor pode reprocessar as dicas offline sem precisar notificar ou interagir com os clientes.
• Fase Online (Leve): Quando a consulta ocorre, o cliente envia apenas o "offset" (a diferença entre a chave real e a parte aleatória pré-computada) e a consulta LWE padrão. O servidor realiza apenas duas multiplicações de matriz (vetor-escalar) sobre inteiros modulares, sem operações de chave pública pesadas.

C. Otimizações Adicionais

• Representação RNS (Residue Number System): Usada para acelerar a multiplicação de matrizes na fase online, permitindo operações nativas de máquina.
• Compressão em Lote (Batched Compression): Várias consultas LWE são comprimidas em uma única cifra aditiva, maximizando o uso do espaço de texto plano do Paillier.

3. Principais Contribuições

1. Primeiro PIR de Alta Performance sem Armazenamento no Cliente: O ZipPIR alcança throughput comparável aos melhores protocolos baseados em LWE (como SimplePIR), mas elimina a necessidade de o cliente armazenar dicas grandes.
2. Eficiência do Paillier: Demonstra que o uso de esquemas aditivos (Paillier), historicamente considerados ineficientes para PIR, pode ser competitivo com esquemas baseados em reticulados (Lattice-based) quando combinados com uma fase offline inteligente.
3. Técnica de Compressão Independente: A técnica de comprimir cifras LWE em cifras aditivas menores é uma contribuição criptográfica que pode ser aplicada em outras áreas além da PIR (ex: inferência privada).
4. Escalabilidade para Bancos Dinâmicos: Ao delegar todo o armazenamento e atualização de estado para o servidor, o protocolo suporta atualizações de banco de dados sem custo de comunicação ou computação adicional para o cliente.

4. Resultados Experimentais

Os autores implementaram o ZipPIR em C++ e realizaram testes comparativos:

• Throughput:
  • Para um banco de dados de 1 GB, o ZipPIR alcança ~3 GB/s (3.5 GB/s para 2 GB).
  • Isso é até 10x mais rápido do que protocolos existentes que não usam armazenamento no cliente (como PIR-with-keys).
  • É comparável ao SimplePIR (que exige 128 MB de armazenamento no cliente), mas sem essa exigência.
• Armazenamento no Servidor:
  • Requer apenas ~120 KB a 170 KB de estado por cliente (para atualizações de dicas), o que é significativamente menor que os megabytes exigidos por outros protocolos de estado.
• Comunicação:
  • Offline: Apenas 400 bytes (chave pública + semente).
  • Online: Tamanho de resposta reduzido drasticamente devido à compressão (ex: ~91 KB para 256 MB de DB, comparado a centenas de KB ou MB em outros protocolos).
• Compressão: A técnica de compressão de cifras LWE alcança reduções de tamanho de 84% a 99%.

5. Significado e Impacto

O ZipPIR representa um avanço significativo na viabilidade prática da PIR em cenários do mundo real:

• Aplicações em Dispositivos Móveis e Navegadores: Ao remover a necessidade de armazenamento local e computação pesada no cliente, o ZipPIR torna a PIR acessível para smartphones e navegadores web.
• Auditoria de Privacidade: É particularmente útil para cenários como auditoria de Signed Certificate Timestamps (SCT) e verificações de credenciais comprometidas, onde os clientes precisam consultar bancos de dados grandes e dinâmicos frequentemente.
• Mudança de Paradigma: O trabalho desafia a noção de que esquemas aditivos são inerentemente lentos para PIR, mostrando que, com a devida separação de fases (offline/online), eles podem superar ou igualar as soluções baseadas em reticulados mais complexas.

Em resumo, o ZipPIR oferece o "melhor dos dois mundos": a velocidade de processamento de massa dos protocolos baseados em LWE com a simplicidade de implantação e baixo custo de recursos dos protocolos sem estado no cliente.