Evaluating PQC KEMs, Combiners, and Cascade Encryption via Adaptive IND-CPA Testing Using Deep Learning

논문 요약: 딥러닝을 활용한 적응형 IND-CPA 테스트를 통한 PQC KEM, 조합기 및 캐스케이드 암호화 평가

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

• 배경: 양자 컴퓨팅의 위협으로 인해 NIST 를 중심으로 포스트 양자 암호 (PQC) 표준화 작업이 진행 중이며, ML-KEM, SLH-DSA, ML-DSA 등이 표준화되었습니다. 현재는 기존 고전 암호와 PQC 를 결합한 하이브리드 암호화 방식이 도입되어, 한쪽 알고리즘이 깨져도 다른 쪽이 안전하면 전체 시스템이 안전하도록 위험을 분산하고 있습니다.
• 문제: 암호학적 안전성 (특히 선택 평문 공격 하의 구별 불가능성, IND-CPA) 을 이론적으로 증명하는 것은 중요하지만, 실제 구현체나 복잡한 하이브리드 구성에서 이러한 속성이 유지되는지 경험적 (Empirically) 으로 검증하는 것은 현실적으로 어렵습니다.
• 목표: 딥러닝 (Deep Learning) 을 활용하여 암호문 구별 불가능성 (IND-CPA) 을 이진 분류 문제로 모델링하고, 이를 통해 PQC 키 캡슐화 메커니즘 (KEM), 하이브리드 KEM, 그리고 캐스케이드 대칭 암호화의 안전성을 데이터 기반으로 검증하는 프레임워크를 제안하고 평가하는 것입니다.

2. 방법론 (Methodology)

연구팀은 Kim et al. [21] 의 기존 딥러닝 기반 IND-CPA 테스트 방법을 확장하여 다음과 같은 접근법을 사용했습니다.

• IND-CPA 게임의 이진 분류 모델링:

  • 기본 원리: 암호화 알고리즘이 IND-CPA 안전하다면, 암호문은 평문이 무엇인지 (예: 무작위 평문 vs 고정된 0 평문) 에 관계없이 구별할 수 없어야 합니다.
  • 학습 데이터: 두 클래스로 구성된 데이터셋을 생성합니다.
    • 클래스 0: 무작위 평문을 암호화한 암호문.
    • 클래스 1: 고정된 평문 (모든 0) 을 암호화한 암호문.
  • 모델: 심층 신경망 (DNN) 을 사용하여 이 두 클래스를 분류하도록 훈련합니다. 손실 함수로 **이진 교차 엔트로피 (Binary Cross-Entropy, BCE)**를 사용하며, SGD(Stochastic Gradient Descent) 로 최적화합니다.
  • 평가 기준: DNN 이 무작위 추측 (50% 정확도) 보다 유의미하게 높은 정확도를 보이면 해당 알고리즘은 IND-CPA 안전성이 깨진 것으로 간주합니다.

• 테스트 대상 및 시나리오:

  1. 단일 PQC KEM: ML-KEM (Kyber), BIKE, HQC 의 기반이 되는 공개키 암호 (PKE) 구성 요소를 테스트.
  2. 하이브리드 KEM: 두 개의 KEM 이나 KEM 과 고전 암호 (RSA, RSA-OAEP, 평문) 를 조합한 경우.
     • 조합 방식: $k = F(k_1, c) \oplus F(k_2, c)$ 형태의 조합기 (Combiner) 사용.
     • 입력: 두 구성 요소의 암호문을 연결 (Concatenation) 하여 DNN 에 입력.
  3. 캐스케이드 대칭 암호화: AES(CTR, CBC, ECB), ChaCha20, DES(EBB) 등을 서로 다른 순서로 중첩 (Cascade) 하여 테스트.

• 통계적 검증:

  • 단순 정확도 비교를 넘어, **양측 이항 검정 (Two-sided binomial test)**을 사용하여 귀무가설 ($H_0$: 정확도 = 0.5) 을 기각할 수 있는지 확인.
  • 유의수준 $\alpha = 0.01$을 적용하여 통계적으로 유의미한 우위가 있는지 판단.

3. 주요 기여 (Key Contributions)

1. PQC KEM 의 경험적 검증: ML-KEM, BIKE, HQC 등 NIST 표준화 후보 및 선정 알고리즘의 기반 PKE 가 IND-CPA 안전성을 만족함을 딥러닝을 통해 실증적으로 확인.
2. 하이브리드 KEM 테스트 프레임워크 확장: $k = F(k_1, c) \oplus F(k_2, c)$ 형태의 조합기를 사용하는 하이브리드 KEM 에 대해 새로운 테스트 알고리즘 (Algorithm 2) 을 제안. 이는 PQC 와 고전 암호 (RSA 등) 의 결합뿐만 아니라, 두 개의 PQC 알고리즘 결합에도 적용 가능.
3. 캐스케이드 암호화 적용: 대칭키 암호의 캐스케이드 구성 (예: AES-CBC + AES-CTR) 에도 동일한 딥러닝 프레임워크를 적용하여 방법론의 일반성을 입증.
4. 엄격한 통계 분석: 기존 딥러닝 기반 암호 분석 연구들과 달리, p-value 를 계산하는 엄격한 가설 검정을 도입하여 결과의 신뢰성을 높임.

4. 실험 결과 (Results)

• 단일 알고리즘 테스트:

  • Plain RSA: 100% 정확도로 암호문을 완벽하게 구별 (결정론적 암호화의 취약성 확인).
  • RSA-OAEP, ML-KEM, BIKE, HQC: DNN 의 정확도가 50% 부근 (무작위 추측 수준) 이었으며, p-value 가 0.01 보다 커서 통계적으로 유의미한 우위가 없음. 이는 이론적 IND-CPA 안전성과 일치함.
  • HQC: 작은 네트워크에서 약간 높은 정확도 (50.26%) 를 보였으나 통계적으로 유의하지 않음.

• 하이브리드 KEM 테스트:

  • PQC KEM 과 RSA-OAEP, Plain RSA, 평문 등을 조합한 경우, DNN 은 모든 조합에서 무작위 추측 수준 (약 50%) 의 정확도를 보임.
  • 주요 발견: 보안하지 않은 구성 요소 (Plain RSA 또는 평문) 가 포함되어 있더라도, 안전한 조합기 (Combiner) 를 사용하면 전체 시스템의 IND-CPA 안전성이 유지됨을 확인 (이론적 보장과 일치).
  • 예외적 관찰: Plain RSA 와 평문을 조합한 경우, 이론적으로는 암호문 $c_{RSA}||m$을 통해 $m$을 복호화하여 판별 가능할 수 있으나, DNN 은 암호문 오라클 (Encryption Oracle) 접근 권한이 없으므로 이를 학습하지 못함. 이는 DNN 모델의 한계를 보여줌.

• 캐스케이드 암호화 테스트:

  • AES-CBC, CTR, ECB, ChaCha20, DES 등을 서로 조합한 17 가지 경우 모두에서 DNN 은 무작위 추측 수준 (49.74% ~ 50.27%) 의 정확도만 보임.
  • 하나라도 IND-CPA 안전한 알고리즘이 포함되면, 전체 캐스케이드 암호가 DNN 에 의해 구별되지 않음을 확인.

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

• 실용적 검증 도구: 딥러닝은 복잡한 하이브리드 암호 구성이나 실제 구현체에서 이론적 분석만으로는 파악하기 어려운 취약점 (구현 오류 등) 을 탐지할 수 있는 적응형 (Adaptive) 실용적 도구로 활용 가능.
• 하이브리드 암호의 안전성 입증: 이론적으로 "하나의 안전한 구성 요소가 있으면 전체가 안전하다"는 하이브리드 암호의 안전성 보장이, 딥러닝 기반의 경험적 테스트에서도 유효함을 입증.
• 한계 및 향후 과제: 현재 DNN 모델은 공개키나 암호문 오라클에 접근하지 못하는 제한된 위협 모델 하에서 작동합니다. 향후 암호문 오라클 접근 권한을 포함한 더 강력한 공격 모델 (Neural Classifier) 을 개발하여 테스트 범위를 확장할 필요가 있음.

요약하자면, 이 논문은 딥러닝을 활용하여 차세대 암호 표준 (PQC) 과 하이브리드 암호 시스템의 IND-CPA 안전성을 데이터 기반으로 검증하는 새로운 패러다임을 제시하며, 다양한 알고리즘 조합에서 이론적 안전성이 경험적으로도 유지됨을 통계적으로 입증했습니다.