@inproceedings{6676,
  abstract     = {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.

Using 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.},
  author       = {Alistarh, Dan-Adrian and Aspnes, James and Ellen, Faith and Gelashvili, Rati and Zhu, Leqi},
  booktitle    = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
  isbn         = {9781450367059},
  location     = {Phoenix, AZ, United States},
  pages        = {986--996},
  publisher    = {ACM Press},
  title        = {{Why extension-based proofs fail}},
  doi          = {10.1145/3313276.3316407},
  year         = {2019},
}

@inproceedings{6677,
  abstract     = {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.

We 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.

Our 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).},
  author       = {Choudhuri, Arka Rai and Hubáček, Pavel and Kamath Hosdurg, Chethan and Pietrzak, Krzysztof Z and Rosen, Alon and Rothblum, Guy N.},
  booktitle    = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019},
  isbn         = {9781450367059},
  location     = {Phoenix, AZ, United States},
  pages        = {1103--1114},
  publisher    = {ACM Press},
  title        = {{Finding a Nash equilibrium is no easier than breaking Fiat-Shamir}},
  doi          = {10.1145/3313276.3316400},
  year         = {2019},
}