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

1. 연구 배경 및 문제 제기 (Problem)

• 배경: 암호학적으로 안전한 난수 생성기 (TRNG) 는 예측 불가능한 키와 논스 (nonce) 생성에 필수적입니다. 링 발진기 (Ring Oscillator, RO) 기반 TRNG 는 열적 지터 (thermal jitter) 를 엔트로피 원천으로 활용하여 널리 사용되지만, 그 출력의 통계적 품질을 보장하기 위한 엄격한 검증이 필요합니다.
• 문제: 기존 연구에서는 Mauduit-Sarkozy $k$차 상관관계 측정치 ($C_k$) 와 Maurer 의 범용 통계 테스트 (Maurer's Universal Test) 가 각각 이론적 경계와 경험적 엔트로피 평가를 제공해 왔으나, 이 두 가지 지표를 서로 연관시키거나 통합하여 검증한 선행 연구는 존재하지 않았습니다. 또한, 고차 마르코프 체인 전이 확률과 이러한 지표들 간의 수학적 관계를 규명한 연구도 부족했습니다.
• 목표: Maurer 테스트의 Z-score 와 2 차 상관관계 ($C_2$) 간의 관계를 규명하고, 이를 링 발진기 TRNG 의 품질 평가를 위한 통합 프레임워크로 제시하는 것.

2. 방법론 (Methodology)

• 이론적 분석:
  • 상관관계와 마르코프 체인의 연결: $k$차 상관관계 측정치 ($C_k$) 와 $k$차 마르코프 체인의 전이 확률 (transition probabilities) 간의 수학적 관계를 유도했습니다. 특히, $C_k$가 낮을수록 전이 확률이 $1/2$에 근접하여 고차 엔트로피를 보장함을 증명했습니다.
  • Maurer 테스트와의 관계: Maurer 테스트의 함수 값 ($f_{TU}$) 과 상관관계 측정치 ($C_k$) 사이에 상한과 하한을 설정하는 이론적 경계를 도출했습니다.
• 실험적 검증 (OpenTRNG 활용):
  • 아키텍처: Allini 등 [6] 의 차동 카운터 기반 접근법을 따랐습니다. 두 개의 서로 다른 주파수를 가진 링 발진기 (RO) 를 기준 클록으로 샘플링하고, 두 카운터의 최하위 비트 (LSB) 를 XOR 하여 원시 출력을 생성합니다. 이는 공통 모드 지터를 제거하고 독립적인 열 잡음을 격리합니다.
  • 변수 설정: OpenTRNG 프레임워크를 사용하여 58 가지 구성 (ERO 및 COSO 아키텍처) 에 대해 실험했습니다. 변수로는 발진기 주파수, 기준 주파수, XOR 누적 깊이 ($n=1$~$16$) 등을 변경했습니다.
  • 측정 지표: 생성된 $10^5$비트 시퀀스에 대해 2 차 상관관계 ($C_2$) 와 Maurer Z-score 를 계산했습니다.

3. 주요 기여 (Key Contributions)

1. 최초의 경험적 상관관계 규명: Maurer 의 Z-score 와 피크가 아닌 (off-peak) 2 차 상관관계 ($C_2$) 간의 강한 양의 상관관계 (Pearson $r \approx 0.95$) 를 최초로 발견하고 실증했습니다.
2. 수학적 관계 도출: $C_k$ 상관관계 측정치와 고차 마르코프 체인 전이 확률, 그리고 Maurer 테스트 간의 명시적인 수학적 관계를 유도했습니다.
3. 통합 검증 프레임워크 제시: TRNG 설계자가 $C_2$와 Maurer Z-score 를 동시에 사용하여 설계 결함을 조기에 감지하고 품질을 인증할 수 있는 실용적인 프로토콜을 제안했습니다.

4. 실험 결과 (Results)

• 강한 상관관계: 58 가지 구성에서 $C_2$와 Maurer Z-score 는 Pearson 상관계수 0.95 의 강한 양의 상관관계를 보였습니다.
• 성능 기준:
  • $|Z| < 0.1$인 구성은 일관되게 $C_2 < 0.01$을 달성했습니다.
  • $C_2 > 0.8$인 경우 $Z > 1$로 나타나 무작위성에서 벗어난 것을 의미했습니다.
• 카운터 기반 vs 직접 샘플링:
  • 직접 비트 샘플링 방식은 $C_2 = 0.34$, $Z = -2.1$로 테스트에 실패했습니다.
  • 반면, 카운터 기반 추출 방식은 $C_2 = 0.009$, $|Z| < 1$로 테스트에 성공했으며, 이는 약 40 배의 $C_2$ 개선을 의미합니다.
• Schmidt 경계 달성: 실험 결과, 차분 추출 (differential extraction) 방식을 사용한 구현체들은 Schmidt 가 제안한 개선된 이론적 경계 ($C_2 \lesssim 0.021$) 보다 2~3 배 더 낮은 값을 달성하여 매우 높은 품질을 보였습니다.
• XOR 누적 효과: XOR 누적 깊이 ($n$) 를 4 이상으로 증가시키면 성능이 이상적인 영역 ($|Z| \approx 0, C_2 < 0.01$) 에 더 가까워지는 것을 확인했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 통합 품질 지표: TRNG 설계자는 별도의 복잡한 테스트 스위트 (NIST, AIS31 등) 를 실행하기 전에, $C_2 < 0.01$과 $|Z| < 2$를 동시에 만족하는지 확인함으로써 설계 품질을 신속하게 검증할 수 있습니다. 이는 평가 시간을 단축하고 설계 결함을 조기에 발견하는 데 기여합니다.
• 이론과 실습의 연결: 조합론적 측정치 ($C_k$) 와 확률론적 모델 (마르코프 체인) 을 연결하여 TRNG 평가의 이론적 토대를 강화했습니다.
• 향후 과제: 아키텍처별 더 엄격한 상관관계 경계 (generic 경계보다 좁은) 를 탐구하고, 다중 소스 XOR 누적 및 고차 상관관계로 프레임워크를 확장하는 것이 향후 연구 방향입니다.

이 논문은 링 발진기 기반 TRNG 의 품질 평가에 있어 상관관계 분석과 통계적 테스트를 통합한 새로운 표준을 제시했다는 점에서 중요한 의의를 가집니다.