--- _id: '2049' abstract: - lang: eng text: "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.\r\n\r\nPerformance-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.\r\n" acknowledgement: "Supported by the European Research Council / ERC Starting Grant (259668- PSPC)\r\nWe would like to thank the anonymous referees of this confer- ence and those of the ECRYPT Workshop on Lightweight Cryptography for very useful comments, and in particular for the suggestion that the scheme is somewhat vulnerable to a man-in-the-middle attack whenever an adversary observes two reader challenges that are the same. We hope that the attack we described in Appendix A corresponds to what the reviewer had in mind. We also thank Tanja Lange for pointing us to the pa- per of [Kir11] and for discussions of some of her recent work. " alternative_title: - LNCS author: - first_name: Stefan full_name: Heyse, Stefan last_name: Heyse - first_name: Eike full_name: Kiltz, Eike last_name: Kiltz - first_name: Vadim full_name: Lyubashevsky, Vadim last_name: Lyubashevsky - first_name: Christof full_name: Paar, Christof last_name: Paar - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Heyse S, Kiltz E, Lyubashevsky V, Paar C, Pietrzak KZ. Lapin: An efficient authentication protocol based on ring-LPN. In: Conference Proceedings FSE 2012. Vol 7549. Springer; 2012:346-365. doi:10.1007/978-3-642-34047-5_20' apa: 'Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., & Pietrzak, K. Z. (2012). Lapin: An efficient authentication protocol based on ring-LPN. In Conference proceedings FSE 2012 (Vol. 7549, pp. 346–365). Washington, DC, USA: Springer. https://doi.org/10.1007/978-3-642-34047-5_20' chicago: 'Heyse, Stefan, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof Z Pietrzak. “Lapin: An Efficient Authentication Protocol Based on Ring-LPN.” In Conference Proceedings FSE 2012, 7549:346–65. Springer, 2012. https://doi.org/10.1007/978-3-642-34047-5_20.' ieee: 'S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, and K. Z. Pietrzak, “Lapin: An efficient authentication protocol based on ring-LPN,” in Conference proceedings FSE 2012, Washington, DC, USA, 2012, vol. 7549, pp. 346–365.' ista: 'Heyse S, Kiltz E, Lyubashevsky V, Paar C, Pietrzak KZ. 2012. Lapin: An efficient authentication protocol based on ring-LPN. Conference proceedings FSE 2012. FSE: Fast Software Encryption, LNCS, vol. 7549, 346–365.' mla: 'Heyse, Stefan, et al. “Lapin: An Efficient Authentication Protocol Based on Ring-LPN.” Conference Proceedings FSE 2012, vol. 7549, Springer, 2012, pp. 346–65, doi:10.1007/978-3-642-34047-5_20.' short: S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K.Z. Pietrzak, in:, Conference Proceedings FSE 2012, Springer, 2012, pp. 346–365. conference: end_date: 2012-03-21 location: Washington, DC, USA name: 'FSE: Fast Software Encryption' start_date: 2012-03-19 date_created: 2018-12-11T11:55:25Z date_published: 2012-03-01T00:00:00Z date_updated: 2021-01-12T06:54:58Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-642-34047-5_20 ec_funded: 1 intvolume: ' 7549' language: - iso: eng main_file_link: - open_access: '1' url: http://www.iacr.org/archive/fse2012/75490350/75490350.pdf month: '03' oa: 1 oa_version: Preprint page: 346 - 365 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication: ' Conference proceedings FSE 2012' publication_status: published publisher: Springer publist_id: '5002' quality_controlled: '1' scopus_import: 1 status: public title: 'Lapin: An efficient authentication protocol based on ring-LPN' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7549 year: '2012' ...