Patents Wiki
Back to briefings
PaperCryptography

A Quantum-Resistant KEM/DEM That Doesn't Lean on a Single Assumption

Every conversation about post-quantum cryptography keeps coming back to the same nervous question. What happens on the day one of the standardized primitives breaks? NIST's August 2024 finalization of FIPS 203 (ML-KEM, the Kyber descendant) gave the field its first broadly deployed lattice-based key encapsulation mechanism. The relief was real. The anxiety is not gone. A single family of structured lattices now carries a disproportionate share of the world's encrypted key agreement.

Panja, Sharifian, Jiang, and Safavi-Naini have just posted a revised preprint that takes a different tack. Their argument: you do not have to bet the farm on a computational assumption if you can borrow a small amount of correlated randomness from the world and let information theory do most of the work.

The paper, "CCA-Secure Hybrid Encryption in Correlated Randomness Model and KEM Combiners" (arXiv:2401.00983, v2 of 24 Mar 2024), reintroduces the classical KEM/DEM composition theorem in a preprocessing model where Alice and Bob start with samples x and y from a public distribution P_XYZ, Eve sees only the side information z, and the session key k emerges from the correlations between x and y. Pair that KEM with a one-time AES DEM and you get hybrid encryption whose only computational assumption is a symmetric primitive, which doubles up cleanly against Grover's algorithm. Stack a public-key KEM beside an information-theoretic one in a combiner, and the resulting scheme stays secure as long as either leg holds.

The paper at a glance

  • arXiv ID: 2401.00983
  • Title: CCA-Secure Hybrid Encryption in Correlated Randomness Model and KEM Combiners
  • Authors: Somnath Panja, Setareh Sharifian, Shaoquan Jiang, Reihaneh Safavi-Naini
  • Institutions: University of Calgary, Intel Corporation, University of Windsor
  • Venue: arXiv preprint
  • Submission date: January 2, 2024 (v1), revised March 24, 2024 (v2)
  • Source: arXiv:2401.00983
  • Discipline: Post-quantum cryptography, hybrid encryption
  • Headline result: An information-theoretically secure KEM (iKEM) composed with a one-time AES DEM gives quantum-resistant hybrid encryption with no public-key assumption on the KEM, and a KEM combiner lets operators mix that iKEM with any public-key KEM so the system survives the failure of either component.

The Hole in the Standard Hybrid Story

The textbook KEM/DEM construction underpins almost every modern hybrid cipher. A public-key KEM produces a fresh symmetric key and encapsulates it. A symmetric DEM encrypts the actual message under that key. The ciphertext is the pair. The security reduction is clean: if the KEM is IND-CCA secure and the DEM is IND-OTCCA secure, the hybrid is IND-CCA. The catch is that the KEM's security rides entirely on a computational assumption, and that assumption is exactly what a sufficiently large quantum computer takes away. Diffie-Hellman, RSA, and most structured-lattice problems are all in the blast radius.

The community's response has been a scramble for new computational assumptions, and ML-KEM is the most successful product of that scramble. But ML-KEM is still a single family of structured lattices, and the history of cryptography is littered with assumption families that held up for a decade and then collapsed. The authors' question is more architectural. What if the KEM did not need a computational assumption at all?

Correlated Randomness, Briefly

The correlated randomness, or preprocessing, model reframes key agreement as a problem about a shared physical or protocol source. A trusted setup samples a triple (x, y, z) from a public distribution P_XYZ. Alice gets x, Bob gets y, and Eve gets the side information z. The KEM's encapsulator uses x to produce a key k and a public encapsulation c1. The decapsulator uses y and c1 to recover k. The DEM encrypts the long message under k. Eve, who sees c1, c2, and z, cannot distinguish k from uniform random.

This is the same setup that has powered information-theoretic secret key agreement for two decades, going back to Maurer's 1993 work and the follow-on body of results on i.i.d. sources, strong extractors, and secret-key capacity. The novelty here is that the framework is being used to build a KEM in the formal IND-CEA / IND-CCA sense, and then composed with a DEM, which means the entire hybrid can be lifted into the standard public-key encryption toolkit.

It is worth being explicit about what the assumption carries and what it does not. The KEM's security is information-theoretic, so an adversary with unbounded compute cannot break it as long as the source is good. The DEM is the only computationally bounded leg, and a one-time pad-style construction plus a doubling of the key length gets you Grover-secure symmetric encryption. The hybrid is therefore quantum-resistant in a way that does not depend on lattice hardness, code hardness, or any other specific problem.

Core Architecture/Flow

How the Construction Hangs Together

The paper uses pKEM = (pkem.Gen, pkem.Enc, pkem.Dec) for the generalized KEM in the correlated randomness model, iKEM for the information-theoretically secure flavor (unbounded adversary), cKEM for the computationally secure flavor, and the standard one-time symmetric encryption for the DEM.

Security games. IND-CEA models chosen-encapsulation attacks against the session key, and IND-CCA adds a chosen-ciphertext decapsulation oracle. For the iKEM, the adversary is bounded to a constant number of queries, q_e for encapsulations and q_d for decapsulations, which mirrors the practical setting where a single session produces a small, fixed number of encapsulations.

The composition theorem. Four reductions are proven, in increasing strength:

  1. IND-CEA cKEM + IND-OT DEM gives IND-CPA hybrid encryption.
  2. IND-CCA cKEM + IND-OTCCA DEM gives IND-CCA hybrid encryption.
  3. IND-q_e-CEA iKEM + IND-OT DEM gives IND-q_e-CPA hybrid encryption.
  4. IND-(q_e; q_d)-CCA iKEM + IND-OTCCA DEM gives IND-(q_e; q_d)-CCA hybrid encryption.

The first two are the textbook KEM/DEM reductions, restated in the preprocessing setting. The last two are the headline. Because the iKEM is information-theoretically secure, the only computational assumption lives in the DEM, and a one-time AES-CTR with a doubled key length satisfies the requirement under Grover.

The two iKEMs. The first construction, iK_OWSWA, is a one-way secret-key agreement scheme that the authors include as a baseline, lifted from earlier Sharifian et al. work. It uses two strongly universal hash families h and h' and is IND-CEA secure against a passive eavesdropper. The second construction, iK_OWSWA-CCA, is the new contribution. It uses the same hash-based scaffolding with an additional strongly universal verification step at the decapsulator, so that an active adversary who tampers with c1 cannot learn anything new about k. The result is IND-CCA security in the bounded-query model.

Both iKEMs reduce to linear-algebraic operations over small fields. The base distribution P_XYZ can be instantiated with low-weight codes, polynomial evaluations, or finite-field arithmetic, and the strongly universal hash families are standard. Pair the CCA-secure iKEM with a one-time AES DEM and you have a fully quantum-resistant hybrid scheme.

KEM combiners. The paper also defines two combiners that let a deployment mix a public-key KEM and an iKEM. A parallel combiner runs both KEMs on independent sources and derives the session key as a function of both outputs. A sequential combiner uses the public-key KEM output to encrypt a message that, combined with the iKEM's key, yields the final session key. In both cases the combined scheme is IND-CCA as long as at least one component is IND-CCA. A deployment can run ML-KEM and an iKEM in parallel, and the resulting system survives either leg being broken.

The Claims Worth Highlighting

  • A general KEM/DEM composition theorem in the correlated randomness model, with both information-theoretic and computational security guarantees, including a CCA-secure composition that does not require a public-key assumption.
  • Two provably secure iKEMs in the i.i.d. source setting: a passive-eavesdropper-secure scheme and an active-adversary-secure scheme, both reducible to linear-algebraic operations.
  • Quantum-resistant hybrid encryption obtained by composing the CCA-secure iKEM with a one-time AES DEM, with the symmetric primitive as the only computational assumption.
  • KEM combiners that mix a public-key KEM and an iKEM, with security retained as long as one component holds, applicable to the post-quantum hybrid TLS handshakes that are now being deployed.
  • A bounded-query security model for iKEMs that fits the practical setting of short sessions and small numbers of encapsulations, where the typical-set size of the source is the main security parameter.

Why This Lands in November 2024

The paper arrives at a moment when the cryptographic community is, for the first time, running a quantum-vulnerable protocol stack alongside a quantum-resistant one and trying to figure out how to glue them together. ML-KEM is now the default KEM in the post-quantum suites, and the major TLS 1.3 drafts that pair classical KEMs with ML-KEM follow the hybrid pattern the combiner result formalizes. The KEM-combiner theorem gives operators a way to add a third, information-theoretic leg to that hybrid, hedging against any single primitive being broken. The iKEM construction gives them a concrete primitive to plug in.

There is also a quiet fit with quantum key distribution. The correlated randomness model is exactly the abstraction that QKD systems produce: Alice and Bob share a string of correlated bits with bounded leakage to Eve, and the rest of the system is classical post-processing. The paper's framework gives cryptographers a way to lift a QKD key-agreement pipeline into a full message-transmission system using only standard symmetric primitives on the receiver side. That piece is missing in many real-world QKD deployments.

Limits, Risks, and Open Ground

The results are not free, and the paper is honest about where the framework ends and the engineering begins.

  • Source of correlated randomness. The iKEMs need a shared correlated source between Alice and Bob, and that source has to come from somewhere: physical-layer secret key generation, QKD, fuzzy extractors over biometric data, or a separate preprocessing protocol. The paper does not propose a deployment pipeline for sourcing the correlated randomness. It treats that as a separate system, a reasonable architectural choice but a real practical gap.
  • Parameter tuning. The CCA-secure iKEM relies on a specific algebraic verification step whose concrete security (tightness of the reduction, exact security parameters) depends on the parameters of the strongly universal hash family and on the typical-set size of the source. The paper gives bounds. Practical tuning is left to future work.
  • Independent-failure assumption. The KEM combiners assume the two component KEMs draw on independent randomness. Correlated failures between the two KEMs, for example both legs' correlated sources being drawn from the same flawed physical process, are not formally analyzed.
  • Implementation maturity. The constructions are proofs-of-concept. There is no reference implementation, no NIST submission, and no interoperability data, so adoption is not on the immediate horizon. The paper is a framework, not a finished product.
  • Bounded-query model. The iKEM's IND-CCA security holds for a fixed, small number of adversarial queries. The bound is consistent with the practical setting of short sessions, but the iKEM is not a drop-in for protocols that expect unbounded CCA security from a single KEM.

What's Next to Watch

  • Hybrid TLS with three legs. Watch for proposals that put a public-key KEM, an iKEM, and the classical KEM in parallel, and apply the combiner reduction to argue security. The combiners in the paper give the theoretical basis. Someone needs to do the engineering.
  • QKD-plus-DEM systems. A natural follow-on is a deployment paper that wires a QKD source to an iKEM and then to a one-time AES DEM, and benchmarks the end-to-end throughput. The cryptographic side is settled. The systems side is wide open.
  • Concrete parameter sets. The bounds in the paper are asymptotic. Production deployments need concrete block sizes, field sizes, and hash family parameters for common source distributions (e.g., wireless channel reciprocity, QKD with finite key, biometric fuzzy extractors).
  • Standardization paths. ML-KEM was a decade-long process. The iKEM family is not on the NIST track today, but the correlated-randomness model is increasingly discussed in the post-quantum community, and a serious parameter-and-implementation package could move it onto a research agenda.

Sources

  • arXiv abstract page: https://arxiv.org/abs/2401.00983
  • arXiv PDF (v2, 24 Mar 2024): https://arxiv.org/pdf/2401.00983
  • arXiv HTML (v2): https://arxiv.org/html/2401.00983v2
  • DOI: https://doi.org/10.48550/arXiv.2401.00983
  • DBLP author record (Panja): https://dblp.org/pid/220/2787.html
  • Background on the classical KEM/DEM composition theorem: Cramer and Shoup, "Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack" (SIAM J. Comput., 2003); Abe, Gennaro, Kurosawa, and Shoup, "Tag-KEM/DEM: A New Framework for Hybrid Encryption and a New Analysis of Kurosawa-Desmedt KEM" (EUROCRYPT 2005 / J. Cryptology 2007).
  • Context for FIPS 203 finalization: NIST FIPS 203, "Module-Lattice-Based Key-Encapsulation Mechanism" (August 2024).
  • Background on the correlated randomness model: Maurer, "Secret Key Agreement by Public Discussion from Common Information" (IEEE Trans. Inf. Theory, 1993); Renner and Wolf, "New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction" (EUROCRYPT 2003).
  • Active IETF drafts for hybrid TLS: draft-ietf-tls-ecdhe-mlkem; draft-ietf-tls-hybrid-design.

Found this useful? Share it with a colleague or post to your team's reading list.