---
_id: '3279'
abstract:
- lang: eng
  text: "We show a hardness-preserving construction of a PRF from any length doubling
    PRG which improves upon known constructions whenever we can put a non-trivial
    upper bound q on the number of queries to the PRF. Our construction requires only
    O(logq) invocations to the underlying PRG with each query. In comparison, the
    number of invocations by the best previous hardness-preserving construction (GGM
    using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting
    from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially
    secure if queried at most q = exp(√n)times and where each invocation of the PRF
    requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n)
    required by known constructions. \r\n"
acknowledgement: Supported by the European Research Council under the European Union’s
  Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)
alternative_title:
- LNCS
author:
- first_name: Abhishek
  full_name: Jain, Abhishek
  last_name: Jain
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Aris
  full_name: Tentes, Aris
  last_name: Tentes
citation:
  ama: 'Jain A, Pietrzak KZ, Tentes A. Hardness preserving constructions of pseudorandom
    functions. In: Vol 7194. Springer; 2012:369-382. doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_21">10.1007/978-3-642-28914-9_21</a>'
  apa: 'Jain, A., Pietrzak, K. Z., &#38; Tentes, A. (2012). Hardness preserving constructions
    of pseudorandom functions (Vol. 7194, pp. 369–382). Presented at the TCC: Theory
    of Cryptography Conference, Taormina, Sicily, Italy: Springer. <a href="https://doi.org/10.1007/978-3-642-28914-9_21">https://doi.org/10.1007/978-3-642-28914-9_21</a>'
  chicago: Jain, Abhishek, Krzysztof Z Pietrzak, and Aris Tentes. “Hardness Preserving
    Constructions of Pseudorandom Functions,” 7194:369–82. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-28914-9_21">https://doi.org/10.1007/978-3-642-28914-9_21</a>.
  ieee: 'A. Jain, K. Z. Pietrzak, and A. Tentes, “Hardness preserving constructions
    of pseudorandom functions,” presented at the TCC: Theory of Cryptography Conference,
    Taormina, Sicily, Italy, 2012, vol. 7194, pp. 369–382.'
  ista: 'Jain A, Pietrzak KZ, Tentes A. 2012. Hardness preserving constructions of
    pseudorandom functions. TCC: Theory of Cryptography Conference, LNCS, vol. 7194,
    369–382.'
  mla: Jain, Abhishek, et al. <i>Hardness Preserving Constructions of Pseudorandom
    Functions</i>. Vol. 7194, Springer, 2012, pp. 369–82, doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_21">10.1007/978-3-642-28914-9_21</a>.
  short: A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.
conference:
  end_date: 2012-03-21
  location: Taormina, Sicily, Italy
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2012-03-19
date_created: 2018-12-11T12:02:25Z
date_published: 2012-05-04T00:00:00Z
date_updated: 2021-01-12T07:42:21Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-642-28914-9_21
ec_funded: 1
intvolume: '      7194'
language:
- iso: eng
main_file_link:
- url: http://www.iacr.org/archive/tcc2012/tcc2012-index.html
month: '05'
oa_version: None
page: 369 - 382
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3367'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hardness preserving constructions of pseudorandom functions
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7194
year: '2012'
...
---
_id: '3280'
abstract:
- lang: eng
  text: 'The (decisional) learning with errors problem (LWE) asks to distinguish &quot;noisy&quot;
    inner products of a secret vector with random vectors from uniform. The learning
    parities with noise problem (LPN) is the special case where the elements of the
    vectors are bits. In recent years, the LWE and LPN problems have found many applications
    in cryptography. In this paper we introduce a (seemingly) much stronger adaptive
    assumption, called &quot;subspace LWE&quot; (SLWE), where the adversary can learn
    the inner product of the secret and random vectors after they were projected into
    an adaptively and adversarially chosen subspace. We prove that, surprisingly,
    the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE
    using secrets of length d (the other direction is trivial.) This result immediately
    implies that several existing cryptosystems whose security is based on the hardness
    of the LWE/LPN problems are provably secure in a much stronger sense than anticipated.
    As an illustrative example we show that the standard way of using LPN for symmetric
    CPA secure encryption is even secure against a very powerful class of related
    key attacks. '
acknowledgement: Supported by the European Research Council under the European Union’s
  Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).
alternative_title:
- LNCS
author:
- 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: 'Pietrzak KZ. Subspace LWE. In: Vol 7194. Springer; 2012:548-563. doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_31">10.1007/978-3-642-28914-9_31</a>'
  apa: 'Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at
    the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer.
    <a href="https://doi.org/10.1007/978-3-642-28914-9_31">https://doi.org/10.1007/978-3-642-28914-9_31</a>'
  chicago: Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. <a
    href="https://doi.org/10.1007/978-3-642-28914-9_31">https://doi.org/10.1007/978-3-642-28914-9_31</a>.
  ieee: 'K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography
    Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563.'
  ista: 'Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference,
    LNCS, vol. 7194, 548–563.'
  mla: Pietrzak, Krzysztof Z. <i>Subspace LWE</i>. Vol. 7194, Springer, 2012, pp.
    548–63, doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_31">10.1007/978-3-642-28914-9_31</a>.
  short: K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.
conference:
  end_date: 2012-03-21
  location: Taormina, Sicily, Italy
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2012-03-19
date_created: 2018-12-11T12:02:26Z
date_published: 2012-05-04T00:00:00Z
date_updated: 2021-01-12T07:42:21Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-642-28914-9_31
ec_funded: 1
intvolume: '      7194'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf
month: '05'
oa: 1
oa_version: Submitted Version
page: 548 - 563
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3366'
quality_controlled: '1'
status: public
title: Subspace LWE
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7194
year: '2012'
...
---
_id: '3281'
abstract:
- lang: eng
  text: 'We consider the problem of amplifying the &quot;lossiness&quot; of functions.
    We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness
    from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f
    is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f
    has image size at most 2 m-L. The question is whether such C* exists for L/m ≫
    ℓ/n. This problem arises naturally in the context of cryptographic &quot;lossy
    functions,&quot; where the relative lossiness is the key parameter. We show that
    for every circuit C* that makes at most t queries to f, the relative lossiness
    of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making
    a polynomial t = poly(n) number of queries can amplify relative lossiness by more
    than an O(logn)/n additive term. We show that this is tight by giving a simple
    construction (cascading with some randomization) that achieves such amplification.'
acknowledgement: "We would like to thank Oded Goldreich and Omer Rein- gold for discussions
  at an early stage of this project, and Scott Aaronson for clarifications regarding
  the collision problem.\r\n"
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Alon
  full_name: Rosen, Alon
  last_name: Rosen
- first_name: Gil
  full_name: Segev, Gil
  last_name: Segev
citation:
  ama: 'Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol
    7194. Springer; 2012:458-475. doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_26">10.1007/978-3-642-28914-9_26</a>'
  apa: 'Pietrzak, K. Z., Rosen, A., &#38; Segev, G. (2012). Lossy functions do not
    amplify well (Vol. 7194, pp. 458–475). Presented at the TCC: Theory of Cryptography
    Conference, Taormina, Sicily, Italy: Springer. <a href="https://doi.org/10.1007/978-3-642-28914-9_26">https://doi.org/10.1007/978-3-642-28914-9_26</a>'
  chicago: Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not
    Amplify Well,” 7194:458–75. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-28914-9_26">https://doi.org/10.1007/978-3-642-28914-9_26</a>.
  ieee: 'K. Z. Pietrzak, A. Rosen, and G. Segev, “Lossy functions do not amplify well,”
    presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy,
    2012, vol. 7194, pp. 458–475.'
  ista: 'Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well.
    TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 458–475.'
  mla: Pietrzak, Krzysztof Z., et al. <i>Lossy Functions Do Not Amplify Well</i>.
    Vol. 7194, Springer, 2012, pp. 458–75, doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_26">10.1007/978-3-642-28914-9_26</a>.
  short: K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.
conference:
  end_date: 2012-03-21
  location: Taormina, Sicily, Italy
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2012-03-19
date_created: 2018-12-11T12:02:26Z
date_published: 2012-05-04T00:00:00Z
date_updated: 2021-01-12T07:42:22Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-642-28914-9_26
intvolume: '      7194'
language:
- iso: eng
main_file_link:
- url: http://www.iacr.org/archive/tcc2012/tcc2012-index.html
month: '05'
oa_version: None
page: 458 - 475
publication_status: published
publisher: Springer
publist_id: '3365'
quality_controlled: '1'
status: public
title: Lossy functions do not amplify well
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7194
year: '2012'
...
---
_id: '3282'
abstract:
- lang: eng
  text: 'Traditionally, symmetric-key message authentication codes (MACs) are easily
    built from pseudorandom functions (PRFs). In this work we propose a wide variety
    of other approaches to building efficient MACs, without going through a PRF first.
    In particular, unlike deterministic PRF-based MACs, where each message has a unique
    valid tag, we give a number of probabilistic MAC constructions from various other
    primitives/assumptions. Our main results are summarized as follows: We show several
    new probabilistic MAC constructions from a variety of general assumptions, including
    CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating
    these frameworks under concrete number theoretic assumptions, we get several schemes
    which are more efficient than just using a state-of-the-art PRF instantiation
    under the corresponding assumption. For probabilistic MACs, unlike deterministic
    ones, unforgeability against a chosen message attack (uf-cma ) alone does not
    imply security if the adversary can additionally make verification queries (uf-cmva
    ). We give an efficient generic transformation from any uf-cma secure MAC which
    is &quot;message-hiding&quot; into a uf-cmva secure MAC. This resolves the main
    open problem of Kiltz et al. from Eurocrypt''11; By using our transformation on
    their constructions, we get the first efficient MACs from the LPN assumption.
    While all our new MAC constructions immediately give efficient actively secure,
    two-round symmetric-key identification schemes, we also show a very simple, three-round
    actively secure identification protocol from any weak PRF. In particular, the
    resulting protocol is much more efficient than the trivial approach of building
    a regular PRF from a weak PRF. © 2012 International Association for Cryptologic
    Research.'
acknowledgement: Supported by the European Research Council under the European Union’s
  Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)
alternative_title:
- LNCS
author:
- first_name: Yevgeniy
  full_name: Dodis, Yevgeniy
  last_name: Dodis
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Eike
  full_name: Kiltz, Eike
  last_name: Kiltz
- first_name: Daniel
  full_name: Wichs, Daniel
  last_name: Wichs
citation:
  ama: 'Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. Message authentication, revisited.
    In: Vol 7237. Springer; 2012:355-374. doi:<a href="https://doi.org/10.1007/978-3-642-29011-4_22">10.1007/978-3-642-29011-4_22</a>'
  apa: 'Dodis, Y., Pietrzak, K. Z., Kiltz, E., &#38; Wichs, D. (2012). Message authentication,
    revisited (Vol. 7237, pp. 355–374). Presented at the EUROCRYPT: Theory and Applications
    of Cryptographic Techniques, Cambridge, UK: Springer. <a href="https://doi.org/10.1007/978-3-642-29011-4_22">https://doi.org/10.1007/978-3-642-29011-4_22</a>'
  chicago: Dodis, Yevgeniy, Krzysztof Z Pietrzak, Eike Kiltz, and Daniel Wichs. “Message
    Authentication, Revisited,” 7237:355–74. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-29011-4_22">https://doi.org/10.1007/978-3-642-29011-4_22</a>.
  ieee: 'Y. Dodis, K. Z. Pietrzak, E. Kiltz, and D. Wichs, “Message authentication,
    revisited,” presented at the EUROCRYPT: Theory and Applications of Cryptographic
    Techniques, Cambridge, UK, 2012, vol. 7237, pp. 355–374.'
  ista: 'Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. 2012. Message authentication, revisited.
    EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 7237,
    355–374.'
  mla: Dodis, Yevgeniy, et al. <i>Message Authentication, Revisited</i>. Vol. 7237,
    Springer, 2012, pp. 355–74, doi:<a href="https://doi.org/10.1007/978-3-642-29011-4_22">10.1007/978-3-642-29011-4_22</a>.
  short: Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.
conference:
  end_date: 2012-04-19
  location: Cambridge, UK
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2012-04-15
date_created: 2018-12-11T12:02:27Z
date_published: 2012-03-10T00:00:00Z
date_updated: 2021-01-12T07:42:22Z
day: '10'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-29011-4_22
ec_funded: 1
file:
- access_level: open_access
  checksum: 8557c17a8c2586d06ebfe62d934f5c5f
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:14:23Z
  date_updated: 2020-07-14T12:46:06Z
  file_id: '5074'
  file_name: IST-2016-686-v1+1_059.pdf
  file_size: 372292
  relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
has_accepted_license: '1'
intvolume: '      7237'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 355 - 374
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3364'
pubrep_id: '686'
quality_controlled: '1'
status: public
title: Message authentication, revisited
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7237
year: '2012'
...
---
_id: '2048'
abstract:
- lang: eng
  text: Leakage resilient cryptography attempts to incorporate side-channel leakage
    into the black-box security model and designs cryptographic schemes that are provably
    secure within it. Informally, a scheme is leakage-resilient if it remains secure
    even if an adversary learns a bounded amount of arbitrary information about the
    schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily
    complicated in order to achieve strong provable security guarantees. As advocated
    by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in
    practice much simpler construction may already suffice to protect against realistic
    side-channel attacks. In this paper, we show that indeed for simpler constructions
    leakage-resilience can be obtained when we aim for relaxed security notions where
    the leakage-functions and/or the inputs to the primitive are chosen non-adaptively.
    For example, we show that a three round Feistel network instantiated with a leakage
    resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively
    (This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if
    a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.)
    We also show that a minor variation of the classical GGM construction gives a
    leakage resilient PRF if both, the leakage-function and the inputs, are chosen
    non-adaptively.
acknowledgement: "Sebastian Faust acknowledges support from the Danish National Research
  Foundation and The National Science Foundation of China (under the grant 61061130540)
  for the Sino-Danish Center for the Theory of Interactive Computation, within part
  of this work was performed; and from the CFEM research center, supported by the
  Danish Strategic Research Council. \r\nSupported by the European Research Council/ERC
  Starting Grant 259668-PSPC.\r\n"
alternative_title:
- LNCS
author:
- first_name: Sebastian
  full_name: Faust, Sebastian
  last_name: Faust
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Joachim
  full_name: Schipper, Joachim
  id: 7BE863D4-E9CF-11E9-9EDB-90527418172C
  last_name: Schipper
citation:
  ama: 'Faust S, Pietrzak KZ, Schipper J. Practical leakage-resilient symmetric cryptography.
    In: <i> Conference Proceedings CHES 2012</i>. Vol 7428. Springer; 2012:213-232.
    doi:<a href="https://doi.org/10.1007/978-3-642-33027-8_13">10.1007/978-3-642-33027-8_13</a>'
  apa: 'Faust, S., Pietrzak, K. Z., &#38; Schipper, J. (2012). Practical leakage-resilient
    symmetric cryptography. In <i> Conference proceedings CHES 2012</i> (Vol. 7428,
    pp. 213–232). Leuven, Belgium: Springer. <a href="https://doi.org/10.1007/978-3-642-33027-8_13">https://doi.org/10.1007/978-3-642-33027-8_13</a>'
  chicago: Faust, Sebastian, Krzysztof Z Pietrzak, and Joachim Schipper. “Practical
    Leakage-Resilient Symmetric Cryptography.” In <i> Conference Proceedings CHES
    2012</i>, 7428:213–32. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-33027-8_13">https://doi.org/10.1007/978-3-642-33027-8_13</a>.
  ieee: S. Faust, K. Z. Pietrzak, and J. Schipper, “Practical leakage-resilient symmetric
    cryptography,” in <i> Conference proceedings CHES 2012</i>, Leuven, Belgium, 2012,
    vol. 7428, pp. 213–232.
  ista: 'Faust S, Pietrzak KZ, Schipper J. 2012. Practical leakage-resilient symmetric
    cryptography.  Conference proceedings CHES 2012. CHES: Cryptographic Hardware
    and Embedded Systems, LNCS, vol. 7428, 213–232.'
  mla: Faust, Sebastian, et al. “Practical Leakage-Resilient Symmetric Cryptography.”
    <i> Conference Proceedings CHES 2012</i>, vol. 7428, Springer, 2012, pp. 213–32,
    doi:<a href="https://doi.org/10.1007/978-3-642-33027-8_13">10.1007/978-3-642-33027-8_13</a>.
  short: S. Faust, K.Z. Pietrzak, J. Schipper, in:,  Conference Proceedings CHES 2012,
    Springer, 2012, pp. 213–232.
conference:
  end_date: 2012-09-12
  location: Leuven, Belgium
  name: 'CHES: Cryptographic Hardware and Embedded Systems'
  start_date: 2012-09-09
date_created: 2018-12-11T11:55:25Z
date_published: 2012-09-01T00:00:00Z
date_updated: 2021-01-12T06:54:58Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-33027-8_13
ec_funded: 1
intvolume: '      7428'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://www.iacr.org/archive/ches2012/74280211/74280211.pdf
month: '09'
oa: 1
oa_version: Preprint
page: 213 - 232
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication: ' Conference proceedings CHES 2012'
publication_status: published
publisher: Springer
publist_id: '5003'
quality_controlled: '1'
scopus_import: 1
status: public
title: Practical leakage-resilient symmetric cryptography
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7428
year: '2012'
...
---
_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: <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
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'
...