Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification

Resumo Técnico: Search-Bound Proximity Proofs (SBPP)

1. Problema: A Lacuna de Proveniência de Autorização

O artigo identifica um problema crítico em sistemas de conteúdo geográfico (LBS) que combinam busca geográfica criptografada com provas de proximidade de conhecimento zero (ZKP). Atualmente, essas duas fases são tratadas de forma independente:

1. Descoberta: O cliente busca conteúdo próximo usando tokens de busca criptografados (ex: GridSE).
2. Verificação: O cliente gera uma prova ZKP (ex: Groth16) para provar que está perto de um local específico sem revelar suas coordenadas exatas.

A Lacuna: Existe uma "lacuna de proveniência de autorização". Uma vez que o estado da sessão no servidor é descartado (para privacidade ou eficiência), não há nenhum mecanismo forense capaz de vincular criptograficamente uma prova ZKP específica à sessão de busca que a autorizou.

• Vulnerabilidade: Um adversário pode interceptar uma prova válida gerada na Sessão A e reassociá-la à Sessão B (mesmo que os parâmetros do conteúdo sejam idênticos). Isso permite a criação de registros de auditoria falsos, onde o acesso é atribuído incorretamente a uma sessão diferente, violando a responsabilidade forense em sistemas que exigem conformidade (ex: controle de acesso geofenceado).

2. Metodologia e Proposta (SBPP)

Os autores propõem o Search-Bound Proximity Proofs (SBPP), um protocolo que une a fase de descoberta à fase de verificação sem modificar o circuito ZKP existente.

Mecanismo Central:
O SBPP introduz um compromisso (commitment) dos dados de autorização diretamente nas entradas públicas da prova ZKP. Isso é feito através de um digest de desafio (challenge digest) que inclui:

1. Nonce da Sessão (N): Um valor aleatório único gerado pelo servidor para cada sessão de busca.
2. Raiz Merkle do Conjunto de Resultados (root(R)): Uma hash que representa o conjunto de itens encontrados na busca.
3. Recibo Assinado (ρ): Um sinal digital do servidor que atesta a validade da sessão e do conjunto de resultados.

Fluxo do Protocolo:

1. O servidor gera uma sessão com um nonce (N) e retorna tokens de busca criptografados.
2. O servidor constrói uma árvore Merkle sobre os resultados da busca e armazena apenas a raiz (root).
3. O cliente seleciona um item para desbloquear e calcula o digest de desafio: H(SBPP-v1, ID_Item, N, root, ...).
4. Este digest é inserido como uma entrada pública no circuito ZKP.
5. O servidor verifica se o digest na prova corresponde ao nonce e root armazenados na sessão.

Modos de Operação:

• Core SBPP: Vincula a prova à sessão (nonce), mas verifica a pertinência ao conjunto de resultados online (o servidor mantém o conjunto completo).
• Full SBPP: Vincula a prova ao conjunto de resultados específico via raiz Merkle, permitindo auditoria offline (o servidor não precisa manter o conjunto de resultados, apenas a raiz).

3. Principais Contribuições

• Definição de SAP (Search-Authorized Proof): Os autores formalizam a noção de segurança SAP, definindo três propriedades essenciais:
  • P1 (Vinculação de Autorização): Uma prova válida para uma sessão não pode ser aceita em outra.
  • P2 (Corretude do Conjunto de Resultados): Uma prova não pode ser aceita para um item que não estava no conjunto de resultados autorizado.
  • P3 (Proveniência de Auditoria): Um auditor externo deve poder verificar, sem estado de sessão ao vivo, que a prova foi gerada a partir de uma autorização específica.
• Ataque de Reassociação de Auditoria: Demonstram que mecanismos de autorização externos à prova (como tokens assinados separados ou MACs) são vulneráveis a ataques de reassociação quando parâmetros de conteúdo se repetem entre sessões.
• Decomposição Prática (SBPP): Apresentam uma implementação que isola falhas em nível de propriedade. Diferente de soluções que usam um hash opaco de um token (V8), o SBPP decompõe a informação em componentes auditáveis independentes (nonce, raiz Merkle, assinatura), permitindo diagnosticar exatamente onde uma auditoria falhou (ex: falha de assinatura vs. falha de pertinência).
• Compatibilidade: A solução não requer modificações no circuito ZKP (mantém as 474 restrições do Groth16) nem em chaves de verificação.

4. Resultados Experimentais

Os autores avaliaram o SBPP usando dados sintéticos e reais (110.776 POIs do OpenStreetMap em Tóquio) e compararam nove variantes de protocolos.

• Segurança:
  • O SBPP (Full) bloqueia 100% dos ataques de reassociação (A2) e de escape de conjunto de resultados em auditoria (A4b), enquanto soluções "proof-external" (como tokens assinados separados) falham nesses cenários.
  • A prova de vinculação é robusta contra tentativas de reatribuição de prova entre sessões diferentes.
• Desempenho:
  • Sobrecarga de Protocolo: O SBPP adiciona apenas 27 µs (mediana) ao tempo de processamento do protocolo (aprox. 7% de overhead sobre a busca GridSE).
  • Latência Total: A geração da prova ZKP (que é a parte mais pesada, 42-125 ms em dispositivos móveis) permanece inalterada. O overhead total do SBPP sobre a linha de base é inferior a 0,03%.
  • Escalabilidade: O modo "Compacto" (Full SBPP) mantém o estado do servidor em O(1) (apenas a raiz Merkle), independentemente do tamanho do conjunto de resultados, permitindo auditoria eficiente mesmo após o descarte do estado da sessão.
• Auditoria Offline: Em testes de auditoria pós-fato (sem estado de sessão), o SBPP Full permitiu a re-verificação completa de 100% das sessões, enquanto o modo Core falhou, confirmando a necessidade da raiz Merkle para auditoria forense.

5. Significado e Impacto

Este trabalho é fundamental para a segurança e conformidade de sistemas de localização baseados em criptografia.

• Responsabilidade Forense: Resolve o dilema de como auditar acessos em sistemas que priorizam a privacidade (descartando estado de sessão). O SBPP garante que cada prova de acesso possa ser rastreada até sua autorização original de forma criptograficamente verificável.
• Separação de Preocupações: Demonstra que a vinculação de autorização não precisa ser feita apenas no nível da aplicação ou via tokens externos, mas deve ser internalizada na prova criptográfica para ser segura.
• Viabilidade de Implantação: Ao não exigir modificações no circuito ZKP e manter um overhead de latência insignificante, o SBPP torna-se uma solução prática para adoção imediata em plataformas de realidade aumentada, mídia bloqueada por localização e controle de acesso geofenceado.

Em resumo, o SBPP preenche a lacuna entre a busca criptografada e a verificação de proximidade, garantindo que a "prova de estar lá" seja indissociável da "autorização para buscar lá", mesmo na ausência de registros de sessão ao vivo.