NICE-PAKE: On the Security of KEM-Based PAKE Constructions without Ideal Ciphers

Nouri Alnahawi; Jacob Alperin-Sheriff; Daniel Apon; Gareth T. Davies; Alexander Wiesmaier

Paper 2024/1957

NICE-PAKE: On the Security of KEM-Based PAKE Constructions without Ideal Ciphers

Nouri Alnahawi

, Hochschule Darmstadt

Jacob Alperin-Sheriff, Independent Researcher

Daniel Apon, The MITRE Corporation

Gareth T. Davies, NXP Semiconductors

Alexander Wiesmaier, Hochschule Darmstadt

Abstract

Password Authenticated Key Exchange (PAKE) is a fundamental cryptographic component that allows two parties to establish a shared key using only (potentially low-entropy) passwords. The interest in realizing generic KEM-based PAKEs has increased significantly in the last few years as part of the global migration effort to quantum-resistant cryptography. One such PAKE is the CAKE protocol, proposed by Beguinet et al. (ACNS ’23). However, despite its simple design based on the well-studied EKE protocol both CAKE and its variant OCAKE do not fully protect against quantum adversaries, as they rely on the Ideal Cipher (IC) model. Related and follow-up works, although touching on that issue, still rely on an IC. Considering the lack of a quantum IC model and the difficulty of using the classical IC to achieve secure instantiations on public keys in general and PQC in particular, we set out to eliminate it from PAKE design. In this paper, we present the No IC Encryption (NICE)-PAKE, a (semi)-generic symmetric PAKE framework providing a quantum-safe alternative for the IC, utilizing simpler cryptographic components for the authentication step. To give a formal proof for our construction, we introduce the notions of A-Part Secrecy (A-SEC-CCA), Splittable Collision Freeness (A-CFR-CCA) and Public Key Uniformity (SPLIT-PKU) for splittable LWE KEMs. We show the relation of the former to the Non-uniform LWE and the Weak Hint LWE assumptions, as well as its application to ring and module LWE. Notably, this side quest led to some surprising discoveries: the new notion is not directly interchangeable between the LWE variants, at least not in a straightforward manner. Further, we show how to obtain a secure PAKE from our construction with concrete parameter choices for both FrodoKEM and CRYSTALS-Kyber. We also address fundamental issues with common IC usage and identify differences between lattice KEMs (and their public keys) regarding their suitability for generic post-quantum PAKEs.

Note: Revised notation and updated authors and affiliations.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: PAKE Key Encapsulation Mechanism Post-Quantum Cryptography Learning with Errors Ideal Cipher
Contact author(s): nouri alnahawi @ h-da de
jacobmas @ gmail com
crypto @ mitre org
gareththomas davies @ nxp com
alexander wiesmaier @ h-da de
History: 2025-02-15: last of 3 revisions; 2024-12-03: received; See all versions
Short URL: https://ia.cr/2024/1957
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1957,
      author = {Nouri Alnahawi and Jacob Alperin-Sheriff and Daniel Apon and Gareth T. Davies and Alexander Wiesmaier},
      title = {{NICE}-{PAKE}: On the Security of {KEM}-Based {PAKE} Constructions without Ideal Ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1957},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1957}
}