Lec 5: Ideal Functionality for PAKE

Game-based security definition for PAKE

• Intuition: “only feasible attack is online guessing”
• Game-based definition formalizes this intuition
• …but how is the “end product” so gross??

​

• Lesson: game-based definitions are ill-suited for the security of many protocols where parties send messages back and forth

​

• Can we have a new paradigm of security definition which
• Describes what an adversary should be able to do (ideal world) → today
• Defines security as “any adversary against the protocol has no more power than the ideal adversary” → next time

“Ideal world”

ideal functionality

What can adversary do in PAKE?

• “Only feasible attack is online guessing”
• Each (active) instance has 3 possible states:
• Not attacked → call it “fresh”
• Successfully attacked → call it “compromised”
• Unsuccessfully attacked → call it “interrupted”
• Instance’s session key depends on its state
• Fresh, counterparty also fresh → equal, uniformly random key
• Fresh, counterparty attacked → uniformly random key (independent of everything else)
• Interrupted → uniformly random key (independent of everything else)
• Compromised → all security guarantee (for this instance) lost

Caveats

2 fundamental questions unanswered…

• The “ideal world” clearly needs the concept of “session”. How is this defined?
• Circumvented in game-based definition
• In game-based definition, adversary can reveal an instance’s session key. Here it cannot. How come?

Session ID

Environment

Ideal world (corrected)

Summary

• Security definition via an “ideal world”
• Ideal adversary can do 1 online attack per instance (TestPwd)
• Party’s session key (NewKey) depends on
• Whether it is attacked
• If so, whether the attack used the correct password (compromised) or not (interrupted)
• If not (fresh), whether its counterparty has been attacked, and whether the 2 passwords match
• Formalizes “adversary can do 1 online attack per instance” intuition better than game-based definition
• Remaining part of definition: need to somehow define “real PAKE protocol is as secure as ideal world”

References

• [CHK+05] Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, and Philip MacKenzie. Universally Composable Password-Based Key Exchange. In EUROCRYPT 2005.
• [DHP+18] Pierre-Alain Dupont, Julia Hesse, David Pointcheval, Leonid Reyzin, and Sophia Yakoubov. Fuzzy Password-Authenticated Key Exchange. In EUROCRYPT 2018.
• [ABB+21] Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanislaw Jarecki, Jonathan Katz, and Jiayu Xu. Universally Composable Relaxed Password Authenticated Key Exchange. In CRYPTO 2021.

• [BGHJ24] Manuel Barbosa, Kai Gellert, Julia Hesse, and Stanislaw Jarecki. Bare PAKE: Universally Composable Key Exchange from just Passwords. In CRYPTO 2024.