Paper 2017/1111

Fuzzy Password-Authenticated Key Exchange

Pierre-Alain Dupont
Julia Hesse, IBM Research Europe - Zurich
David Pointcheval, ENS Paris
Leonid Reyzin, Boston University
Sophia Yakoubov, Aarhus University
Abstract

Consider key agreement by two parties who start out knowing a common secret (which we refer to as “pass-string”, a generalization of “password”), but face two complications: (1) the pass-string may come from a low-entropy distribution, and (2) the two parties’ copies of the pass-string may have some noise, and thus not match exactly. We provide the first efficient and general solutions to this problem that enable, for example, key agreement based on commonly used biometrics such as iris scans. The problem of key agreement with each of these complications individually has been well studied in literature. Key agreement from low-entropy shared pass-strings is achieved by password-authenticated key exchange (PAKE), and key agreement from noisy but high-entropy shared pass-strings is achieved by information-reconciliation protocols as long as the two secrets are “close enough.” However, the problem of key agreement from noisy low-entropy pass-strings has never been studied. We introduce (universally composable) fuzzy password-authenticated key exchange (fPAKE), which solves exactly this problem. fPAKE does not have any entropy requirements for the pass-strings, and enables secure key agreement as long as the two pass-strings are “close” for some notion of closeness. We also give two constructions. The first construction achieves our fPAKE definition for any (efficiently computable) notion of closeness, including those that could not be handled before even in the high-entropy setting. It uses Yao’s garbled circuits in a way that is only two times more costly than their use against semi-honest adversaries, but that guarantees security against malicious adversaries. The second construction is more efficient, but achieves our fPAKE definition only for pass-strings with low Hamming distance. It builds on very simple primitives: robust secret sharing and PAKE.

Note: Added link to the patched protocol.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
Keywords
Authenticated Key ExchangePAKEHamming DistanceError Correcting CodesYao’s Garbled Circuits
Contact author(s)
juliahesse2 @ gmail com
david pointcheval @ ens fr
reyzin @ bu edu
sophia yakoubov @ cs au dk
History
2023-09-25: last of 3 revisions
2017-11-20: received
See all versions
Short URL
https://ia.cr/2017/1111
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1111,
      author = {Pierre-Alain Dupont and Julia Hesse and David Pointcheval and Leonid Reyzin and Sophia Yakoubov},
      title = {Fuzzy Password-Authenticated Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1111},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1111}},
      url = {https://eprint.iacr.org/2017/1111}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.