Paper 2020/1043

Minimal Symmetric PAKE and 1-out-of-N OT from Programmable-Once Public Functions

Ian McQuoid, Mike Rosulek, and Lawrence Roy

Abstract

Symmetric password-authenticated key exchange (sPAKE) can be seen as an extension of traditional key exchange where two parties agree on a shared key if and only if they share a common secret (possibly low-entropy) password. We present the first sPAKE protocol to simultaneously achieve the following properties: - only two exponentiations per party, the same as plain unauthenticated Diffie-Hellman key agreement (and likely optimal); - optimal round complexity: a single flow (one message from each party that can be sent in parallel) to achieve implicit authentication, or two flows to achieve explicit mutual authentication; - security in the random oracle model, rather than ideal cipher or generic group model; - UC security, rather than game-based. Our protocol is a generalization of the seminal EKE protocol of Bellovin & Merritt (S&P 1992). We also present a UC-secure 1-out-of-$N$ oblivious transfer (OT) protocol, for random payloads. Its communication complexity is independent of $N$, meaning that $N$ can even be exponential in the security parameter. Such a protocol can also be considered a kind of oblivious PRF (OPRF). Our protocol improves over the leading UC-secure 1-out-of-$N$ OT construction of Masny & Rindal (CCS 2019) for all $N>2$, and has essentially the same cost for $N=2$. The new technique underlying these results is a primitive we call programmable-once public function (POPF). Intuitively, a POPF is a function whose output can be programmed by one party on exactly one point. All other outputs of the function are outside of any party's control, in a provable sense.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM CCS 2020
DOI
10.1145/3372297.3417870
Keywords
password-authenticated key exchangeoblivious transfer
Contact author(s)
rosulekm @ eecs oregonstate edu
History
2020-08-28: received
Short URL
https://ia.cr/2020/1043
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1043,
      author = {Ian McQuoid and Mike Rosulek and Lawrence Roy},
      title = {Minimal Symmetric PAKE and 1-out-of-N OT from Programmable-Once Public Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1043},
      year = {2020},
      doi = {10.1145/3372297.3417870},
      note = {\url{https://eprint.iacr.org/2020/1043}},
      url = {https://eprint.iacr.org/2020/1043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.