---
_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
article_processing_charge: No
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: <i>Conference Proceedings FSE 2012</i>.
    Vol 7549. Springer; 2012:346-365. doi:<a href="https://doi.org/10.1007/978-3-642-34047-5_20">10.1007/978-3-642-34047-5_20</a>'
  apa: 'Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., &#38; Pietrzak, K. Z. (2012).
    Lapin: An efficient authentication protocol based on ring-LPN. In <i>Conference
    proceedings FSE 2012</i> (Vol. 7549, pp. 346–365). Washington, DC, USA: Springer.
    <a href="https://doi.org/10.1007/978-3-642-34047-5_20">https://doi.org/10.1007/978-3-642-34047-5_20</a>'
  chicago: 'Heyse, Stefan, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof
    Z Pietrzak. “Lapin: An Efficient Authentication Protocol Based on Ring-LPN.” In
    <i>Conference Proceedings FSE 2012</i>, 7549:346–65. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-34047-5_20">https://doi.org/10.1007/978-3-642-34047-5_20</a>.'
  ieee: 'S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, and K. Z. Pietrzak, “Lapin:
    An efficient authentication protocol based on ring-LPN,” in <i>Conference proceedings
    FSE 2012</i>, 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.” <i>Conference Proceedings FSE 2012</i>, vol. 7549, Springer, 2012,
    pp. 346–65, doi:<a href="https://doi.org/10.1007/978-3-642-34047-5_20">10.1007/978-3-642-34047-5_20</a>.'
  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
das_tickbox: '1'
date_created: 2018-12-11T11:55:25Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2026-07-07T13:06:19Z
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7549
year: '2012'
...