GACR ePrint

Abstract

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 combine 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+).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.

Keywords

PAKE, PQC, MLWE, KEM

Publication Information

ePrint ID: 2025/005
Date submitted: 2025-12-07
Last revised: 2025-12-07
Category: Public-key cryptography

Downloads

BibTeX Citation

@misc{gacreprint:2025/005,
    author = {Nouri Alnahawi and Alexander Wiesmaier},
    title = {NICE-PAKE and TEMPO Instantiations from MLWE Rerandomizable Splittable KEMs},
    howpublished = {GACR ePrint Archive, Paper 2025/005},
    year = {2025},
    note = {\url{https://eprint.gacr.info/2025/005}},
}