{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:53Z","timestamp":1753895093276,"version":"3.41.2"},"reference-count":35,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,3,5]]},"abstract":"<jats:p>                We investigate proof systems where security holds against rational parties instead of malicious ones.         Our starting point is the notion of rational arguments, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also  computationally bounded.<\/jats:p>\n          <jats:p>Rational arguments are an interesting primitive because they generally allow for very efficient protocols, and in particular sublinear verification (i.e. where the Verifier does not have to read the entire input). In this paper we aim at narrowing the gap between  literature on rational schemes and real world applications. Our contribution is two-fold.<\/jats:p>\n          <jats:p>We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest.<\/jats:p>\n          <jats:p>As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our  aforementioned compiler can also be applied to obtain efficient extractable rational arguments for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mrow>\n                  <mml:mi mathvariant=\"sans-serif\">N<\/mml:mi>\n                  <mml:mi mathvariant=\"sans-serif\">P<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:mrow>\n            <\/mml:math>. <\/jats:p>","DOI":"10.62056\/a63zl86bm","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T19:27:10Z","timestamp":1712690830000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["How to Make Rational Arguments Practical and Extractable"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8184-4704","authenticated-orcid":false,"given":"Matteo","family":"Campanelli","sequence":"first","affiliation":[{"name":"Protocol Labs","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2909-9177","authenticated-orcid":false,"given":"Chaya","family":"Ganesh","sequence":"additional","affiliation":[{"name":"Indian Institute of Science","place":["India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3297-3750","authenticated-orcid":false,"given":"Rosario","family":"Gennaro","sequence":"additional","affiliation":[{"name":"The City University of New York","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:C:BCGTV13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","article-title":"SNARKs for C: Verifying Program Executions Succinctly\n  and in Zero Knowledge","volume-title":"CRYPTO\u00a02013, Part\u00a0II","volume":"8043","author":"Eli Ben-Sasson","year":"2013"},{"key":"ref2:SP:WTSTW18","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1109\/SP.2018.00060","article-title":"Doubly-Efficient zkSNARKs Without Trusted Setup","volume-title":"2018 IEEE Symposium on Security and Privacy","author":"Riad S. Wahby","year":"2018"},{"key":"ref3:CCS:CamFioQue19","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1145\/3319535.3339820","article-title":"LegoSNARK: Modular Design and Composition of Succinct\n  Zero-Knowledge Proofs","volume-title":"ACM CCS 2019","author":"Matteo Campanelli","year":"2019"},{"key":"ref4:CCS:MBKM19","doi-asserted-by":"publisher","first-page":"2111","DOI":"10.1145\/3319535.3339817","article-title":"Sonic: Zero-Knowledge SNARKs from Linear-Size Universal\n  and Updatable Structured Reference Strings","volume-title":"ACM CCS 2019","author":"Mary Maller","year":"2019"},{"key":"ref5:EC:CHMMVW20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1007\/978-3-030-45721-1_26","article-title":"Marlin: Preprocessing zkSNARKs with Universal and\n  Updatable SRS","volume-title":"EUROCRYPT\u00a02020, Part\u00a0I","volume":"12105","author":"Alessandro Chiesa","year":"2020"},{"key":"ref6:AC:CFFQR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-92078-4_1","article-title":"Lunar: A Toolbox for More Efficient Universal and\n  Updatable zkSNARKs and Commit-and-Prove Extensions","volume-title":"ASIACRYPT\u00a02021, Part\u00a0III","volume":"13092","author":"Matteo Campanelli","year":"2021"},{"key":"ref7:PKC:ABCGOT22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/978-3-030-97121-2_21","article-title":"ECLIPSE: Enhanced Compiling Method for Pedersen-Committed\n  zkSNARK Engines","volume-title":"PKC\u00a02022, Part\u00a0I","volume":"13177","author":"Diego F. Aranha","year":"2022"},{"year":"2021","author":"Jonathan Lee","article-title":"Linear-time and post-quantum zero-knowledge SNARKs for\n  R1CS","key":"ref8:EPRINT:LSTW21"},{"key":"ref9:CCS:KatPanVla22","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1145\/3548606.3560657","article-title":"RedShift: Transparent SNARKs from List Polynomial\n  Commitments","volume-title":"ACM CCS 2022","author":"Assimakis A. Kattis","year":"2022"},{"key":"ref10:EC:Groth16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","article-title":"On the Size of Pairing-Based Non-interactive Arguments","volume-title":"EUROCRYPT\u00a02016, Part\u00a0II","volume":"9666","author":"Jens Groth","year":"2016"},{"year":"2023","author":"Jens Ernstberger","article-title":"zk-Bench: A Toolset for Comparative Evaluation and\n  Performance Benchmarking of SNARKs","key":"ref11:zkalc"},{"key":"ref12:STOC:RotVadWig13","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1145\/2488608.2488709","article-title":"Interactive proofs of proximity: delegating computation in\n  sublinear time","volume-title":"45th ACM STOC","author":"Guy N. Rothblum","year":"2013"},{"key":"ref13:am","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1145\/2213977.2214069","article-title":"Rational proofs","volume-title":"Proceedings of the 44th Symposium on Theory of Computing\n  Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012","author":"Pablo Daniel Azar","year":"2012"},{"key":"ref14:cg15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-319-25594-1_15","article-title":"Sequentially Composable Rational Proofs","volume-title":"Decision and Game Theory for Security - 6th International\n  Conference, GameSec 2015, London, UK, November 4-5, 2015, Proceedings","volume":"9406","author":"Matteo Campanelli","year":"2015"},{"key":"ref15:ITCS:GHRV14","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1145\/2554797.2554845","article-title":"Rational arguments: single round delegation with sublinear\n  verification","volume-title":"ITCS 2014","author":"Siyao Guo","year":"2014"},{"key":"ref16:TCC:GHRV16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-662-49099-0_12","article-title":"Rational Sumchecks","volume-title":"TCC\u00a02016-A, Part\u00a0II","volume":"9563","author":"Siyao Guo","year":"2016"},{"key":"ref17:EC:BunFisSze20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-030-45721-1_24","article-title":"Transparent SNARKs from DARK Compilers","volume-title":"EUROCRYPT\u00a02020, Part\u00a0I","volume":"12105","author":"Benedikt B\u00fcnz","year":"2020"},{"key":"ref18:STOC:KalRazRot14","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1145\/2591796.2591809","article-title":"How to delegate computations: the power of no-signaling\n  proofs","volume-title":"46th ACM STOC","author":"Yael Tauman Kalai","year":"2014"},{"key":"ref19:testudolatincrypt","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-031-44469-2_17","article-title":"sfTestudo: Linear Time Prover SNARKs with Constant Size\n  Proofs and Square Root Size Universal Setup","volume-title":"Progress in Cryptology - LATINCRYPT 2023 - 8th\n  International Conference on Cryptology and Information Security in Latin\n  America, LATINCRYPT 2023, Quito, Ecuador, October 3-6, 2023, Proceedings","volume":"14168","author":"Matteo Campanelli","year":"2023"},{"year":"2023","author":"Matteo Campanelli","article-title":"How to Make Rational Arguments Practical and Extractable","key":"ref20:cryptoeprint:2023\/1966"},{"key":"ref21:TCC:Lee21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-90453-1_1","article-title":"Dory: Efficient, Transparent Arguments for Generalised Inner\n  Products and Polynomial Commitments","volume-title":"TCC\u00a02021, Part\u00a0II","volume":"13043","author":"Jonathan Lee","year":"2021"},{"key":"ref22:cg17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-319-68711-7_4","article-title":"Efficient Rational Proofs for Space Bounded Computations","volume-title":"Decision and Game Theory for Security - 8th International\n  Conference, GameSec 2017, Vienna, Austria, October 23-25, 2017, Proceedings","volume":"10575","author":"Matteo Campanelli","year":"2017"},{"key":"ref23:C:RafZap21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1007\/978-3-030-84242-0_27","article-title":"An Algebraic Framework for Universal and Updatable\n  SNARKs","volume-title":"CRYPTO\u00a02021, Part\u00a0I","volume":"12825","author":"Carla R\u00e0fols","year":"2021"},{"year":"2019","author":"Ariel Gabizon","article-title":"PLONK: Permutations over Lagrange-bases for Oecumenical\n  Noninteractive arguments of Knowledge","key":"ref24:EPRINT:GabWilCio19"},{"key":"ref25:AC:KatZavGol10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-17373-8_11","article-title":"Constant-Size Commitments to Polynomials and Their\n  Applications","volume-title":"ASIACRYPT\u00a02010","volume":"6477","author":"Aniket Kate","year":"2010"},{"key":"ref26:STOC:GGSW13","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1145\/2488608.2488667","article-title":"Witness encryption and its applications","volume-title":"45th ACM STOC","author":"Sanjam Garg","year":"2013"},{"key":"ref27:WYXKW21","first-page":"501","article-title":"Mystique: Efficient Conversions for Zero-Knowledge Proofs\n  with Applications to Machine Learning","volume-title":"30th USENIX Security Symposium, USENIX Security 2021,\n  August 11-13, 2021","author":"Chenkai Weng","year":"2021"},{"key":"ref28:CCS:FFGKOP16","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1145\/2976749.2978368","article-title":"Hash First, Argue Later: Adaptive Verifiable Computations on\n  Outsourced Data","volume-title":"ACM CCS 2016","author":"Dario Fiore","year":"2016"},{"key":"ref29:seti","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1109\/5992.895191","article-title":"SETI@home-massively distributed computing for SETI","volume":"3","author":"Eric Korpela","year":"2001","journal-title":"Comput. Sci. Eng."},{"key":"ref30:folding","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/IPDPS.2009.5160922","article-title":"Folding@home: Lessons from eight years of volunteer\n  distributed computing","volume-title":"23rd IEEE International Symposium on Parallel and\n  Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009","author":"Adam L. Beberg","year":"2009"},{"year":"2022","author":"Matteo Campanelli","article-title":"Witness Encryption for Succinct Functional Commitments and\n  Applications","key":"ref31:sfc-we"},{"key":"ref32:am1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/2492002.2482561","article-title":"Super-efficient rational proofs","volume-title":"Proceedings of the fourteenth ACM Conference on Electronic\n  Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013","author":"Pablo Daniel Azar","year":"2013"},{"key":"ref33:TCC:CamGen18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-030-03810-6_3","article-title":"Fine-Grained Secure Computation","volume-title":"TCC\u00a02018, Part\u00a0II","volume":"11240","author":"Matteo Campanelli","year":"2018"},{"key":"ref34:EC:GGPR13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","article-title":"Quadratic Span Programs and Succinct NIZKs without\n  PCPs","volume-title":"EUROCRYPT\u00a02013","volume":"7881","author":"Rosario Gennaro","year":"2013"},{"key":"ref35:C:FucKilLos18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-96881-0_2","article-title":"The Algebraic Group Model and its Applications","volume-title":"CRYPTO\u00a02018, Part\u00a0II","volume":"10992","author":"Georg Fuchsbauer","year":"2018"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:25:33Z","timestamp":1733865933000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":35,"URL":"https:\/\/doi.org\/10.62056\/a63zl86bm","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2024-01-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-50"}}