Mon, 23 Nov 2026 13:00 On the UC-(In)Security of PAKE Protocols Without the Random Oracle Model by Naman Kumar (IRIF, CNRS, Université Paris Cité)

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic key, where the only information shared in advance is a low-entropy password. The first efficient PAKE protocol whose security does not rely on the random oracle model is the one by Katz, Ostrovsky and Yung (KOY, EUROCRYPT 2001). Unfortunately, the KOY protocol has only been proven secure in the game-based setting, and it is unclear whether KOY is secure in the stronger Universal Composability (UC) framework, which is the current security standard for PAKE.

In this work, we present a thorough study of the UC-security of KOY. Our contributions are twofold:

  1. We formally prove that the KOY protocol is not UC-secure;
  2. We then show that the UC-security of KOY holds in the Algebraic Group Model, under the Decisional Square Diffie-Hellman (DSDH) assumption.

Overall, we characterize the exact conditions under which KOY is UC-secure. Interestingly, the DSDH assumption is stronger than DDH under which KOY can be proven game-based secure, which reveals some subtle gaps between the two PAKE security notions that have never been studied.

Speaker Bio: ⯆

I am a second-year PhD Student at the Institut de recherche en informatique fondamentale in Paris, supervised by Geoffroy Couteau. My work focuses on both theoretical constructions of primitives like MPC, PAKE and Threshold Signatures, along with analysis of concrete cryptographic protocols. Previously I have also held positions at NTT Research and Silence Laboratories, and my work has been showcased at top conferences such as CRYPTO, EUROCRYPT and TCC.

Venue: Online