Lapin: an efficient authentication protocol based on ring-LPN. (English) Zbl 1282.94078

Canteaut, Anne (ed.), Fast software encryption. 19th international workshop, FSE 2012, Washington, DC, USA, March 19–21, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34046-8/pbk). Lecture Notes in Computer Science 7549, 346-365 (2012).
Summary: We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt 2011 [E. Kiltz et al., Lect. Notes Comput. Sci. 6632, 7–26 (2011; Zbl 1281.94083)], and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices.
Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt’11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES.
For the entire collection see [Zbl 1251.68005].


94A62 Authentication, digital signatures and secret sharing
68P25 Data encryption (aspects in computer science)


Zbl 1281.94083
Full Text: DOI