---
_id: '6676'
abstract:
- lang: eng
  text: "It is impossible to deterministically solve wait-free consensus in an asynchronous
    system. The classic proof uses a valency argument, which constructs an infinite
    execution by repeatedly extending a finite execution. We introduce extension-based
    proofs, a class of impossibility proofs that are modelled as an interaction between
    a prover and a protocol and that include valency arguments.\r\n\r\nUsing proofs
    based on combinatorial topology, it has been shown that it is impossible to deterministically
    solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However,
    it was unknown whether proofs based on simpler techniques were possible. We show
    that this impossibility result cannot be obtained by an extension-based proof
    and, hence, extension-based proofs are limited in power."
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: James
  full_name: Aspnes, James
  last_name: Aspnes
- first_name: Faith
  full_name: Ellen, Faith
  last_name: Ellen
- first_name: Rati
  full_name: Gelashvili, Rati
  last_name: Gelashvili
- first_name: Leqi
  full_name: Zhu, Leqi
  last_name: Zhu
citation:
  ama: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based
    proofs fail. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
    of Computing</i>. ACM Press; 2019:986-996. doi:<a href="https://doi.org/10.1145/3313276.3316407">10.1145/3313276.3316407</a>'
  apa: 'Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2019).
    Why extension-based proofs fail. In <i>Proceedings of the 51st Annual ACM SIGACT
    Symposium on Theory of Computing</i> (pp. 986–996). Phoenix, AZ, United States:
    ACM Press. <a href="https://doi.org/10.1145/3313276.3316407">https://doi.org/10.1145/3313276.3316407</a>'
  chicago: Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi
    Zhu. “Why Extension-Based Proofs Fail.” In <i>Proceedings of the 51st Annual ACM
    SIGACT Symposium on Theory of Computing</i>, 986–96. ACM Press, 2019. <a href="https://doi.org/10.1145/3313276.3316407">https://doi.org/10.1145/3313276.3316407</a>.
  ieee: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based
    proofs fail,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
    of Computing</i>, Phoenix, AZ, United States, 2019, pp. 986–996.
  ista: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2019. Why extension-based
    proofs fail. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
    Computing. STOC: Symposium on Theory of Computing, 986–996.'
  mla: Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” <i>Proceedings
    of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, ACM Press,
    2019, pp. 986–96, doi:<a href="https://doi.org/10.1145/3313276.3316407">10.1145/3313276.3316407</a>.
  short: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings
    of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019,
    pp. 986–996.
conference:
  end_date: 2019-06-26
  location: Phoenix, AZ, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2019-06-23
date_created: 2019-07-24T09:13:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-12-13T12:28:28Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3313276.3316407
external_id:
  arxiv:
  - '1811.01421'
  isi:
  - '000523199100089'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1811.01421
month: '06'
oa: 1
oa_version: Preprint
page: 986-996
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
related_material:
  record:
  - id: '14364'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Why extension-based proofs fail
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '6677'
abstract:
- lang: eng
  text: "The Fiat-Shamir heuristic transforms a public-coin interactive proof into
    a non-interactive argument, by replacing the verifier with a cryptographic hash
    function that is applied to the protocol’s transcript. Constructing hash functions
    for which this transformation is sound is a central and long-standing open question
    in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is
    no easier than breaking the soundness of the Fiat-Shamir transformation when applied
    to the sumcheck protocol. In particular, if the transformed protocol is sound,
    then any hard problem in #P gives rise to a hard distribution in the class CLS,
    which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized
    games for which it is hard to find a Nash equilibrium, by reducing the inversion
    of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution
    is a stateful incrementally verifiable procedure that, given a SAT instance over
    n variables, counts the number of satisfying assignments. This is accomplished
    via an exponential sequence of small steps, each computable in time poly(n). Incremental
    verifiability means that each intermediate state includes a sumcheck-based proof
    of its correctness, and the proof can be updated and verified in time poly(n)."
article_processing_charge: No
author:
- first_name: Arka Rai
  full_name: Choudhuri, Arka Rai
  last_name: Choudhuri
- first_name: Pavel
  full_name: Hubáček, Pavel
  last_name: Hubáček
- first_name: Chethan
  full_name: Kamath Hosdurg, Chethan
  id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
  last_name: Kamath Hosdurg
- 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: Guy N.
  full_name: Rothblum, Guy N.
  last_name: Rothblum
citation:
  ama: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
    GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: <i>Proceedings
    of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>.
    ACM Press; 2019:1103-1114. doi:<a href="https://doi.org/10.1145/3313276.3316400">10.1145/3313276.3316400</a>'
  apa: 'Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen,
    A., &#38; Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than
    breaking Fiat-Shamir. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium
    on Theory of Computing  - STOC 2019</i> (pp. 1103–1114). Phoenix, AZ, United States:
    ACM Press. <a href="https://doi.org/10.1145/3313276.3316400">https://doi.org/10.1145/3313276.3316400</a>'
  chicago: Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z
    Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier
    than Breaking Fiat-Shamir.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium
    on Theory of Computing  - STOC 2019</i>, 1103–14. ACM Press, 2019. <a href="https://doi.org/10.1145/3313276.3316400">https://doi.org/10.1145/3313276.3316400</a>.
  ieee: A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen,
    and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,”
    in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 
    - STOC 2019</i>, Phoenix, AZ, United States, 2019, pp. 1103–1114.
  ista: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
    GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings
    of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. STOC:
    Symposium on Theory of Computing, 1103–1114.'
  mla: Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking
    Fiat-Shamir.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
    of Computing  - STOC 2019</i>, ACM Press, 2019, pp. 1103–14, doi:<a href="https://doi.org/10.1145/3313276.3316400">10.1145/3313276.3316400</a>.
  short: A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N.
    Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
    Computing  - STOC 2019, ACM Press, 2019, pp. 1103–1114.
conference:
  end_date: 2019-06-26
  location: Phoenix, AZ, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2019-06-23
date_created: 2019-07-24T09:20:53Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:15:55Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/3313276.3316400
ec_funded: 1
external_id:
  isi:
  - '000523199100100'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2019/549
month: '06'
oa: 1
oa_version: Preprint
page: 1103-1114
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  -
  STOC 2019
publication_identifier:
  isbn:
  - '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
related_material:
  record:
  - id: '7896'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...