From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP

Resumo Técnico: Dos Bits às Chaves de Raiz Mista

Definição do Problema
O One-Time Pad de Raiz Mista (MR-OTP), introduzido em um trabalho precedente [1], generaliza o clássico One-Time Pad binário para espaços de dígitos com bases não uniformes. Ele permite a codificação nativa de alfabetos de dados heterogêneos (ex: sequências de DNA, texto latino) sem conversão binária intermediária, preservando a sigilo perfeito de Shannon. No entanto, uma implementação prática requer um mecanismo para converter a saída de entropia binária bruta de uma fonte de Distribuição de Chaves Quânticas (QKD) em uma tupla de chave uniformemente distribuída sobre o espaço de chaves de raiz mista.

Uma abordagem ingênua — ler $k = \lceil \log_2 P \rceil$ bits (onde $P$ é o produto das bases) e reduzir o inteiro resultante módulo $P$ — introduz uma distorção estatística conhecida como "viés de módulo" (modulo bias). No cenário de informação teórica, qualquer não-uniformidade na distribuição da chave viola a hipótese do teorema do sigilo perfeito, tornando o sistema inseguro, independentemente da magnitude do viés. O artigo aborda o desafio algorítmico de converter um fluxo binário uniforme em uma tupla de chave de raiz mista uniforme sem introduzir este viés, mantendo a segurança de ponta a ponta de informação teórica.

Metodologia
O artigo estabelece uma equivalência estrutural entre os pesos posicionais de raiz mista e a forma aninhada de avaliação polinomial.

1. Correspondência Algébrica: Os autores identificam o método de Horner e seu inverso como a dualidade algébrica canônica para esta conversão. O mapeamento direto (avaliação de Horner) compõe uma tupla de dígitos em um único inteiro, enquanto o mapeamento inverso (decomposição de Horner Inversa) recupera os dígitos de um inteiro através de redução modular sucessiva. Isso estabelece uma bijeção entre o espaço de chaves $\mathcal{K}$ e o intervalo de inteiros $\{0, \dots, P-1\}$.
2. Amostragem por Rejeição: Para eliminar o viés de módulo, o artigo propõe um algoritmo de amostragem por rejeição (Algoritmo 1). O algoritmo extrai $k$ bits para formar um inteiro $V$. Se $V \ge P$, a amostra é descartada e o processo se repete. Se $V < P$, a decomposição de Horner inversa é aplicada para gerar a tupla de chave.
3. Estrutura de Análise de Segurança: O artigo analisa todo o pipeline (QKD $\to$ Extração de Chave $\to$ Criptografia MR-OTP) através de sessões únicas e múltiplas. Ele emprega um esquema de partição de rolagem de chave (key-rolling) onde blocos disjuntos do fluxo QKD são usados para a chave e a sequência de bases de cada sessão.
4. Taxonomia de Adversários: A análise de segurança distingue quatro classes de adversários: baseados em testes, algébricos, ilimitados (unbounded) e de apenas texto cifrado (ciphertext-only). Ela separa o "segredo computacional" (a sequência de bases $B$) do "segredo de informação teórica" (o preenchimento/pad $K$).

Contribuições Principais e Resultados

• Amostragem de Chave Uniforme: O artigo prova que a redução modular ingênua quebra o sigilo perfeito (Proposição 3.1). Demonstra que a amostragem por rejeição combinada com a decomposição de Horner inversa restaura uma distribuição uniforme sobre o espaço de chaves (Teorema 3.4). O custo esperado de bits deste processo é limitado por $2\lceil \log_2 P \rceil$, com um número esperado de rodadas de rejeição de no máximo 2 (Proposição 3.5).
• Segurança de Ponta a Ponta: A composição de uma fonte QKD ideal, o algoritmo de amostragem por rejeição e o MR-OTP alcança o sigilo perfeito de Shannon para uma única sessão (Teorema 4.2) e através de $N$ sessões sob um esquema de rolagem de chave por partição (Teorema 6.2). Isso ocorre sem suposições computacionais.
• Eficiência de Representação: O artigo quantifica o ganho de eficiência do MR-OTP sobre o OTP binário para alfabetos naturais. Ao operar no espaço de símbolos nativo, o MR-OTP elimina o "overhead binário" ($\lceil \log_2 b \rceil - \log_2 b$) inerente à codificação binária. Por exemplo, oferece uma redução de $\approx 16,9\%$ em material de chave para dígitos decimais e $\approx 6,0\%$ para o alfabeto latino (Proposição 5.3).
• Problema de Recuperação de Base (BRP):
  • Apenas Texto Cifrado: O artigo prova que recuperar a sequência de bases $B$ apenas a partir do texto cifrado é insolúvel do ponto de vista de informação teórica (Corolário 8.2). O texto cifrado fornece zero informação sobre $B$ além da restrição $b_i > c_i$.
  • Texto Claro Conhecido: No cenário de texto claro conhecido, o artigo estabelece um limite inferior incondicional sobre a complexidade de consulta para adversários baseados em testes, mostrando que identificar $B$ requer pelo menos $|F_T| - 1$ consultas, onde $|F_T|$ permanece exponencial em relação ao comprimento da mensagem $L$ para pequenos $T$ (Teorema 8.10).
  • Invariância de Segurança: Um resultado central (Teorema 8.15) prova que mesmo que um adversário (limitado ou ilimitado) recupere com sucesso a sequência de bases $B$ a partir de dados de texto claro conhecido, ele obtém zero informação sobre qualquer mensagem futura criptografada sob uma nova chave. A segurança de informação teórica do preenchimento é preservada independentemente do status computacional do problema de recuperação de base.
• Extração em Lote (Batched Extraction): O artigo introduz um algoritmo de extração em lote (Seção 9) que extrai um único inteiro grande para gerar $N$ dígitos de chave simultaneamente. Isso reduz o overhead de rejeição em comparação com a amostragem sequencial, aproximando-se do limite teórico de entropia de $\log_2 b$ bits por símbolo conforme $N \to \infty$ (Teorema 9.2).
• Fontes Não Ideais: O artigo estende as garantias de segurança para fontes QKD não ideais que são $\epsilon$-próximas da uniformidade em distância de variação total. Mostra que a degradação da segurança de ponta a ponta é limitada por $2N\epsilon$ para $N$ sessões (Teorima 10.3).

Significância e Alegações
O artigo afirma fornecer a fundação algorítmica completa para o deployment do MR-OTP com fontes QKD, mantendo o sigilo estrito de informação teórica. Sua principal significância reside em:

1. Resolução do Problema do Viés: Fornece um método provadamente correto (amostragem por rejeição + inversão de Horner) para converter entropia binária em chaves de raiz mista sem violar o requisito de uniformidade do sigilo perfeito.
2. Segurança Temporal Incondicional: Estabelece que a segurança de mensagens futuras é independente da dificuldade computacional de recuperar a sequência de bases. Mesmo que a sequência de bases seja recuperada, o sistema retém o sigilo perfeito para novas criptografias. Isso cria uma estrutura de "dois níveis" de segurança, onde a camada computacional (esconder a base) e a camada de informação teórica (esconder a mensagem) são independentes.
3. Eficiência: Demonstra que o MR-OTP não é apenas teoricamente sólido, mas também praticamente mais eficiente que o OTP binário para alfabetos que não são potências de dois, reduzindo o consumo de chaves sem sacrificar a segurança.
4. Classificação de Adversários: Classifica rigorosamente as capacidades dos adversários, provando que a garantia de informação teórica é incondicional para todas as classes de adversários, enquanto os resultados de dureza computacional aplicam-se apenas a subconjuntos específicos (testes vs. algébricos) no cenário de texto claro conhecido.

O artigo conclui identificando problemas abertos, especificamente em relação à variante de rolagem de chave dinâmica (onde a sequência de bases depende de textos cifrados anteriores) e a dureza computacional de caso médio do Problema de Recuperação de Base para adversários algébricos.