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

1. Problem Statement

The transition to Post-Quantum Cryptography (PQC) necessitates the use of hybrid encryption schemes, which combine classical algorithms (e.g., RSA) with quantum-resistant primitives (e.g., ML-KEM, BIKE, HQC) to mitigate risks during the migration period. While theoretical security proofs exist for these constructions, empirical validation of their security properties in real-world implementations remains challenging.

Specifically, verifying Indistinguishability under Chosen-Plaintext Attack (IND-CPA) is crucial. IND-CPA ensures that an adversary cannot distinguish between ciphertexts of two different plaintexts. Traditional cryptanalysis is often theoretical or computationally intensive. The authors address the need for a practical, data-driven method to empirically test whether specific PQC Key Encapsulation Mechanisms (KEMs), their hybrid combinations, and cascade symmetric encryptions leak exploitable patterns that violate IND-CPA security.

2. Methodology

The paper proposes a framework that models the IND-CPA security game as a binary classification task using Deep Neural Networks (DNNs).

A. Core Concept

• The Game: The authors simulate the IND-CPA game where a challenger encrypts either a fixed plaintext (e.g., all zeros) or a uniformly random plaintext.
• The Adversary: A DNN acts as the adversary, trained to classify ciphertexts into one of the two classes (Fixed vs. Random).
• Security Metric: If the encryption scheme is IND-CPA secure, the DNN's accuracy should not significantly exceed random guessing (50%). If the DNN achieves significantly higher accuracy, it indicates a vulnerability (a distinguishable pattern).

B. Experimental Setup

• Algorithms Tested:
  • PQC KEMs: ML-KEM (Kyber), BIKE, and HQC (NIST candidates).
  • Hybrid KEMs: Combinations of PQC KEMs with classical asymmetric ciphers (RSA-OAEP, plain RSA) and plaintext, using a provably secure combiner structure: $k = F(k_1, c) \oplus F(k_2, c)$.
  • Cascade Symmetric Encryption: Combinations of AES (CTR, CBC, ECB), ChaCha20, and DES.
• Neural Architecture: Two network sizes were tested (Small: 2 layers, 100 nodes; Big: 4 layers, 600 nodes). Inputs were raw ciphertext bytes.
• Training:
  • Loss Function: Binary Cross-Entropy (BCE).
  • Optimizer: Stochastic Gradient Descent (SGD) with Nesterov Accelerated Gradient (NAG).
  • Data: 500,000 samples per class for training, with rigorous validation and testing sets to prevent overfitting.
• Statistical Validation: Unlike previous deep learning cryptanalysis papers, this work employs two-sided binomial hypothesis testing (significance level $\alpha = 0.01$) to determine if the classifier's accuracy is statistically distinguishable from 50%.

C. Algorithmic Extensions

• Algorithm 1 (Standard): Used for standard PKE schemes (underlying the KEMs) and cascade encryption.
• Algorithm 2 (Hybrid): Specifically designed for hybrid KEMs. The input to the DNN is the concatenation of ciphertexts from two components. The classification task distinguishes between cases where the shared secrets are identical (leading to a specific XOR structure) versus independent.

3. Key Contributions

1. Empirical IND-CPA Testing for PQC: The first application of DNN-based distinguishers to the underlying PKE components of NIST-standardized PQC algorithms (ML-KEM, BIKE, HQC).
2. Novel Hybrid KEM Framework: An extension of the DNN methodology to test hybrid KEMs constructed with provably secure combiners ($k = F(k_1, c) \oplus F(k_2, c)$), validating that security holds even when one component is insecure (e.g., plain RSA).
3. Cascade Encryption Analysis: Application of the framework to symmetric cascade encryption (e.g., AES-CTR followed by AES-CBC), demonstrating that the method is generalizable beyond asymmetric cryptography.
4. Rigorous Statistical Rigor: Introduction of formal hypothesis testing (binomial tests) to validate results, moving beyond simple accuracy metrics to ensure statistical significance.

4. Results

The experiments yielded consistent results across all tested scenarios:

• Baseline Validation: The DNN achieved 100% accuracy on Plain RSA (textbook RSA), confirming the model's ability to detect known vulnerabilities. Conversely, it achieved ~50% accuracy on RSA-OAEP, confirming its security.
• PQC KEMs: For ML-KEM, BIKE, and HQC, the DNNs achieved accuracies hovering around 50% (ranging from 49.73% to 50.26%).
  • Statistical Significance: No result rejected the null hypothesis ($H_0: \pi = 0.5$) at $\alpha = 0.01$. Even the slight deviation in HQC (small network, p=0.02) was not significant in the larger network and did not constitute a practical break.
• Hybrid KEMs: Combinations of PQC KEMs with insecure components (Plain RSA, Plaintext) using the secure combiner showed no distinguishable advantage. The DNNs failed to learn patterns, maintaining ~50% accuracy. This empirically supports the theoretical guarantee that a secure combiner preserves IND-CPA if at least one component is secure.
• Cascade Encryption: All tested symmetric combinations (including those involving non-IND-CPA ciphers like AES-ECB or DES-ECB) resulted in accuracies indistinguishable from random guessing, provided at least one component was IND-CPA secure.

5. Significance and Limitations

Significance:

• Practical Validation: The study demonstrates that Deep Learning can serve as a versatile, adaptive tool for empirically validating cryptographic implementations and compositions, complementing formal mathematical proofs.
• Hybrid Security Confirmation: It provides data-driven evidence that hybrid constructions (combining PQC and classical crypto) effectively mitigate risks, as the DNN adversary could not exploit the weaker components when a secure combiner was used.
• Methodological Advance: The use of rigorous statistical testing sets a new standard for machine learning-based cryptanalysis, preventing false positives from random fluctuations.

Limitations:

• Threat Model Gap: The DNN adversary in this study operates without access to public keys or encryption oracles, unlike a full IND-CPA adversary. While the model captures fundamental structural weaknesses, it may miss attacks that rely on oracle access.
• Scope: The study focuses on specific NIST candidates and standard combiners; results may vary with different parameter sets or non-standard implementations.

Conclusion:
The paper concludes that the tested PQC algorithms, their hybrid combinations, and cascade symmetric encryptions exhibit strong IND-CPA properties under the considered DNN adversary model. The lack of exploitable patterns in the data supports the theoretical security guarantees of these constructions.