Resumo Técnico: PIVOT – Funções Pseudorandomas Oblíquas de Limiar Proativas e Verificáveis a partir de Ações de Grupos de Isogenia

1. Definição do Problema

Funções Pseudorandomas Oblíquas (OPRFs) permitem que um cliente avalie uma função chaveada sobre uma entrada privada sem revelar a entrada ao servidor. Em uma OPRF de limiar (threshold OPRF), a chave secreta é distribuída entre $n$ servidores, exigindo que pelo menos $t$ servidores cooperem para a avaliação. Enquanto os esquemas de limiar padrão protegem contra corrupção estática (onde um conjunto fixo de servidores é comprometido), eles falham contra um adversário móvel. Em um modelo de ameaça móvel, um atacante pode comprometer diferentes servidores ao longo do tempo, acumulando partes (shares) de diferentes épocas. Se as partes permanecerem estáticas, o adversário poderá eventualmente coletar $t$ partes do mesmo estado de compartilhamento e reconstruir a chave mestra, mesmo que nunca controle $t$ servidores simultaneamente.

As OPRFs baseadas em isogenia existentes são projetadas primariamente para modelos de corrupção estática. Além disso, os mecanismos de compartilhamento de segredo proativo existentes em grupos clássicos não se traduzem facilmente para o cenário de isogenia devido à necessidade de vincular compromissos polinomiais (no campo escalar) com ações de grupos de isogenia (em curvas elípticas). Há uma carência de uma construção que ofereça simultaneamente:

1. Segurança pós-quântica (baseada em isogenias).
2. Verificabilidade (garantindo que os servidores avaliem sob a chave correta).
3. Segurança proativa (atualizando periodicamente as partes para frustrar adversários móveis).
4. Geração de chave sem dealer (dealerless) (sem configuração de confiança/trusted setup).
5. Migração de comitê (alterando o conjunto de servidores ou o limiar sem re-criptografar os dados da aplicação).

2. Metodologia e Construção

O artigo introduz o PIVOT (Proactive Isogeny-based Verifiable Oblivious Threshold PRF), um framework construído sobre ações de grupos de isogenia eficazes (ex: CSIDH). A estrutura algébrica central baseia-se na propriedade comutativa das ações de isogenia: $[a]([b]E) = [a+b]E$.

Arquitetura Central

O PIVOT mantém uma única chave mestra de longa duração $k$ e uma chave pública $pk = [k]E_0$. No entanto, a representação de $k$ muda ao longo do tempo. O sistema opera em épocas. Na época $e$, os servidores detêm partes $s^{(e)}_i = F_e(i)$ de um polinômio de Shamir $F_e(X)$, onde $F_e(0) = k$. O vetor de compromisso do coeficiente público $A^{(e)}$ certifica o polinômio $F_e$.

O protocolo consiste em cinco procedimentos principais:

1. Geração de Chave Distribuída Sem Dealer (DKG):

   • Cada servidor atua como um dealer de Compartilhamento de Segredo Verificável (VSS), amostrando um polinômio aleatório e distribuindo as partes.
   • Contribuições qualificadas são agregadas para formar o polinômio mestre inicial $F_0(X) = \sum f_j(X)$.
   • Provas de Vínculo (Link Proofs): Uma inovação crítica é o uso de provas de Conhecimento Zero Não Interativas (NIZK) para vincular o termo constante do polinômio comprometido (a parte escalar) ao expoente usado na cadeia de ação de isogenia sequencial que gera a chave pública $pk$. Isso garante que a chave pública corresponda ao segredo compartilhado sem reconstruir $k$.

2. Avaliação de Limiar (Threshold Evaluation):

   • O cliente ofusca sua entrada $x$ mapeando-a para uma curva $X = H_1(ctx \| x)$ e aplicando uma ação aleatória $[r]$, enviando $B = [r]X$.
   • Um quórum de $t$ servidores aplica suas partes ponderadas por Lagrange sequencialmente: $Q_h = [\lambda^I_{i_h} s^{(e)}_{i_h}] Q_{h-1}$.
   • Devido à propriedade aditiva da ação, a curva final é $Q_t = [k]B$.
   • O cliente desofusca para obter $Y = [k]X$ e deriva a saída.
   • Verificação: Cada servidor fornece uma prova NIZK ($\pi_{eval}$) certificando que a ação realizada corresponde à parte comprometida no vetor público $A^{(e)}$ da época atual.

3. Atualização Proativa de Partes (Proactive Share Refresh):

   • Para combater adversários móveis, os servidores atualizam as partes periodicamente sem alterar $k$.
   • "Dealers de atualização" qualificados amostram polinômios de zero-compartilhamento $z_j(X)$ onde $z_j(0)=0$.
   • O novo polinômio é $F_{e+1}(X) = F_e(X) + \sum z_j(X)$. Como os termos constantes somam zero, $F_{e+1}(0) = k$.
   • Os compromissos dos coeficientes são atualizados de forma homomórfica. As partes antigas são apagadas de forma segura após a transição.

4. Verificação, Culpa (Blame) e Reinício Robusto:

   • Se um servidor submeter uma prova ou parte malformada, a parte detectora gera um certificado de culpa (um registro assinado da falha).
   • O servidor culpado é removido e o protocolo reinicia com um novo quórum. Isso garante abortos identificáveis.

5. Recompartilhamento de Comitê (Committee Resharing):

   • Permite a migração para um novo conjunto de servidores ou um novo limiar $t'$.
   • Um quórum antigo trata suas partes ponderadas por Lagrange como termos constantes para novos polinômios distribuídos ao novo comitê.
   • Crucialmente, isso transfere o segredo $k$ sem reconstruí-lo, preservando a chave pública e todas as saídas de OPRF geradas anteriormente.

Desafios Técnicos Abordados

• Consistência de Testemunha entre Domínios (Cross-Domain Witness Consistency): O artigo formaliza a necessidade de relações NP conjuntas (ex: $R_{link}, R_{eval}$) que vinculem um escalar comprometido no campo ao mesmo escalar usado na ação de isogenia. Provar isso separadamente é insuficiente; a testemunha deve ser idêntica entre os domínios.
• Consistência de Época: O protocolo impõe que as cadeias de avaliação devem usar partes de um certificado de época único para evitar a mistura de partes de diferentes polinômios.

3. Principais Contribuições

1. Funcionalidade Formal: Os autores definem uma funcionalidade ideal $\mathcal{F}_{pTVOPRF}$ para uma VOPRF de limiar proativa de longa duração, modelando explicitamente adversários móveis que podem alterar o conjunto de servidores corrompidos entre as épocas.
2. Construção Sem Dealer: Uma construção que combina ações de grupos de isogenia eficazes com compartilhamento de segredo de Shamir e compromissos aditivamente homomórficos, onde a chave mestra nunca é reconstruída por nenhuma parte individual.
3. Manutenção Proativa: Um mecanismo para renovar as partes dos servidores contra adversários móveis enquanto preserva a chave mestra, a chave pública e todas as saídas históricas de OPRF. Isso inclui um protocolo coordenado de transição de época.
4. Relações NP Conjuntas: A identificação e formalização de relações NIZK específicas necessárias para vincular o domínio do compartilhamento de segredo (coeficientes polinomiais) ao domínio da ação de isogenia (transformações de curva).
5. Recompartilhamento de Comitê: Um protocolo para migrar o segredo para um novo comitê ou alterar o limiar sem invalidar as bases de dados criptografadas anteriormente indexadas por saídas de OPRF.
6. Análise de Segurança: A construção é provada segura no modelo de oráculo aleatório sob as suposições de vetorização e uma-mais-ação-de-grupo-oculta (one-more hidden-group-action), provando a privacidade da entrada e o segredo da chave contra adversários semi-honestos móveis.

4. Resultados e Desempenho

• Corretude: O artigo prova que o protocolo mantém o invariante de que a chave mestra $k$ e a chave pública $pk$ permanecem constantes através de DKG, avaliação, atualização e recompartilhamento.
• Segurança: A construção é provada segura contra um adversário semi-honesto móvel que corrompe menos de $t$ servidores em qualquer época individual. A segurança baseia-se no apagamento seguro das partes antigas e na privacidade de informação teórica do compartilhamento de Shamir.
• Compromissos de Eficiência (Trade-offs):
  • Tamanho do Registro (Transcript Size): Ao contrário das abordagens de servidor virtual baseadas em MPC que oferecem registros de cliente de tamanho constante, o PIVOT possui um registro de cliente de $O(t)$ porque expõe a cadeia sequencial de $t$ avaliações parciais e provas.
  • Latência: A avaliação requer $t$ ações de grupo e provas sequenciais, criando um gargalo de latência linear em relação ao limiar.
  • Manutenção: A atualização proativa e o recompartilhamento de comitê envolvem comunicação $O(n^2)$ (devido à distribuição de partes ponto a ponto), mas não requerem ações de isogenia, tornando-os adequados para amortização ao longo de longos períodos.
  • Aplicações: O artigo destaca que, embora o custo online seja maior, a capacidade de atualizar as partes e migrar comitês sem re-criptografar grandes bases de dados (ex: serviços de busca privada) oferece eficiência operacional significativa para serviços de longa duração.

5. Significância e Alegações

O artigo afirma apresentar a primeira VOPRF de limiar a partir de ações de grupos de isogenia que fornece segurança proativa contra um adversário móvel.

Os autores posicionam o PIVOT não como uma otimização de desempenho sobre as OPRFs existentes de servidor único ou baseadas em MPC, mas como um framework completo de funcionalidades para serviços de longa duração. A significância reside na escolha arquitetônica de expor explicitamente a estrutura de limiar em vez de escondê-la atrás de um servidor virtual. Essa explicitação permite:

• Aplicação direta de atualização proativa (adição de polinômios de zero-compartilhamento).
• Responsabilidade individual (atribuição de culpa).
• Migração contínua de comitê sem reconstrução de chave.

O artigo conclui que para serviços que exigem longevidade operacional de anos na presença de comprometimento gradual, o custo de um registro de $O(t)$ é uma troca necessária pela capacidade de renovar periodicamente o estado de segurança do sistema sem interromper o serviço criptográfico subjacente ou re-criptografar os dados dependentes.