IACR News item: 02 December 2025
Nouri Alnahawi, Alexander Wiesmaier
ePrint Report
We propose two novel instantiations for the NICE-PAKE and TEMPO protocols, which were presented by Alnahawi et al. (ePrint:2024/1957), and Arriaga, Barbosa and Jarecki (ePrint:2025/1399) repectively. Our instantiations are not formally analyzed yet, but build upon known KEM security assumptions and well-studied PAKE designs. Therefore, we believe there is a great chance that a formal proof in the Universal Composability (UC) framework should also hold.
Our constructions combines three concepts: 1) Lattice KEMs with Splittable public keys of the form As+e as introduced in Arriaga et al. (AC24:ABJS), Alnahawi et al. (ePrint:2024/1957) and Arriaga et al. (ePrint:2025/1399). 2) The Programmable Only Once Function (POPF) realized as a 2-round Feistel (2F) as in McQuoid, Rosulek and Roy (CCS20:MRR) and Arriaga , Barbosa and Jarecki (ePrint:2025/231). 3) Rerandomizable KEM as introduced in Duverger et al. (CCS25:DFJ+).
Similar to the aforementioned works, our goal is to eliminate the usage of the Ideal Cipher (IC) in (O)EKE-style KEM-based PQC PAKEs, the motivation of which is adequately and extensively explained in the cited literature. Our main contribution lies within the following two aspects: 1) Mitigating malicious public key generation attacks in the NICE-PAKE construction. 2) Defining a mechanism to realize the missing group operation in the 2F public key authentication step in NoIC-PAKE. Briefly put, we utilize the rerandomization procedure of (CCS25:DFJ+) to sample a second uniform MLWE sample, which is in turn used to shift the initiator's public key forming another fresh sample that yields indistinguishable from uniform. By doing so, we assume that we can enhance the security of NICE-PAKE to withstand a certain class of attacks, and reduce the computational complexity of the 2F instantiation relying on obfuscation in the OQUAKE variant of the 2F PAKE, which was introduced by Vos et al. (ePrint:2025/1343).
Obviously, we cannot ascertain the security of our proposed constructions without conducting a complete and thorough formal analysis. Hence, remaining open questions and future work include defining an indistinguishable UC simulator in the ideal UC world that is also capable of extracting adversarial password guesses. Further, we need to identify the concrete KEM properties required to prove security in UC via the common game-hopping reductionist proof approach.
Our constructions combines three concepts: 1) Lattice KEMs with Splittable public keys of the form As+e as introduced in Arriaga et al. (AC24:ABJS), Alnahawi et al. (ePrint:2024/1957) and Arriaga et al. (ePrint:2025/1399). 2) The Programmable Only Once Function (POPF) realized as a 2-round Feistel (2F) as in McQuoid, Rosulek and Roy (CCS20:MRR) and Arriaga , Barbosa and Jarecki (ePrint:2025/231). 3) Rerandomizable KEM as introduced in Duverger et al. (CCS25:DFJ+).
Similar to the aforementioned works, our goal is to eliminate the usage of the Ideal Cipher (IC) in (O)EKE-style KEM-based PQC PAKEs, the motivation of which is adequately and extensively explained in the cited literature. Our main contribution lies within the following two aspects: 1) Mitigating malicious public key generation attacks in the NICE-PAKE construction. 2) Defining a mechanism to realize the missing group operation in the 2F public key authentication step in NoIC-PAKE. Briefly put, we utilize the rerandomization procedure of (CCS25:DFJ+) to sample a second uniform MLWE sample, which is in turn used to shift the initiator's public key forming another fresh sample that yields indistinguishable from uniform. By doing so, we assume that we can enhance the security of NICE-PAKE to withstand a certain class of attacks, and reduce the computational complexity of the 2F instantiation relying on obfuscation in the OQUAKE variant of the 2F PAKE, which was introduced by Vos et al. (ePrint:2025/1343).
Obviously, we cannot ascertain the security of our proposed constructions without conducting a complete and thorough formal analysis. Hence, remaining open questions and future work include defining an indistinguishable UC simulator in the ideal UC world that is also capable of extracting adversarial password guesses. Further, we need to identify the concrete KEM properties required to prove security in UC via the common game-hopping reductionist proof approach.
Additional news items may be found on the IACR news page.