Correlation Bounds and Markov Analysis for Ring-Oscillator TRNGs: A Joint Validation Framework

1. Problema e Motivação

Os Geradores de Números Aleatórios Verdadeiros (TRNGs) baseados em osciladores de anel (Ring Oscillators - ROs) são fundamentais para aplicações criptográficas, fornecendo sementes imprevisíveis. No entanto, validar a qualidade estatística desses geradores é complexo.

• Falta de Correlação entre Métricas: Embora existam medidas teóricas robustas, como a medida de correlação de ordem $k$ de Mauduit-Sárközy ($C_k$) e testes empíricos como o Teste Universal de Maurer (que avalia a entropia via compressibilidade), não havia trabalhos anteriores que correlacionassem essas métricas ou estabelecessem limites teóricos conjuntos entre elas.
• Necessidade de Validação Unificada: Projetistas de TRNGs frequentemente utilizam baterias de testes (como NIST ou Diehard) sem uma compreensão teórica unificada de como a estrutura do gerador (ex: amostragem vs. contagem) impacta simultaneamente a entropia e a correlação.

2. Metodologia

O artigo propõe um framework de validação conjunta que conecta três pilares teóricos e empíricos:

1. Medida de Correlação ($C_k$): Especificamente a correlação de segunda ordem ($C_2$), que mede a dependência estatística entre bits separados por um atraso.
2. Teste de Maurer: Utiliza o escore Z ($Z$) para avaliar a compressibilidade da sequência e, consequentemente, a entropia.
3. Cadeias de Markov de Alta Ordem: Modelagem da saída do TRNG como um processo estocástico com memória, permitindo a análise das probabilidades de transição entre estados de bits.

Abordagem Experimental:

• Ferramenta: Utilização do framework de código aberto OpenTRNG para simulações reprodutíveis.
• Arquitetura: Foco em TRNGs baseados em osciladores de anel (ERO, MURO, COSO) com extração diferencial baseada em contagem de períodos (diferente da amostragem direta de bits).
• Configuração: Variação de frequências dos osciladores ($f_1, f_2$), frequência de referência ($f_{ref}$) e profundidade de acumulação XOR ($n$).
• Análise: Geração de $10^5$ bits para cada configuração, calculando $C_2$ e o escore Z de Maurer, e comparando os resultados com limites teóricos (incluindo o limite aprimorado de Schmidt).

3. Principais Contribuições Teóricas

O artigo estabelece relações matemáticas inéditas entre as métricas:

• Relação $C_k$ e Probabilidades de Transição de Markov: O Teorema 1 demonstra que uma baixa correlação $C_k(S)$ garante que as probabilidades de transição de uma cadeia de Markov de ordem $k$ estejam próximas de $1/2$. Especificamente, desvios nas probabilidades de transição são limitados por uma função de $C_k(S)$. Isso conecta a estrutura combinatória (correlação) à estrutura probabilística (entropia).
• Limites entre Teste de Maurer e Correlação: O Teorema 2 deriva limites teóricos que relacionam a função de teste de Maurer ($f_{TU}$) diretamente com a medida de correlação $C_k(S)$. Isso permite prever o comportamento do teste de Maurer com base na correlação da sequência.
• Validação do Limite de Schmidt: O trabalho valida computacionalmente que implementações práticas podem atingir o limite de correlação aprimorado de Schmidt ($C_k \le \sqrt{2^k \ln(N)/N}$), que é significativamente mais rigoroso que o limite anterior de Alon.

4. Resultados Experimentais

As simulações realizadas com 58 configurações de parâmetros no OpenTRNG revelaram:

• Correlação Positiva Forte: Existe uma forte correlação positiva (Pearson $r = 0.95$) entre o escore Z de Maurer e a correlação de segunda ordem fora do pico ($C_2$). Isso significa que, à medida que a correlação diminui (melhor aleatoriedade), o escore Z de Maurer tende a se aproximar de zero (ideal).
• Desempenho da Extração Diferencial por Contagem:
  • O método de contagem de períodos (counter-based) superou drasticamente a amostragem direta de bits.
  • Amostragem direta: $C_2 = 0.34$ (falha nos testes).
  • Contagem diferencial: $C_2 = 0.009$ (passa nos testes, $|Z| < 1$).
  • Isso representa uma melhoria de aproximadamente 40 vezes na métrica de correlação.
• Acumulação XOR: O uso de acumulação XOR de múltiplas fontes independentes ($n \ge 4$) moveu as configurações para a região ideal ($|Z| \approx 0$ e $C_2 < 0.01$).
• Conformidade com o Limite de Schmidt: As implementações práticas alcançaram valores de $C_2$ que são 2 a 3 vezes inferiores ao limite teórico de Schmidt, indicando alta qualidade de aleatoriedade.

5. Significado e Conclusão

Este trabalho preenche uma lacuna crítica na literatura de TRNGs ao unificar a análise teórica e empírica:

• Protocolo de Validação Simplificado: Os autores propõem que projetistas podem adotar um protocolo prático onde a verificação conjunta de $C_2 < 0.01$ e $|Z| < 2$ serve como um indicador robusto de qualidade, sugerindo que o TRNG passará em baterias de testes completas (como NIST ou AIS31).
• Ponte Teórico-Prática: A conexão estabelecida entre as cadeias de Markov, a medida de correlação e o teste de compressibilidade de Maurer oferece uma base matemática sólida para o design de novos TRNGs.
• Impacto no Design: A confirmação de que a extração diferencial baseada em contagem reduz drasticamente a correlação e melhora a entropia valida essa arquitetura como superior para aplicações de segurança de alto nível.

Em resumo, o artigo fornece não apenas uma nova ferramenta de validação, mas também uma compreensão teórica profunda de como a arquitetura física do oscilador e o método de extração de dados influenciam diretamente as propriedades estatísticas e criptográficas do gerador de números aleatórios.