Separate Your Domains: NIST PQC KEMs and Oracle Cloning

Mihir Bellare Y, Hannah Davis, Felix Günther

Keita Xagawa

JiaYv An, Yankun Gao, Lei Han

Driven by advances in the standardization of NIST’s Post-Quantum Cryptography (PQC) algorithms, research on constructing Password Authenticated Key Exchange (PAKE) protocols using Key Encapsulation Mechanisms (KEMs) has gained considerable attention. Several PAKE protocols have established precise security requirements for the underlying KEM. Arriaga et al. introduced a PAKE protocol called CHIC, which requires the KEM to achieve anonymity under plaintext-checkable attacks (ANO-1PCA). An anonymous KEM does not leak any information about which public key was used for encryption. It protects the identities and privacy of participants and is critical in preventing identity-guessing attacks, therefore, anonymity is also called key-privacy. The anonymity of NIST PQC Round-3 candidates has recently been analyzed, some of which satisfied ANO-CCA.Huguenin-Dumittan and Vaudenay proposed two efficient constructions, TCHand TH, to create KEM from public-key encryption (PKE) schemes. Jiang et al. introduced TRHbased on TH. These constructions can transform any OW-CPA PKE into an IND-qCCA KEM efficiently and avoid re-encryption. However, prior to this work, no research has been conducted to determine whether these constructions preserve or lift anonymity.In this paper, we proved that for any OW-CPA, DS-IND PKE, the construction KEMRH= TRH[PKE,H] achieves ANO1-CCA in the quantum random oracle model (QROM). We then construct a KEM called KyberRH, and provide an algorithm for the CHIC protocol using KyberRH.

Muhamad Akrom, Supriadi Rustad, Guruh Fajar Shidik +3 more

Bilal El Issaoui

MRS-AUTH RESEARCH PHASE/ASSUMPTIONS — NO NIST/IETF CERTIFICATION post-quantum security with a novel cryptographic layer derived from the theory of linear Diophantine representation systems. The construction combines three components: (1) a post-quantum KEM (Kyber) for key encapsulation, (2) an MRS chain, a deterministic structured traversal of the solution space of N = 19A + 9B — as an entropy source fed through HKDF modelled as a Random Oracle. And (3) AES-GCM for authenticated encryption. The session key is formed as the XOR of the KEM-derived key and the MRS-derived master key. The central mathematical insight is that the minimal coefficient A₀ of any representation N = 19A + 9B equals the digital root dr(N), a consequence of the congruence 19 ≡ 1 (mod 9). This property is scale-invariant and extends canonically to three-dimensional systems pA + qB + rC under mild divisibility conditions. The resulting MRS chain is fully deterministic yet cryptographically opaque after HKDF compression, bridging structural predictability with entropic security. The MRS-AUTH-KEM achieves IND-CCA2 security under three standard assumptions: IND-CCA2 security of the underlying KEM, the Random Oracle Model for HKDF, and IND-CPA security of AES-GCM. The security reduction proceeds via a four-game hybrid argument, formalized in EasyCrypt. The adversary's advantage is bounded by 2 · negl(λ), and breaking the scheme requires simultaneously defeating both Kyber and the MRS chain providing a concrete, quantifiable security margin beyond existing hybrid constructions. Domain separation between HKDF contexts prevents cross-context collisions, and the scale-invariance of the digital root ensures that the anchor A₀ remains stable under all system extensions. RESEARCH PHASE — NO NIST/IETF CERTIFICATION

Emanuel H. Knill