Paper 2013/092

Man-in-the-Middle Secure Authentication Schemes from LPN and Weak PRFs

Vadim Lyubashevsky and Daniel Masny

Abstract

We show how to construct, from any weak pseudorandom function, a 3-round symmetric-key authentication protocol that is secure against man-in-the-middle attacks. The construction is very efficient, requiring both the secret key and communication size to be only 3n bits long. Our techniques also extend to certain classes of randomized weak-PRFs, chiefly among which are those based on the classical LPN problem and its more efficient variants such as Toeplitz-LPN and Ring-LPN. Building a man-in-the-middle secure authentication scheme from any weak-PRF resolves a problem left open by Dodis et al. (Eurocrypt 2012), while building a man-in-the-middle secure scheme based on any variant of the LPN problem solves the main open question in a long line of research aimed at constructing a practical light-weight authentication scheme based on learning problems, which began with the work of Hopper and Blum (Asiacrypt 2001).

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
authentication schemesLPNHB authenticationweak-PRFs
Contact author(s)
lyubash @ di ens fr
History
2013-03-11: last of 2 revisions
2013-02-20: received
See all versions
Short URL
https://ia.cr/2013/092
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/092,
      author = {Vadim Lyubashevsky and Daniel Masny},
      title = {Man-in-the-Middle Secure Authentication Schemes from {LPN} and Weak {PRFs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/092},
      year = {2013},
      url = {https://eprint.iacr.org/2013/092}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.