Hidden Elo: Private Matchmaking through Encrypted Rating Systems

1. O Problema

O matchmaking (emparelhamento) é fundamental em aplicações modernas como jogos online, redes sociais e aplicativos de namoro. A maioria dos sistemas utiliza algoritmos de classificação (como o sistema Elo) para emparelhar usuários com níveis de habilidade semelhantes. No entanto, existem duas principais preocupações de privacidade e segurança:

• Vazamento de Dados: Os sistemas tradicionais exigem que o servidor tenha acesso aos dados de classificação (rating) em texto claro, permitindo que o provedor de serviço (ou um adversário que o comprometa) monitore o desempenho exato dos usuários.
• Falta de Transparência e Exploração: Em alguns casos (como no antigo algoritmo do Tinder), os usuários não conhecem sua própria classificação. Além disso, sistemas abertos são suscetíveis a exploração, onde jogadores tentam selecionar oponentes específicos para maximizar ganhos e minimizar perdas ("selective pairing"), distorcendo a integridade do sistema.

O objetivo do trabalho é criar um protocolo de matchmaking que permita atualizações precisas de classificação e emparelhamento justo, mantendo os valores exatos de classificação privados e seguros, mesmo contra o provedor de serviços.

2. Metodologia (H-Elo)

Os autores propõem o H-Elo (Hidden Elo), um protocolo baseado em Criptografia Homomórfica Total (FHE) e Provas de Conhecimento Zero (ZKPs). O sistema utiliza o esquema CKKS-RNS (Cheon-Kim-Kim-Song com Sistema de Números Residuais), que permite operações aritméticas em números aproximados (reais), essencial para o cálculo de Elo.

O protocolo envolve três entidades:

1. Provedor de Serviço (SP): Gerencia o emparelhamento e executa os cálculos de atualização de classificação de forma cega (sobre dados criptografados).
2. Clientes (U): Usuários que possuem seus dados de classificação criptografados localmente.
3. Curador de Chaves Confiável (KC): Uma entidade (que pode operar em um Ambiente de Execução Confiável - TEE) que gera chaves e atesta a integridade das atualizações, mas não participa do cálculo diário do matchmaking.

Fluxo do Protocolo:

• Registro: O usuário envia sua classificação inicial criptografada e uma prova de ZKP (NIZK) que comprova que a classificação está dentro de um intervalo válido para o seu rank, sem revelar o valor exato.
• Atualização de Classificação: Após $N$ partidas, o SP calcula a nova classificação homomorficamente usando a fórmula de Elo ($R' = R + K \cdot (S_{real} - S_{exp})$) sobre os dados criptografados. O SP não vê os valores reais.
• Divulgação e Verificação: O KC descriptografa o resultado para o usuário. O usuário gera uma nova prova de ZKP que vincula a nova classificação criptografada à sua classificação em texto claro (atualmente conhecida apenas por ele) e ao compromisso (commitment) anterior, garantindo que o SP não manipulou os dados.

Primitivas Criptográficas:

• FHE (CKKS): Para cálculos seguros sobre dados criptografados.
• NIZK (Non-Interactive Zero-Knowledge): Para provar que a classificação está dentro de um intervalo válido e que o compromisso e o texto cifrado são consistentes (sem revelar o valor).
• Assinaturas Digitais: Usadas pelo KC para atestar a integridade das atualizações.

3. Principais Contribuições

1. Primeiro Protocolo de Matchmaking Baseado em Classificação Privada: O H-Elo é uma das primeiras implementações que utiliza FHE para permitir atualizações de rating cegas, garantindo que o usuário conheça sua classificação real sem expô-la ao servidor.
2. Segurança Pós-Quântica: Ao utilizar esquemas baseados em retículos (Lattice-based cryptography) via CKKS, o sistema oferece segurança contra ataques de computadores quânticos, diferentemente de soluções baseadas em curvas elípticas ou emparelhamento bilinear (BDH).
3. Análise de Segurança Formal: Os autores definem e provam dois conceitos de segurança:
   • Matchmaking Justo em N Rodadas: Garante que as classificações sejam atualizadas corretamente e que os usuários sejam emparelhados com oponentes de rank equivalente.
   • Elo Oculto (Hidden Elo): Garante que o provedor de serviço não aprenda mais sobre o valor exato do Elo do que o que é inferido pela validade da prova de intervalo.
4. Comparação Sistemática: O trabalho compara o H-Elo com a Matchmaking Encryption (ME), destacando as vantagens em termos de segurança e redução de pressupostos de confiança, apesar do custo computacional maior.

4. Resultados e Avaliação

Os autores implementaram o H-Elo usando a biblioteca OpenFHE e realizaram testes em um cenário de xadrez com 3 oponentes por atualização ($n=3$).

• Desempenho (Runtime):

  • A atualização completa de classificação (incluindo bootstrapping para limpar o ruído) leva aproximadamente 23,25 segundos no nível de segurança de 128 bits.
  • A geração de chaves é custosa (cerca de 4,87 segundos para 128 bits), mas é uma operação única por registro.
  • Sem o bootstrapping, a atualização leva cerca de 7,46 segundos.
  • O sistema não é adequado para aplicações que exigem latência instantânea (como jogos em tempo real), mas é viável para sistemas de reputação de mercado ou torneios onde as classificações são atualizadas após o evento.

• Precisão:

  • O esquema CKKS é aproximado, introduzindo ruído. No entanto, após 10.000 atualizações consecutivas, a diferença média entre o cálculo em texto claro e o criptografado foi de apenas $5,569 \times 10^{-4}$.
  • Isso demonstra que o ruído acumulado é insignificante para a justiça do matchmaking.

• Memória:

  • O maior custo de memória vem da geração e armazenamento da chave de bootstrapping (aproximadamente 7,5 GB para 128 bits). Isso é gerenciável em servidores modernos, mas requer estratégias de gerenciamento de chaves para grandes bases de usuários.

• Comparação com Matchmaking Encryption (ME):

  • O H-Elo é significativamente mais lento que o ME (baseado em BDH). No entanto, o H-Elo oferece segurança pós-quântica e reduz a confiança necessária no provedor de serviço (o SP não precisa conhecer as políticas ou atributos dos usuários, apenas processar dados criptografados).

5. Significado e Conclusão

O trabalho H-Elo representa um avanço significativo na privacidade de sistemas de emparelhamento. Ele resolve o dilema de como manter a transparência para o usuário (saber sua classificação) enquanto protege essa informação contra o provedor de serviço e adversários.

Embora a sobrecarga computacional atual do FHE impeça sua adoção em jogos de alta frequência (como shooter em tempo real), o protocolo é altamente relevante para:

• Sistemas de reputação em mercados online (e-commerce).
• Torneios de e-sports e esportes tradicionais.
• Aplicativos de networking profissional onde a precisão da classificação é vital, mas a privacidade dos dados é prioritária.

O artigo estabelece as bases para futuras pesquisas em sistemas de classificação privados, sugerindo expansões para outros sistemas (como Glicko) e arquiteturas descentralizadas.