{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T16:13:05Z","timestamp":1778083985805,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This technical paper explores two solutions for arithmetization of computational integrity statements in STARKs, namely the algebraic intermediate representation, AIR, and its preprocessed variant, PAIR. The work then focuses on their soundness implications for Reed\u2013Solomon proximity testing. It proceeds by presenting a comparative study of these methods, providing their theoretical foundations and deriving the degree bounds for low-degree proximity testing. The study shows that using PAIR increases the degree bound for Reed\u2013Solomon proximity testing, which affects its soundness and complexity. However, the possibility of reducing the degree bound with multiple selector columns is also explored, namely by following an approach based on the decomposition of the selector values. Focusing on performance optimization, the work proceeds by qualitatively comparing computational demands of the components of both arithmetization methods, particularly their impact on the low-degree extensions. The paper concludes that, while PAIR might simplify constraint enforcement, it can be easily translated to AIR, and system testing with benchmarks is necessary to determine the application-specific superiority of either method. This work should provide insight into the strengths and limitations of each method, helping researchers and practitioners in the field of STARKs make informed design choices.<\/jats:p>","DOI":"10.1007\/s00145-025-09567-0","type":"journal-article","created":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:34:36Z","timestamp":1770752076000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Study of Arithmetization Methods for STARKs"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3200-2225","authenticated-orcid":false,"given":"Tiago","family":"Martins","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1062-4569","authenticated-orcid":false,"given":"Jo\u00e3o","family":"Farinha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,10]]},"reference":[{"key":"9567_CR1","unstructured":"0xMiden. AirScript. July (2023). https:\/\/github.com\/0xMiden\/air-script\/tree\/next (visited on 05\/11\/2025)."},{"key":"9567_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01200057","volume":"1","author":"L Babai","year":"1991","unstructured":"L. Babai and L. Fortnow. \u201cArithmetization: A New Method in Structural Complexity Theory.\u201d Computational Complexity 1 (1991), 41\u201366. https:\/\/doi.org\/10.1007\/BF01200057.","journal-title":"Computational Complexity"},{"key":"9567_CR3","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, I. Ben-Tov, A. Chiesa, A. Gabizon, D. Genkin, M. Hamilis, E. Pergament, M. Riabzev, M. Silberstein, E. Tromer, M. Virza, Computational integrity with a public random string from quasi-linear PCPs. IACR Cryptology ePrint Archive, Paper 2016\/646. (2016). https:\/\/eprint.iacr.org\/2016\/646","DOI":"10.1007\/978-3-319-56617-7_19"},{"key":"9567_CR4","doi-asserted-by":"publisher","unstructured":"E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, Fast Reed-Solomon Interactive Oracle Proofs of Proximity\u2019. in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Edited by I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella. Volume 107. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 2018, 14:1\u201314:17. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.14. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9018.","DOI":"10.4230\/LIPIcs.ICALP.2018.14"},{"key":"9567_CR5","unstructured":"E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive, Paper 2018\/046 (2018). https:\/\/eprint.iacr.org\/2018\/046."},{"key":"9567_CR6","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, \u201cScalable zero knowledge with no trusted setup\u201d. in Advances in Cryptology\u2013CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, Proceedings, Part III 39. Springer. Aug. pages 701\u2013732 (2019).","DOI":"10.1007\/978-3-030-26954-8_23"},{"key":"9567_CR7","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, D. Carmon, Y. Ishai, S. Kopparty, S. Saraf, Proximity gaps for Reed-Solomon codes. Electronic Colloquium on Computational Complexity, Revision 3 of Report No. 83. 2021 (2020). https:\/\/eprint.iacr.org\/2020\/654.","DOI":"10.1109\/FOCS46700.2020.00088"},{"key":"9567_CR8","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, N. Spooner, \u201cInteractive oracle proofs\u201d. in Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part II 14. Springer. pages 31\u201360 (2016).","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"9567_CR9","unstructured":"E. Ben-Sasson, L. Goldberg, S. Kopparty, and S. Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. IACR Cryptology ePrint Archive, Paper 2019\/336. 2019. https:\/\/eprint.iacr.org\/2019\/336 (visited on 03\/30\/2023)."},{"issue":"2","key":"9567_CR10","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E Ben-Sasson","year":"2008","unstructured":"E. Ben-Sasson and M. Sudan. \u201cShort PCPs with polylog query complexity\u201d. SIAM Journal on Computing 38.2 (2008), 551\u2013607.","journal-title":"SIAM Journal on Computing"},{"key":"9567_CR11","unstructured":"A.T. Bharucha-Reid M. Sambandham. Random polynomials: Probability and mathematical statistics: a series of monographs and textbooks. Academic Press (2014)."},{"key":"9567_CR12","doi-asserted-by":"crossref","unstructured":"A. Fiat, A. Shamir, \u201cHow to Prove Yourself: Practical Solutions to Identification and Signature Problems\u201d. in Proceedings on Advances in Cryptology\u2014CRYPTO \u201986. Santa Barbara, California, USA: Springer-Verlag, pages 186\u2013194 (1987).","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9567_CR13","unstructured":"A. Gabizon. From AIRs to RAPs - how PLONK-style arithmetization works (2021). https:\/\/hackmd.io\/@aztec-network\/plonk-arithmetiization-air (visited on 03\/30\/2023)."},{"key":"9567_CR14","volume-title":"Contemporary abstract algebra","author":"JA Gallian","year":"2010","unstructured":"J.A. Gallian. Contemporary abstract algebra. 7th edition. Brooks-Cole\/Cengage Learning, Belmont, CA, 2010.","edition":"7"},{"key":"9567_CR15","unstructured":"U. Hab\u00f6ck. A summary on the FRI low degree test. IACR Cryptology ePrint Archive, Paper 2022\/1216 (2022). https:\/\/eprint.iacr.org\/2022\/1216 (visited on 03\/30\/2023)"},{"key":"9567_CR16","volume-title":"Numerical Methods With Applications","author":"AK Kaw","year":"2011","unstructured":"A.K. Kaw, E.K. Kalu, D. Nguyen, Numerical Methods With Applications. University of South Florida, Florida (2011)"},{"key":"9567_CR17","unstructured":"LambdaClass. Arithmetization schemes for ZK-SNARKs. Jan (2023). https:\/\/blog.lambdaclass.com\/arithmetization-schemes-for-zk-snarks\/ (visited on 05\/11\/2025)"},{"issue":"4","key":"9567_CR18","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C Lund","year":"1992","unstructured":"C. Lund, L. Fortnow, H. Karloff, and N. Nisan. \u201cAlgebraic methods for interactive proof systems\u201d. Journal of the ACM (JACM) 39.4 (1992), 859\u2013868.","journal-title":"Journal of the ACM (JACM)"},{"key":"9567_CR19","unstructured":"H. Masip-Ardevol, M. Guzm\u00e1n-Albiol, J. Baylina-Mel\u00e9, J.L. Mu\u00f1oz-Tapia. eSTARK: Extending STARKs with Arguments. Cryptology ePrint Archive, Paper 2023\/474. Apr (2023). https:\/\/eprint.iacr.org\/2023\/474"},{"key":"9567_CR20","unstructured":"Polygon Miden. AirScript Documentation. Feb (2023). https:\/\/0xmiden.github.io\/air-script\/ (visited on 03\/30\/2023)"},{"key":"9567_CR21","unstructured":"StarkWare Team. Arithmetization II - \u201cWe Need To Go Deeper\u201d. Mar (2019). https:\/\/medium.com\/starkware\/arithmetization-ii-403c3b3f4355 (visited on 03\/30\/2023)"},{"key":"9567_CR22","unstructured":"StarkWare Team. ethSTARK Documentation \u2013 Version 1.1. IACR Cryptology ePrint Archive, Paper 2021\/582. Jan. 2021. https:\/\/eprint.iacr.org\/2021\/582."},{"key":"9567_CR23","doi-asserted-by":"crossref","unstructured":"A. Terras, Fourier Analysis on Finite Groups and Applications. London Mathematical Society Student Texts. Cambridge University Press (1999)","DOI":"10.1017\/CBO9780511626265"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09567-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-025-09567-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09567-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:18:36Z","timestamp":1778080716000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-025-09567-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,10]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["9567"],"URL":"https:\/\/doi.org\/10.1007\/s00145-025-09567-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,10]]},"assertion":[{"value":"22 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"15"}}