--- _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: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400' apa: 'Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316400' 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 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400. 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 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, 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.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400. 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' ... --- _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 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: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM Press; 2019:986-996. doi:10.1145/3313276.3316407' apa: 'Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2019). Why extension-based proofs fail. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 986–996). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316407' chicago: Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 986–96. ACM Press, 2019. https://doi.org/10.1145/3313276.3316407. ieee: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 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.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–96, doi:10.1145/3313276.3316407. 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' ...