Lapin: An efficient authentication protocol based on Ring-LPN

Abstract : 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'11 (Kiltz et al.), 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.
Type de document :
Communication dans un congrès
Anne Canteaut. Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012, Mar 2012, Washington DC, United States. Springer, 7549, pp.346-365, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-34047-5_20〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00864307
Contributeur : Vadim Lyubashevsky <>
Soumis le : vendredi 20 septembre 2013 - 17:38:26
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Stephan Heyse, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, Krzysztof Pietrzak. Lapin: An efficient authentication protocol based on Ring-LPN. Anne Canteaut. Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012, Mar 2012, Washington DC, United States. Springer, 7549, pp.346-365, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-34047-5_20〉. 〈hal-00864307〉

Partager

Métriques

Consultations de la notice

251