Empirical Ciphertext Distinguishability Testing of KEMs and Hybrid Encryption via Deep Learning

summary

The gist

Ensuring ciphertext indistinguishability is fundamental to cryptographic security, but empirically validating this property in real implementations and hybrid settings presents practical challenges…

In short

This research uses deep neural networks to empirically test ciphertext indistinguishability (IND-CPA) for Post-Quantum Cryptography (PQC) Key Encapsulation Mechanisms (KEMs). By training models to distinguish between random and fixed plaintexts, the study validates the security of ML-KEM, BIKE, and HQC. The findings confirm that no algorithm or hybrid construction shows a significant advantage over random guessing under the tested deep learning adversary model.

Key concepts

IND-CPA Game
This is a cryptographic game where an attacker tries to distinguish between two types of ciphertexts: one encrypted with a truly random message and another encrypted with a fixed, specific message. The goal is to prove that the ciphertext looks random, making it impossible for an attacker to tell the difference.
DNN-based Modeling
The paper uses Deep Neural Networks (DNNs) as a tool to model this IND-CPA game. A DNN is trained on labeled data—ciphertexts known to come from random messages versus fixed messages—to learn patterns that might reveal weaknesses in the underlying encryption scheme.
Hybrid KEM Combiner
This refers to combining two separate KEM components, $k = F(k1, c) ext{ ⊕ } F(k2, c)$. The DNN tests if this combination preserves security. It checks if the combined output looks random even when one component is weak or insecure.
Two-Sided Binomial Hypothesis Testing
This is a rigorous statistical method used to determine if the performance of a neural classifier (the DNN) is significantly better than random guessing. It helps confirm whether the observed accuracy gains are real or just due to chance.

Terminology used across episodes

This episode discusses

The paper

Empirical Ciphertext Distinguishability Testing of KEMs and Hybrid Encryption via Deep Learning · Read on arXiv

Simon Calderon, Niklas Johansson, Onur Günülue

Linköping University · Technische University Dortmund

We model indistinguishability under chosen-plaintext attack (IND-CPA) games as binary classification tasks for deep neural networks (DNNs). We apply this methodology to the public-key encryption (PKE) schemes used to construct PQC key encapsulation mechanisms (KEMs) such as ML-KEM and HQC, and to cascaded symmetric algorithms, demonstrating methodological generality. Moreover, we present a novel extension of this approach to empirical distinguishability testing of hybrid KEMs. For IND-CPA-secure schemes and their combinations, no DNN achieves accuracy significantly different from random guessing (measured via Bonferroni-corrected binomial tests), consistent with theoretical security guarantees. For insecure schemes, such as plain RSA, AES-CTR and AES-CBC with IV or counter reuse, or RC4, the DNNs classify the ciphertexts better than random guessing. Thus, this framework is shown to serve as a practical, scheme-agnostic tool for flagging distinguishable ciphertexts in both individual and composed constructions.

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "Empirical Ciphertext Distinguishability Testing of KEMs and Hybrid Encryption via Deep Learning".

Elias: Here's the gist of the paper. Ensuring ciphertext indistinguishability is fundamental to cryptographic security, but empirically validating this property in real implementations and hybrid settings presents practical challenges <ref:2604.06942#pg2>.

Nadia: By modeling indistinguishability under chosen-plaintext attack (IND-CPA) games as binary classification tasks and training on labeled ciphertext data with binary cross-entropy loss, we study deep neural network (DNN) distinguishers for ciphertext indistinguishability <ref:2604.06942#pg4>.

Elias: We apply this methodology to PQC key encapsulation mechanisms (KEMs) <ref:2604.06942#pg4>.

Nadia: The main contributions of this work include: 1.

Title and authors: Nadia: To get into the details of this paper, we have to look at how they frame their approach in the title and who is behind it. They're testing KEMs and hybrid encryption using deep learning. It’s a direct connection between modern PQC constructions and machine learning techniques.

Elias: And those authors, Simon Calderon, Niklas Johansson, and Onur Günlü, bring different expertise to the table—one focused on the algorithms themselves, another on proofs and parameters for those algorithms, and one who brings in a perspective on measurement research.

Priya: It’s interesting how they combine these fields because we always need to know if a new construction actually holds up when you look at it through an empirical lens rather than just pure mathematics.

Nadia: They are essentially using this DNN modeling of the IND-CPA game to empirically test the IND-CPA properties of the underlying public key encryption schemes they study, specifically ML-KEM, BIKE, and HQC.

Elias: And what's a real point for us is that they don't just stop at testing individual KEMs; they extend this methodology to test hybridized KEMs as well. This moves the research into a more complex area where combining different primitives matters.

Priya: So it’s about checking security inheritance when you mix things up, which is something we deal with a lot in privacy and measurement studies when looking at composite systems.

Nadia: Right, and their main contribution is presenting this novel extension to test these hybridized KEMs where the construction uses a provably secure combiner of the form k equals F of k1 c XOR F of k2 c, which is quite specific.

Elias: That combination structure, where you take two shared secrets from component KEMs and combine them using XOR with some function F applied to the concatenated ciphertext c, that's a key focus for them. It tests if the resulting shared secret k is still secure under this model.

The paper's summary: Nadia: So what they summarize is that their DNN framework complements formal security analysis by providing a practical tool to evaluate indistinguishability and find potential weaknesses in both implementations and composed constructions. It’s meant to be an empirical supplement to the math.

Elias: They detail their main contributions, starting with using the DNN-based modeling of the IND-CPA game to test individual PQC KEMs like ML-KEM, BIKE, and HQC. That’s testing the security of those standalone components.

Priya: I'm curious about how they handle the data for this training part; it involves training a DNN to distinguish between encryptions of uniformly random plaintexts and encryptions of a fixed plaintext, like all zeros. It’s a standard setup but applied here for security testing.

Nadia: That’s right, they train each DNN using stochastic gradient descent with binary cross-entropy loss on this labeled ciphertext data. They are looking at whether the network can tell the difference between random and fixed inputs based on the ciphertext alone.

Elias: The summary also highlights their extension to test hybrid KEMs, where they input a concatenation of the ciphertext outputs from both components when testing that specific combiner structure we talked about earlier.

Priya: So when you look at hybrid systems, they are feeding the network two parts of the ciphertext and checking if those parts decrypt or decapsulate to the same underlying value or two independent values. It’s a way to check for security inheritance in that specific combination.

The paper's improvements: Nadia: They suggest several ways they improve things, focusing on extending the testing beyond just individual KEMs and into those more complex hybrid scenarios we discussed.

Elias: One major extension is precisely what they present: allowing the testing of hybridized KEMs constructed with that provably secure combiner structure, k equals F of k1 c XOR F of k2 c. It tests security when you mix any KEM with any asymmetric cipher in this way.

Priya: And they also demonstrate the generality by applying their deep learning-based constructions to other hybridized scenarios, such as cascade symmetric encryption, showing that it works beyond just standard KEM combinations.

Nadia: That cascade symmetric encryption testing shows they can apply this methodology to other complex composite constructions too, proving the method has some methodological generality. It’s not just limited to KEM mixing.

Elias: And they also introduce a rigorous statistical analysis for their experiments, moving beyond what you might see in typical deep learning papers. They use two-sided binomial hypothesis testing to determine whether the neural binary classifiers actually gain a nonnegligible advantage over random guessing.

Priya: That statistical rigor is important because it tells us if the observed accuracy improvement is anything meaningful or just noise, and they show that even when an insecure component algorithm like plain RSA is used, the accuracies stay close to fifty percent.

Conclusion: Nadia: So wrapping up the paper Empirical Ciphertext Distinguishability Testing of KEMs and Hybrid Encryption via Deep Learning. They conclude that no algorithm or combination of algorithms demonstrated a significant advantage when tested against this DNN adversary model.

Elias: This means, according to their rigorous statistical analysis using two-sided binomial tests with a significance level alpha equals zero point zero one, there’s no evidence of any exploitable patterns under the considered deep learning adversary model. It aligns with the theoretical guarantees that hybrids including at least one IND-CPA secure component preserve indistinguishability.

Priya: I think what’s important for us is that this method provides an adaptive, practical way to validate indistinguishability in more general settings, which complements traditional analytical security analysis. It gives us a data-driven way to check implementations and compositions.

Nadia: They also point out some limitations of using this DNN framework because the neural classifier doesn't have access to public keys or encryption oracles, which limits the types of attack vectors it can capture directly.

Elias: That’s a fair caveat; while it captures fundamental aspects of the IND-CPA game, if you want to model attacks that require access to those external resources, this specific DNN modeling has its limits. It's an empirical estimator for real-world validation, not a complete security proof in itself.

Priya: So the paper provides a way to use deep learning as an adaptive, practical estimator for indistinguishability in more general IND-CPA settings and helps us validate implementations and compositions empirically. That’s the core value here.

More episodes

← Home