Resumo Técnico: Melhoria da Resiliência à Vazamento Local de Shamir Secret Sharing e Interseção de Polinômios Ótima no Pior Caso

1. Enunciado do Problema

Este artigo aborda dois problemas distintos, mas interconectados, relativos a polinômios $Q(X)$ de grau menor que $k$ sobre um corpo finito de ordem prima $\mathbb{F}_p$:

1. Resiliência à Vazamento Local (LLR) para Shamir Secret Sharing: O problema questiona quanta informação um adversário pode aprender sobre o segredo $Q(0)$ dado um número limitado de bits (especificamente um bit) vazado de cada parcela $Q(\alpha_i)$. O objetivo é determinar a taxa mínima $R = k/n$ necessária para garantir que o segredo permaneça seguro (ou seja, que a distância de variação total entre as distribuições de transcrição para diferentes segredos seja negligenciável). Antes deste trabalho, o melhor limite conhecido exigia $R \geq 0,668$, e suspeitava-se que uma "barreira" em $R = 1/2$ fosse insuperável para funções de vazamento de pior caso.

2. Interseção de Polinômios Ótima (OPI) no Pior Caso: Dadas listas de entrada $S_1, \dots, S_n \subset \mathbb{F}_p$ e pontos de avaliação $\alpha_i$, o objetivo é encontrar um polinômio $Q(X)$ de grau $< k$ que satisfaça $Q(\alpha_i) \in S_i$ para o maior número possível de índices $i$. O problema investiga a existência de tais polinômios (resultados existenciais) e a eficiência de encontrá-los (resultados algorítmicos), particularmente no contexto de algoritmos quânticos. Trabalhos anteriores estabeleceram que algoritmos quânticos poderiam alcançar uma razão de satisfação relacionada à "lei do semicírculo" $SCL_\rho(R/2)$, enquanto algoritmos clássicos estavam limitados a razões menores.

2. Metodologia e Estrutura Técnica

Os autores desenvolvem um arcabouço de análise de Fourier unificado que reduz tanto LLR quanto OPI ao problema de decodificação de lista e recuperação de lista do código dual (especificamente, códigos de Reed-Solomon Generalizados).

Componentes Técnicos Principais:

• Proxies de Fourier: Os autores definem "proxias de Fourier" para limitar as quantidades de interesse. Para OPI, eles limitam a discrepância entre o tamanho real da interseção e o tamanho esperado para listas aleatórias. Para LLR, eles limitam a distância de variação total entre as distribuições de transcrição. Essas proxias são expressas como somas sobre o código dual $C^\perp$ envolvendo coeficientes de Fourier das funções de vazamento ou dos conjuntos de entrada.
• Limiar de Fourier Ponderado (Lema 1.15): Uma contribuição técnica central é um lema que limita somas ponderadas sobre o código dual. Ao aproveitar os recentes avanços na recuperação de lista de códigos Reed-Solomon (Brakensiek et al., 2026; Jeronimo, 2026; Dao et al., 2026), os autores mostram que essas somas são exponencialmente pequenas quando a taxa $R > 1/2$.
• Cruzando a Barreira de 1/2: Para lidar com taxas $R \leq 1/2$, os autores não podem confiar apenas em proxias "de fase esquecida" (que ignoram as fases complexas dos coeficientes de Fourier). Em vez disso, eles utilizam normas de Gowers (especificamente a norma $U^3$) e a desigualdade de von Neumann generalizada para explorar os cancelamentos de fase nas somas de Fourier originais. Isso permite provar resiliência e limites de discrepância mesmo quando $R$ é ligeiramente inferior a $1/2$.
• Algoritmos Quânticos (DQI): Para resultados algorítmicos, o artigo utiliza o arcabouço de Interferometria Quântica Decodificada (DQI). Os autores melhoram a análise do estado quântico $|\phi_\ell\rangle$ proposto em trabalhos anteriores. Ao combinar os limites existenciais melhorados de OPI com algoritmos eficientes de decodificação de lista para o código dual, eles demonstram como preparar estados quânticos que geram soluções de alta satisfação.
• Separação de Hardness (Dificuldade): Para estabelecer uma vantagem quântica, os autores adaptam os resultados de dificuldade de Yamakawa e Zhandry (2024) relativos a códigos Reed-Solomon dobrados (folded). Eles constroem dois tipos de conjuntos OPI (esparsos e equilibrados) que codificam o problema de fonte Yamakawa-Zhandry, provando que, embora algoritmos quânticos possam resolver essas instâncias eficientemente, algoritmos clássicos requerem consultas superpolinomiais.

3. Contribuições e Resultados Principais

A. Resiliência à Vazamento Local (LLR)

O artigo quebra a longa "barreira de um meio" para a resiliência ao vazamento local de pior caso no Shamir secret sharing:

• Teorema 1.3: Os autores provam que o Shamir secret sharing é resiliente ao vazamento local de um bit para qualquer taxa $R > 1/2 - \delta$ (para algum constante absoluto $\delta > 0$).
• Isso melhora o melhor resultado anterior que exigia $R \geq 0,668$ (Kasser, 2025).
• O resultado aplica-se a funções de vazamento arbitrárias (pior caso), não apenas às equilibradas. Os autores demonstram adicionalmente que o caso equilibrado é o mais difícil, o que implica que seu limiar se aplica de forma geral.
• Para qualquer número fixo de bits vazados $b$, o esquema é resiliente para todo $R > 1/2$.

B. Interseção de Polinômios Ótima (OPI)

O artigo fornece melhorias significativas tanto em garantias existenciais quanto algorítmicas:

• Discrepância Próxima da Ótima (Teorema 1.10): Os autores provam que os códigos Reed-Solomon possuem uma discrepância de OPI próxima da ótima (implicando a existência de soluções perfeitas) sob três condições:
  1. $R > 1/2$.
  2. $R > 1/2 - \delta$ e densidade de entrada $\rho \geq 1/2 - \delta$.
  3. $R + \rho > 1$.
• Algoritmo Quântico (Teorema 1.8): Eles apresentam um algoritmo quântico que encontra uma solução com razão de satisfação de pelo menos $SCL_\rho(R)$ (a "lei do duplo semicírculo"), melhorando os limites anteriores de $SCL_\rho(R/2)$.
  • Crucialmente, se $R + \rho > 1$, o algoritmo encontra uma solução perfeita (satisfazendo todas as restrições) com alta probabilidade.
• Melhoria Existencial (Teorema 1.11): Para taxas $R \in (\rho, 1/2]$, os autores provam a existência de soluções com razão de satisfação $V_\rho(R) = 1 - (1-2\rho)(1-2R)$, que excede estritamente a garantia da lei do duplo semicírculo. Este resultado é existencial e não possui atualmente um contraparte algorítmica eficiente.

C. Vantagem Quântica

• Teorema 1.12: O artigo estabelece uma separação incondicional entre a dificuldade quântica e clássica para OPI em relação a um oráculo de pertinência (membership oracle).
• Eles constroem um conjunto aleatório de instâncias de OPI equilibradas sobre corpos quase-polinomiais onde um algoritmo quântico de tempo polinomial encontra uma solução perfeita, enquanto qualquer algoritmo clássico realizando consultas polinomiais tem probabilidade negligenciável de encontrar uma solução com razão de satisfação melhor que $1/2 + \Omega(1/\log \log n)$.

4. Significância e Alegações

O artigo afirma ser o primeiro a quebrar a barreira de $1/2$ para a resiliência ao vazamento local de pior caso no Shamir secret sharing, um limiar que era um grande problema em aberto. Ao unificar LLR e OPI através de uma lente de análise de Fourier e aproveitar os recentes avanços na recuperação de lista de Reed-Solomon, os autores alcançam:

1. Limites de Segurança Mais Estritos: Reduzindo a taxa necessária para o compartilhamento de segredo seguro contra vazamento local.
2. Melhores Algoritmos Quânticos: Impulsionando a razão de satisfação alcançável para OPI de $R/2$ para $R$ (a lei do duplo semicírculo) e permitindo soluções perfeitas em regimes de alta densidade.
3. Separações de Hardness: Fornecendo um exemplo concreto onde algoritmos quânticos oferecem uma vantagem superpolinomial sobre algoritmos clássicos para um problema algébrico natural (OPI) em relação a oráculos de pertinência, estendendo o escopo dos resultados de Yamakawa-Zhandry de códigos dobrados para códigos escalares.

Os autores enfatizam que suas técnicas dependem do "arcabouço comum de análise de Fourier" que reduz esses problemas à recuperação de lista dual, permitindo importar avanços combinatórios recentes para alcançar essas melhorias. Eles declaram explicitamente que as melhorias existenciais além da lei do duplo semicírculo (Teorema 1.11) não são atualmente conhecidas como computáveis de forma eficiente.