Two-Round Man-in-the-Middle Security from LPN

David Cash, Eike Kiltz, and Stefano Tessaro

Abstract

Secret-key authentication protocols have recently received a considerable amount of attention, and a long line of research has been devoted to devising efficient protocols with security based on the hardness of the learning-parity with noise (LPN) problem, with the goal of achieving low communication and round complexities, as well as highest possible security guarantees. In this paper, we construct 2-round authentication protocols that are secure against sequential man-in-the-middle (MIM) attacks with tight reductions to LPN, Field-LPN, or other problems. The best prior protocols had either loose reductions and required 3 rounds (Lyubashevsky and Masny, CRYPTO'13) or had a much larger key (Kiltz et al., EUROCRYPT'11 and Dodis et al., EUROCRYPT'12). Our constructions follow from a new generic deterministic and round-preserving transformation enhancing actively-secure protocols of a special form to be sequentially MIM-secure while only adding a limited amount of key material and computation.

Available format(s)
Category
Secret-key cryptography
Publication info
Keywords
Secret-key authenticationMan-in-the-Middle securityLPNField LPN.
Contact author(s)
tessaro @ cs ucsb edu
History
Short URL
https://ia.cr/2015/1220

CC BY

BibTeX

@misc{cryptoeprint:2015/1220,
author = {David Cash and Eike Kiltz and Stefano Tessaro},
title = {Two-Round Man-in-the-Middle Security from LPN},
howpublished = {Cryptology ePrint Archive, Paper 2015/1220},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/1220}},
url = {https://eprint.iacr.org/2015/1220}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.