Resumo Técnico: Resiliência à Fuga Quântica de Shamir Secret Sharing

Declaração do Problema

O artigo investiga a resiliência à fuga quântica do esquema padrão e não modificado de compartilhamento de segredos de Shamir sobre corpos primos $\mathbb{F}_p$. Embora o esquema de Shamir seja amplamente utilizado em criptografia de limiar (threshold cryptography) e computação multipartidária segura, suas garantias de segurança assumem tradicionalmente que conjuntos não autorizados não aprendem nada sobre o segredo. Na prática, contudo, informações parciais (fugas) podem ser expostas através de canais laterais.

Os autores estendem o estudo da resiliência à fuga local do cenário clássico (onde um adversário obtém uma saída clássica curta, por exemplo, um bit, de cada parte) para o cenário quântico. Neste modelo, o dispositivo de cada parte recebe uma parte clássica e produz um único qubit (ou um pequeno número de qubits) para um adversário que pode realizar medições conjuntas. O estudo explora ainda como o entrelaçamento pré-compartilhado entre os dispositivos de fuga, ou entre os dispositivos e o adversário, impacta a segurança.

Metodologia

O artigo emprega uma combinação de análise de Fourier em corpos finitos e propriedades de códigos de Distância Máxima Separável (MDS) para limitar a vantagem de distinção entre dois estados de segredo.

1. Redução de Fourier de Pauli:

   • A fuga de cada parte é modelada como uma matriz de densidade $\rho_i(y_i)$. Os autores a expandem na base de Pauli: $\rho_i(y) = \frac{1}{2}(I + r_{i,X}(y)X + r_{i,Y}(y)Y + r_{i,Z}(y)Z)$.
   • Eles definem um "orçamento de Fourier" $W_i(a)$ baseado nas magnitudes ao quadrado dos coeficientes de Fourier das funções de coeficientes de Pauli.
   • Usando a identidade de Parseval e a ortogonalidade dos operadores de Pauli, a vantagem de distinção é limitada por uma soma sobre o código dual de Shamir $C^\perp_0$:
     $$\text{Adv} \leq \sum_{a \in C^\perp_0 \setminus \{0\}} \prod_{i=1}^n \sqrt{W_i(a_i)}$$
   • Isso reduz o problema de segurança quântica ao controle de uma soma ponderada sobre o código dual, de forma semelhante às provas de fuga clássica, mas complicada pela natureza matricial dos coeficientes.

2. Tratamento de Entrelaçamento e Blocos:

   • Blocos Disjuntos: Para dispositivos que compartilham entrelaçamento dentro de blocos disjuntos (mas não entre blocos ou com o adversário), os autores aplicam uma desigualdade de Brascamp-Lieb MDS em blocos. Isso permite limitar a soma dos produtos das normas de traço dos coeficientes de Fourier para saídas de blocos.
   • Entrelaçamento com o Adversário: Para um conjunto de dispositivos $E$ que compartilham entrelaçamento arbitrário com o adversário, os autores utilizam um argumento de redução. Eles mostram que, se o adversário aprende as partes clássicas de $E$, a segurança do sistema restante reduz-se a um esquema de Shamir não entrelaçado com $n-r$ partes e limiar $t-r$.

3. Resultados Negativos (Ataques):

   • O artigo constrói um ataque específico usando um estado GHZ compartilhado entre $t$ dispositivos. Ao aplicar deslocamentos de fase dependentes de suas partes e medir na base de Pauli-X, os dispositivos podem distinguir entre segredos com alta vantagem, mesmo que produzam apenas um bit clássico cada.

Contribuições Principais e Resultados

1. Fuga Quântica Não Entrelaçada

Os autores provam que o compartilhamento de segredos de Shamir é seguro contra a fuga quântica local de um qubit não entrelaçado, desde que a taxa de limiar $\tau = t/n$ exceda uma constante específica $\tau^\star \approx 0,73339$.

• Resultado: Se $\tau > \tau^\star + \eta$ (para um $\eta > 0$ fixo), a vantagem de distinção é exponencialmente pequena ($2^{-\Omega(n)}$).
• Técnica: Isto é derivado usando a desigualdade de Brascamp-Lieb MDS em blocos com tamanho de bloco $b=1$.

2. Blocos Entrelaçados Disjuntos

A segurança é estendida para cenários onde os dispositivos são particionados em blocos disjuntos de tamanho máximo fixo $b$, onde os dispositivos dentro de um bloco podem compartilhar entrelaçamento e realizar computações conjuntas, mas os blocos são independentes entre si e do adversário.

• Resultado: A segurança mantém-se para taxas de limiar suficientemente altas $\tau > \tau^\star(b)$, onde $\tau^\star(b) < 1$. À medida que o tamanho do bloco $b$ aumenta, a taxa de limiar necessária aproxima-se de 1.
• Especificidades: A Tabela 1 no artigo lista limiares suficientes para tamanhos de bloco iguais (por exemplo, para $b=2$, $\tau \approx 0,933$; para $b=3$, $\tau \approx 0,987$).

3. Fuga com Entrelaçamento do Adversário

O artigo analisa o caso em que uma fração linear de dispositivos ($r = \delta n$) compartilha entrelaçamento arbitrário entre si e com o adversário.

• Resultado: A segurança mantém-se se a taxa "residual" satisfizer:
  $$\frac{\tau - \delta}{1 - \delta} > \tau^\star$$
  Isso implica que, para uma taxa de limiar $\tau > \tau^\star$ fixa, a segurança é mantida mesmo se uma fração linear de dispositivos ($\delta < \frac{\tau - \tau^\star}{1 - \tau^\star}$) compartilhar entrelaçamento com o adversário.

4. Resultado Negativo: Ataque GHZ

Os autores demonstram que, se $t$ dispositivos compartilharem um estado GHZ, o esquema torna-se inseguro mesmo sob fuga clássica de um único bit.

• Mecanismo: $t$ dispositivos compartilham um estado GHZ. Cada um aplica um deslocamento de fase baseado em sua parte e mede na base X; o produto dos resultados revela o segredo com vantagem $\cos^2(\pi/(2p)) \approx 1 - O(p^{-2})$.
• Implicação: Este ataque não requer entrelaçamento com o adversário, apenas entre os $t$ dispositivos de fuga. Ele estabelece que o número máximo de dispositivos que podem compartilhar entrelaçamento arbitrário preservando a segurança é linear em $n$ (até fatores constantes), mas a fração ótima permanece uma questão em aberto.

Significância e Alegações

O artigo afirma iniciar o estudo da resiliência à fuga quântica para o amplamente utilizado e não modificado esquema de compartilhamento de segredos de Shamir.

• Robustez de Esquemas Padrão: Os resultados mostram que o esquema de Shamir padrão retém fortes garantias de segurança contra a fuga quântica sem exigir novos algoritmos de compartilhamento ou mudanças de protocolo, desde que o limiar seja suficientemente alto (acima de $\approx 0,733$).
• Papel do Entrelaçamento: O trabalho destaca uma distinção crítica: enquanto a fuga quântica não entrelaçada é gerenciável com limiares altos, a presença de entrelaçamento arbitrário entre os dispositivos de fuga (especificamente um estado GHZ entre $t$ dispositivos) pode quebrar a segurança mesmo para saídas clássicas.
• Otimalidade: Os autores são modestos quanto à otimalidade de seus limites. Eles observam que o limiar suficiente $\tau^\star \approx 0,733$ é superior ao limite clássico conhecido ($\approx 0,668$) e colocam a questão de se essa lacuna pode ser fechada. Da mesma forma, a fração exata de dispositivos entrelaçados compatível com a segurança é deixada como um problema em aberto.

O artigo conclui que a resiliência à fuga quântica depende fundamentalmente tanto do tamanho das saídas vazadas quanto da estrutura de entrelaçamento disponível para os dispositivos de fuga.