Quantum algorithm for Discrete Gaussian Sampling

Resumo Técnico: Algoritmo Quântico para Amostragem Gaussiana Discreta

Declaração do Problema
A Amostragem Gaussiana Discreta (DGS) em reticulados é um problema fundamental na criptografia baseada em reticulados, servindo como componente central tanto para primitivas criptográficas (por exemplo, assinaturas digitais "hash-and-sign") quanto para criptanálise (por exemplo, resolver o Problema do Vetor Mais Curto, Learning with Errors (LWE) e Short Integer Solution (SIS)). A tarefa envolve amostrar um vetor de reticulado $x$ com probabilidade proporcional a $e^{-\pi\|x-c\|^2/\sigma^2}$. A dificuldade da amostragem aumenta à medida que o parâmetro de largura $\sigma$ diminui, particularmente abaixo do "parâmetro de suavização".

Algoritmos clássicos existentes enfrentam trade-offs significativos:

• Amostrador de Klein: Eficiente (tempo polinomial), mas restrito a valores grandes de $\sigma$ dependentes da qualidade da base de entrada.
• Cadeia de Markov Monte Carlo (MCMC) [49]: Funciona para qualquer $\sigma$, mas sofre de alta complexidade de tempo, escalando inversamente com um parâmetro $\Delta$ (relacionado à razão de massas gaussianas), tornando-o exponencial no pior caso.
• Algoritmos de Memória Exponencial: Algoritmos como [3] podem amostrar para qualquer $\sigma$, mas exigem memória exponencial, tornando-os impraticáveis para criptanálise.

Atualmente, nenhum algoritmo quântico conhecido oferece aceleração para esses métodos de amostragem sem depender de recursos irreais como RAM quântica (qRAM) para memória exponencial, ou falham em melhorar a complexidade assintótica da abordagem MCMC.

Metodologia
Os autores propõem um algoritmo quântico para DGS baseado em Amostragem de Rejeição Quântica [41]. A estratégia central envolve transformar um estado quântico preparado por uma distribuição conhecida em uma distribuição alvo via amplificação de amplitude.

1. Preparação do Estado Inicial (Amostrador Quântico de Klein): O algoritmo começa preparando um estado quântico correspondente a uma variante da distribuição de Klein, $|q\rangle$. Isso é alcançado adaptando o algoritmo clássico de amostragem de Klein (Algoritmo 1) para um circuito quântico (Algoritmo 2), conforme detalhado em [11]. Esta etapa constrói uma superposição de vetores de reticulado onde as amplitudes aproximam a distribuição de Klein.
2. Transdução de Amplitude: O algoritmo emprega uma operação unitária para modificar as amplitudes do estado $|q\rangle$. Ele calcula a razão entre a distribuição gaussiana discreta alvo $D_{\Omega, \sigma}$ e a distribuição inicial de Klein $q$. Isso envolve estimar massas gaussianas sobre intervalos finitos usando técnicas de Kitaev e Webb [31] e de Boer [10].
3. Amostragem de Rejeição Quântica: Usando a razão calculada, o algoritmo aplica transdução de amplitude a um qubit ancilla. O estado é então projetado no subespaço de "aceitação" usando Amplificação de Amplitude Quântica (QAA) [17]. O número de iterações necessárias é proporcional à raiz quadrada da razão de rejeição $w = \max_x (D_2(x)/D_1(x))$.
4. Precisão e Aproximação: O algoritmo opera com estados de distribuição aproximada $|D \pm 2^{-\nu}\rangle$. Os autores delimitam rigorosamente a distância de variação total entre o estado de saída e a distribuição gaussiana discreta ideal, garantindo que o erro seja negligenciável ao escolher parâmetros apropriados para o tamanho do domínio finito $M$ e a precisão $\nu$.

Principais Contribuições
O artigo apresenta três contribuições primárias:

1. Uma Aceleração Quadrática na Complexidade de DGS: Os autores demonstram um algoritmo quântico que amostra de uma distribuição gaussiana discreta com uma aceleração quadrática assintótica sobre o algoritmo clássico MCMC [49]. Enquanto a complexidade clássica escala como $O(1/\Delta)$, a complexidade quântica escala como $O(1/\sqrt{\Delta})$, onde $\Delta$ representa a razão de massas gaussianas. Esta aceleração é alcançada sem exigir memória quântica exponencial, utilizando apenas qubits polinomiais (embora possa depender de qRAM para acesso à memória clássica em cenários específicos de ataque).
2. Duas Variantes de Ataques Duais Quânticos ao LWE: Os autores aplicam seu amostrador ao framework de ataque dual "moderno" ao LWE [42], propondo duas versões quânticas distintas:
   • Variante 1 (com qRAM): Substitui a etapa de amostragem MCMC clássica na primeira fase do ataque pelo amostrador quântico. Isso resulta em uma aceleração quadrática na fase de amostragem, mas mantém a exigência de qRAM na segunda fase (distinguidor baseado em FFT).
   • Variante 2 (sem qRAM): Uma abordagem inovadora que integra o amostrador quântico diretamente na segunda fase do ataque. Ao combinar o amostrador com um algoritmo de estimativa de média quântica (Corolário 1), esta variante evita completamente a necessidade de qRAM, exigindo apenas memória clássica e quântica polinomial. Embora tenha uma complexidade de tempo maior que a Variante 1, oferece uma vantagem distinta em restrições de memória.
3. Aceleração Quântica para SIS: Os autores aplicam seu amostrador ao algoritmo para resolver o problema Short Integer Solution (SIS) para qualquer norma [12]. Ao quantizar a etapa de amostragem e aplicar amplificação de amplitude para filtrar vetores curtos, eles alcançam uma aceleração quadrática sobre a contraparte clássica (excluindo a etapa de pré-processamento BKZ).

Resultados e Análise de Complexidade

• Complexidade de Amostragem: O amostrador quântico proposto alcança uma contagem de portas de aproximadamente $\tilde{O}(mM(\nu + mM + m^2r)^2)$ e contagem de qubits de $\tilde{O}(m(\nu + mM + m^2r))$, onde $m$ é a dimensão do reticulado. A complexidade é dominada pela raiz quadrada do custo clássico do MCMC.
• Ataques Duais ao LWE:
  • A variante baseada em qRAM melhora a complexidade do ataque por um fator de $\sqrt{\Delta}$ em comparação com o ataque baseado em MCMC clássico.
  • A variante sem qRAM fornece uma alternativa eficiente em memória, trocando tempo pela eliminação de requisitos de memória clássica exponencial.
• SIS no Dilithium: O artigo fornece estimativas aproximadas para a complexidade quântica de atacar o problema SIS no esquema de assinatura Dilithium. Os resultados (Tabela 2) indicam que, embora o ataque quântico reduza significativamente a complexidade de tempo em comparação com ataques clássicos (por exemplo, reduzindo $\log_2 T_{attack}$ de 202 para 146 para o NIST Level 2), a complexidade permanece fortemente limitada pela etapa de pré-processamento de redução de base BKZ.

Significado e Alegações
Os autores posicionam este trabalho como uma expansão da "caixa de ferramentas de criptanálise quântica". Eles reconhecem explicitamente que as acelerações assintóticas apresentadas podem ser difíceis de realizar na prática devido aos custos inerentes de manter qRAM e à natureza sequencial da busca de Grover. O artigo não alega quebrar padrões específicos do NIST imediatamente, mas fornece limites teóricos e melhorias algorítmicas.

O significado reside em:

• Fornecer a primeira aceleração quântica conhecida para Amostragem Gaussiana Discreta que é aplicável aos regimes de parâmetros usados na criptanálise baseada em reticulados.
• Demonstrar que técnicas quânticas podem ser adaptadas para reduzir requisitos de memória em ataques duais, oferecendo uma nova dimensão (memória vs. tempo) para trade-offs criptanalíticos.
• Estabelecer um framework para quantizar algoritmos que dependem de amostragem MCMC, potencialmente aplicável a outros problemas de reticulados além de LWE e SIS.

Os autores concluem que, embora detalhes de implementação prática (profundidade, contagens de portas não assintóticas) sejam deixados para trabalhos futuros, os resultados teóricos oferecem uma base rigorosa para entender a dificuldade quântica de problemas de reticulados.