---
_id: '2974'
abstract:
- lang: eng
  text: "We construct a perfectly binding string commitment scheme whose security
    is based on the learning parity with noise (LPN) assumption, or equivalently,
    the hardness of decoding random linear codes. Our scheme not only allows for a
    simple and efficient zero-knowledge proof of knowledge for committed values (essentially
    a Σ-protocol), but also for such proofs showing any kind of relation amongst committed
    values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u)
    for any circuit C.\r\n\r\nTo get soundness which is exponentially small in a security
    parameter t, and when the zero-knowledge property relies on the LPN problem with
    secrets of length l, our 3 round protocol has communication complexity O(t|C|l
    log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants
    are small, and the computation consists mostly of computing inner products of
    bit-vectors."
acknowledgement: "We are grateful to Petros Mol for helpful discussions on the reduction
  for the hardness of the xLPN problem.\r\n"
alternative_title:
- LNCS
author:
- first_name: Abhishek
  full_name: Jain, Abhishek
  last_name: Jain
- first_name: Stephan
  full_name: Krenn, Stephan
  id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
  last_name: Krenn
  orcid: 0000-0003-2835-9093
- 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, Krenn S, Pietrzak KZ, Tentes A. Commitments and efficient zero knowledge
    proofs from learning parity with noise. In: Wang X, Sako K, eds. Vol 7658. Springer;
    2012:663-680. doi:<a href="https://doi.org/10.1007/978-3-642-34961-4_40">10.1007/978-3-642-34961-4_40</a>'
  apa: 'Jain, A., Krenn, S., Pietrzak, K. Z., &#38; Tentes, A. (2012). Commitments
    and efficient zero knowledge proofs from learning parity with noise. In X. Wang
    &#38; K. Sako (Eds.) (Vol. 7658, pp. 663–680). Presented at the ASIACRYPT: Theory
    and Application of Cryptology and Information Security, Beijing, China: Springer.
    <a href="https://doi.org/10.1007/978-3-642-34961-4_40">https://doi.org/10.1007/978-3-642-34961-4_40</a>'
  chicago: Jain, Abhishek, Stephan Krenn, Krzysztof Z Pietrzak, and Aris Tentes. “Commitments
    and Efficient Zero Knowledge Proofs from Learning Parity with Noise.” edited by
    Xiaoyun Wang and Kazue Sako, 7658:663–80. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-34961-4_40">https://doi.org/10.1007/978-3-642-34961-4_40</a>.
  ieee: 'A. Jain, S. Krenn, K. Z. Pietrzak, and A. Tentes, “Commitments and efficient
    zero knowledge proofs from learning parity with noise,” presented at the ASIACRYPT:
    Theory and Application of Cryptology and Information Security, Beijing, China,
    2012, vol. 7658, pp. 663–680.'
  ista: 'Jain A, Krenn S, Pietrzak KZ, Tentes A. 2012. Commitments and efficient zero
    knowledge proofs from learning parity with noise. ASIACRYPT: Theory and Application
    of Cryptology and Information Security, LNCS, vol. 7658, 663–680.'
  mla: Jain, Abhishek, et al. <i>Commitments and Efficient Zero Knowledge Proofs from
    Learning Parity with Noise</i>. Edited by Xiaoyun Wang and Kazue Sako, vol. 7658,
    Springer, 2012, pp. 663–80, doi:<a href="https://doi.org/10.1007/978-3-642-34961-4_40">10.1007/978-3-642-34961-4_40</a>.
  short: A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.),
    Springer, 2012, pp. 663–680.
conference:
  end_date: 2012-12-06
  location: Beijing, China
  name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security'
  start_date: 2012-12-02
date_created: 2018-12-11T12:00:38Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2021-01-12T07:40:11Z
day: '01'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-642-34961-4_40
ec_funded: 1
editor:
- first_name: Xiaoyun
  full_name: Wang, Xiaoyun
  last_name: Wang
- first_name: Kazue
  full_name: Sako, Kazue
  last_name: Sako
file:
- access_level: open_access
  checksum: ab879537385efc4cb4203e7ef0fea17b
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:14:00Z
  date_updated: 2020-07-14T12:45:58Z
  file_id: '5048'
  file_name: IST-2016-721-v1+1_513.pdf
  file_size: 482570
  relation: main_file
file_date_updated: 2020-07-14T12:45:58Z
has_accepted_license: '1'
intvolume: '      7658'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 663 - 680
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: '3730'
pubrep_id: '721'
scopus_import: 1
status: public
title: Commitments and efficient zero knowledge proofs from learning parity with noise
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: 7658
year: '2012'
...