Information-Theoretic Distributed Point Functions with Shorter Keys

1. Declaração do Problema

O artigo aborda a construção de Funções de Pontos Distribuídas Teoricamente Informacionais (ITDPFs).

• Definição: Uma ITDPF $(t, n)$ permite que uma função de ponto $f_{\alpha, \beta}(x)$ (que produz $\beta$ na entrada $\alpha$ e $0$ em qualquer outro lugar) seja dividida em $n$ chaves secretas. Qualquer subconjunto de $\le t$ servidores não aprende absolutamente nada sobre a função (segurança perfeita), enquanto a soma das avaliações de todos os $n$ servidores reconstitui o valor da função.
• O Desafio: A métrica primária para eficiência em DPFs é o tamanho da chave (o tamanho máximo das chaves secretas). As ITDPFs perfeitamente seguras existentes para o grupo de saída $G = \mathbb{Z}_p$ (onde $p$ é qualquer primo) sofrem com tamanhos de chave subótimos.
  • Trabalhos anteriores (por exemplo, Boyle et al., Li et al.) alcançaram tamanhos de chave com expoentes envolvendo funções como $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$.
  • O objetivo é reduzir o tamanho assintótico da chave, mantendo a segurança perfeita e suportando qualquer primo $p$ arbitrário.

2. Metodologia

Os autores propõem uma construção inovadora baseada na Estrutura LKZ (Li, Kopparty e Zhang) combinada com técnicas de Recuperação de Informação Privada (PIR) de última geração.

A. A Estrutura LKZ

A estrutura transforma um Esquema de Compartilhamento de Segredos (SSS) em uma ITDPF por meio de Conversão de Partes.

1. Conversão de Partes: Requer converter partes de um SSS de limite $(t, n)$ ($L_1$) em partes de um SSS aditivo ($L_2$) de modo que a soma das partes convertidas revele uma relação específica com o segredo original.
2. Representação Bilnear: A função de ponto é representada como uma função bilinear das partes convertidas.
3. Insight Chave: O tamanho da chave da ITDPF resultante é proporcional à complexidade de comunicação do esquema PIR subjacente utilizado para gerar a conversão de partes.

B. Aproveitamento da PIR Baseada em Derivadas de GKS

A inovação técnica central é a utilização do recente esquema de PIR $n_r$-servidores com 1-privacidade de Ghasemi, Kopparty e Sudan (GKS, STOC 2025).

• Mecanismo GKS: Ao contrário de esquemas PIR anteriores que apenas consultam avaliações de um polinômio, o GKS consulta tanto avaliações quanto derivadas de Hasse do polinômio.
• Fundamento Matemático:
  • Utiliza famílias de correspondência $S$ e polinômios de decodificação $S$ sobre corpos finitos.
  • Introduz a propriedade de interpolação 0 com multiplicidade. Ao solicitar derivadas, o esquema pode interpolar o termo constante de um polinômio esparso usando menos servidores ou parâmetros menores.
  • Especificamente, o GKS alcança uma complexidade de comunicação de $2^{O(\nu_{r+1}(N))}$ para $n_r$ servidores, onde $n_r$ depende do número de fatores primos do módulo.

C. Etapas da Construção Proposta

1. Configuração:
   • Selecionar um módulo $M = m \cdot p$ (produto de primos distintos).
   • Construir uma família de correspondência $S_M$ e um polinômio de decodificação $S_M$ com multiplicidade 2 (habilitado pelas consultas de derivadas).
2. Conversão de Partes ($Conv$):
   • O servidor possui uma parte $c_\ell$ derivada de um vetor aleatório $w$ e do índice alvo $\alpha$.
   • Dada uma entrada $x$, o servidor calcula um "polinômio central" $D_x(Z)$ restrito a uma linha multiplicativa.
   • Usando a regra da cadeia, o servidor calcula a derivada de Hasse de primeira ordem de $D_x(Z)$ em pontos específicos $b_\ell$.
   • O servidor produz uma parte convertida envolvendo a avaliação $D_x(b_\ell)$ e o termo da derivada, ponderados por coeficientes de interpolação $a_{\ell, k}$.
3. Geração de DPF:
   • O gerador cria $2n_r$ chaves. Cada chave consiste em um par: uma parte aditiva do valor de saída e uma parte do SSS subjacente baseado em PIR.
   • O algoritmo de avaliação calcula o produto interno dos componentes da chave para recuperar a parte aditiva de $f_{\alpha, \beta}(x)$.

3. Contribuições Principais

1. Conversão de Partes Inovadora: Os autores derivam uma nova função de conversão de partes diretamente da PIR baseada em derivadas de GKS. Esta é a primeira aplicação de PIR baseada em derivadas para construir ITDPFs.
2. Tamanho de Chave Melhorado: Eles constroem uma ITDPF $(1, 2n_r)$ perfeitamente segura com grupo de saída $\mathbb{Z}_p$.
   • Tamanho da Chave: $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$.
   • Melhoria: Isso é assintoticamente menor do que as melhores ITDPFs perfeitamente seguras anteriores (por exemplo, $2^{O(\nu_r(N))}$ de Li et al.), reduzindo efetivamente o expoente de $\nu_r(N)$ para $\nu_{r+1}(N)$.
3. Segurança Perfeita: A construção mantém segurança perfeita (segurança teórica da informação contra adversários computacionalmente ilimitados), ao contrário de algumas alternativas estatísticas que trocam segurança por eficiência.
4. Generalidade: O esquema funciona para qualquer primo $p$ como módulo do grupo de saída, uma generalização significativa sobre algumas construções anteriores.

4. Resultados

• Limites Teóricos: O artigo prova que o esquema proposto satisfaz os requisitos de correção e segurança perfeita da estrutura LKZ.
• Comparação (Tabela I):
  • Comparado ao Teorema 10 de [10] (Li et al.), que possui tamanho de chave $O(2^{c_1(r) \cdot \nu_r(N)})$, o novo esquema alcança $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$. Como $\nu_{r+1}(N) < \nu_r(N)$, as novas chaves são estritamente mais curtas assintoticamente.
  • Comparado ao Teorema 1 de [2] (Boyle et al.), o novo esquema não é pior e oferece melhor escalabilidade assintótica para grandes $N$.
• Parâmetros: O número de servidores necessários é $2n_r$, onde $n_r$ é definido pelo número de fatores primos na construção PIR (por exemplo, $n_1=2, n_2=3, \dots$).

5. Significado

• Eficiência em MPC e PIR: As DPFs são blocos fundamentais para Computação Multipartidária Segura (MPC) e Recuperação de Informação Privada (PIR). Reduzir o tamanho da chave traduz-se diretamente em menor sobrecarga de comunicação e requisitos de armazenamento nesses protocolos.
• Ponte entre PIR e DPFs: O trabalho demonstra uma sinergia poderosa entre avanços recentes em PIR (especificamente abordagens baseadas em derivadas) e a construção de DPFs. Sugere que melhorias na complexidade de comunicação da PIR podem ser traduzidas diretamente em DPFs mais eficientes.
• Direções Futuras:
  • A construção atual é limitada a DPFs com 1-privacidade (segurança contra 1 servidor coludindo) porque a PIR GKS subjacente é 1-privada. Estender isso para DPFs com $t$-privacidade com $t > 1$ sem uma explosão exponencial no número de servidores é um desafio em aberto.
  • A extensão do grupo de saída de $\mathbb{Z}_p$ de ordem prima para grupos abelianos arbitrários é identificada como trabalho futuro.

Em resumo, este artigo apresenta um avanço na eficiência de ITDPFs perfeitamente seguras, aproveitando as técnicas mais recentes de PIR baseadas em derivadas, alcançando as chaves secretas mais curtas conhecidas para grupos de saída de ordem prima.