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
-
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}
}
