Cryptology ePrint Archive: Report 2015/1220

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

David Cash and 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.

Category / Keywords: secret-key cryptography / Secret-key authentication, Man-in-the-Middle security, LPN, Field LPN.

Original Publication (in the same form): IACR-TCC-2016

Date: received 21 Dec 2015, last revised 21 Dec 2015

Contact author: tessaro at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Version: 20151223:205921 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]