[{"page":"986-996","oa_version":"Preprint","type":"conference","title":"Why extension-based proofs fail","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian"},{"full_name":"Aspnes, James","last_name":"Aspnes","first_name":"James"},{"last_name":"Ellen","full_name":"Ellen, Faith","first_name":"Faith"},{"first_name":"Rati","last_name":"Gelashvili","full_name":"Gelashvili, Rati"},{"full_name":"Zhu, Leqi","last_name":"Zhu","first_name":"Leqi"}],"abstract":[{"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.","lang":"eng"}],"conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","location":"Phoenix, AZ, United States","start_date":"2019-06-23"},"date_created":"2019-07-24T09:13:05Z","status":"public","date_published":"2019-06-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6676","month":"06","external_id":{"arxiv":["1811.01421"]},"publisher":"ACM Press","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2020-08-11T10:10:40Z","day":"01","article_processing_charge":"No","doi":"10.1145/3313276.3316407","department":[{"_id":"DaAl"}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1811.01421"}],"publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","scopus_import":1,"year":"2019","publication_identifier":{"isbn":["9781450367059"]},"oa":1,"citation":{"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.","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","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.","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","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.","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.","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."}},{"conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","location":"Phoenix, AZ, United States","start_date":"2019-06-23"},"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)."}],"type":"conference","oa_version":"Preprint","author":[{"full_name":"Choudhuri, Arka Rai","last_name":"Choudhuri","first_name":"Arka Rai"},{"last_name":"Hubáček","full_name":"Hubáček, Pavel","first_name":"Pavel"},{"first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Alon","last_name":"Rosen","full_name":"Rosen, Alon"},{"full_name":"Rothblum, Guy N.","last_name":"Rothblum","first_name":"Guy N."}],"title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","page":"1103-1114","language":[{"iso":"eng"}],"quality_controlled":"1","_id":"6677","month":"06","date_created":"2019-07-24T09:20:53Z","date_published":"2019-06-01T00:00:00Z","doi":"10.1145/3313276.3316400","department":[{"_id":"KrPi"}],"oa":1,"year":"2019","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/549"}],"scopus_import":"1","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019","ec_funded":1,"project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"publisher":"ACM Press","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication_status":"published","day":"01","article_processing_charge":"No","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"7896"}]},"date_updated":"2020-10-08T11:05:55Z","citation":{"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.","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","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.","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.","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","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.","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."},"publication_identifier":{"isbn":["9781450367059"]}}]