---
_id: '3250'
abstract:
- lang: eng
  text: The Learning Parity with Noise (LPN) problem has recently found many applications
    in cryptography as the hardness assumption underlying the constructions of "provably
    secure" cryptographic schemes like encryption or authentication protocols.
    Being provably secure means that the scheme comes with a proof showing that the
    existence of an efficient adversary against the scheme implies that the underlying
    hardness assumption is wrong. LPN based schemes are appealing for theoretical
    and practical reasons. On the theoretical side, LPN based schemes offer a very
    strong security guarantee. The LPN problem is equivalent to the problem of decoding
    random linear codes, a problem that has been extensively studied in the last half
    century. The fastest known algorithms run in exponential time and unlike most
    number-theoretic problems used in cryptography, the LPN problem does not succumb
    to known quantum algorithms. On the practical side, LPN based schemes are often
    extremely simple and efficient in terms of code-size as well as time and space
    requirements. This makes them prime candidates for light-weight devices like RFID
    tags, which are too weak to implement standard cryptographic primitives like the
    AES block-cipher. This talk will be a gentle introduction to provable security
    using simple LPN based schemes as examples. Starting from pseudorandom generators
    and symmetric key encryption, over secret-key authentication protocols, and, if
    time admits, touching on recent constructions of public-key identification, commitments
    and zero-knowledge proofs.
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. Cryptography from learning parity with noise. In: Vol 7147. Springer;
    2012:99-114. doi:<a href="https://doi.org/10.1007/978-3-642-27660-6_9">10.1007/978-3-642-27660-6_9</a>'
  apa: 'Pietrzak, K. Z. (2012). Cryptography from learning parity with noise (Vol.
    7147, pp. 99–114). Presented at the SOFSEM: Current Trends in Theory and Practice
    of Computer Science, Špindlerův Mlýn, Czech Republic: Springer. <a href="https://doi.org/10.1007/978-3-642-27660-6_9">https://doi.org/10.1007/978-3-642-27660-6_9</a>'
  chicago: Pietrzak, Krzysztof Z. “Cryptography from Learning Parity with Noise,”
    7147:99–114. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-27660-6_9">https://doi.org/10.1007/978-3-642-27660-6_9</a>.
  ieee: 'K. Z. Pietrzak, “Cryptography from learning parity with noise,” presented
    at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Špindlerův
    Mlýn, Czech Republic, 2012, vol. 7147, pp. 99–114.'
  ista: 'Pietrzak KZ. 2012. Cryptography from learning parity with noise. SOFSEM:
    Current Trends in Theory and Practice of Computer Science, LNCS, vol. 7147, 99–114.'
  mla: Pietrzak, Krzysztof Z. <i>Cryptography from Learning Parity with Noise</i>.
    Vol. 7147, Springer, 2012, pp. 99–114, doi:<a href="https://doi.org/10.1007/978-3-642-27660-6_9">10.1007/978-3-642-27660-6_9</a>.
  short: K.Z. Pietrzak, in:, Springer, 2012, pp. 99–114.
conference:
  end_date: 2012-01-27
  location: Špindlerův Mlýn, Czech Republic
  name: 'SOFSEM: Current Trends in Theory and Practice of Computer Science'
  start_date: 2012-01-21
corr_author: '1'
date_created: 2018-12-11T12:02:15Z
date_published: 2012-02-19T00:00:00Z
date_updated: 2024-10-09T20:54:42Z
day: '19'
department:
- _id: KrPi
doi: 10.1007/978-3-642-27660-6_9
intvolume: '      7147'
language:
- iso: eng
month: '02'
oa_version: None
page: 99 - 114
publication_status: published
publisher: Springer
publist_id: '3407'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cryptography from learning parity with noise
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7147
year: '2012'
...