{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T04:07:16Z","timestamp":1767931636043,"version":"3.49.0"},"reference-count":28,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:00:00Z","timestamp":1759881600000},"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":[[2025,12,2]]},"abstract":"<jats:p>We present the first horizontally scalable polynomial commitment scheme (PCS) that is both transparent and plausibly post-quantum (PQ) secure. This PCS can be combined with the distributed polynomial interactive oracle proof (PIOP) introduced in Pianist (IEEE S&amp; P 2024), which achieves linear scalability by encoding witnesses using bivariate polynomials. While Pianist and other scalable SNARK systems offer strong performance profiles, they rely on trusted setup ceremonies and cryptographic assumptions that are not PQ secure, e.g., pairing-based primitives. In contrast, we present a bivariate PCS based on FRI, which, when used to compile the Pianist PIOP, achieves a transparent and plausibly PQ alternative. Distributed FRI has a high communication cost. Therefore, we introduce Fold-and-Batch, a customizable technique that applies partial folding locally before performing batched FRI centrally. We formally prove the security of our constructions and provide an implementation for three variants of distributed FRI, accompanied by thorough performance evaluations. Our results show that Fold-and-Batch reduces communication overhead compared to existing distributed FRI approaches, while preserving scalability and maintaining moderate proof sizes. To our knowledge, this is the first horizontally scalable PCS that simultaneously achieves transparency, plausible PQ security, and a tunable tradeoff between efficiency, verifier cost, and communication.<\/jats:p>","DOI":"10.62056\/akjby76bm","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:47Z","timestamp":1767915587000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["FRIttata: A FRI-based Polynomial Commitment Scheme for Distributed Proof Generation"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-1972-7815","authenticated-orcid":false,"given":"Hua","family":"Xu","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2759-043X","authenticated-orcid":false,"given":"Mariana","family":"Gama","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3352-6968","authenticated-orcid":false,"given":"Emad","family":"Beni","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]},{"id":[{"id":"https:\/\/ror.org\/04xze1462","id-type":"ROR","asserted-by":"publisher"}],"name":"Nokia Bell Labs","place":["Antwerp, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1093-7978","authenticated-orcid":false,"given":"Jiayi","family":"Kang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"ref1:plonk","volume-title":"PLONK: Permutations over Lagrange-bases for Oecumenical\n  Noninteractive arguments of Knowledge","author":"Ariel Gabizon","year":"2019"},{"key":"ref2:pianist","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1109\/SP54263.2024.00035","article-title":"Pianist: Scalable zkRollups via Fully Distributed\n  Zero-Knowledge Proofs","author":"Tianyi Liu","year":"2024"},{"key":"ref3:DIZK","isbn-type":"print","first-page":"675","article-title":"DIZK: A Distributed Zero Knowledge Proof System","author":"Howard Wu","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9781939133045"},{"key":"ref4:groth16","series-title":"Lecture Notes in Computer Science","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":"9666","author":"Jens Groth","year":"2016"},{"key":"ref5:KZG","series-title":"Lecture Notes in Computer Science","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":"6477","author":"Aniket Kate","year":"2010"},{"key":"ref6:FRI","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2018.14","article-title":"Fast Reed-Solomon Interactive Oracle Proofs of Proximity","volume":"107","author":"Eli Ben-Sasson","year":"2018"},{"key":"ref7:HyperPianist","doi-asserted-by":"publisher","first-page":"3383","DOI":"10.1109\/SP61157.2025.00202","article-title":"HyperPianist: Pianist with Linear-Time Prover and\n  Logarithmic Communication Cost","author":"Chongrong Li","year":"2025","ISSN":"https:\/\/id.crossref.org\/issn\/2375-1207","issn-type":"electronic"},{"key":"ref8:HyperPlonk","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-031-30617-4_17","article-title":"HyperPlonk: Plonk with Linear-Time Prover and High-Degree\n  Custom Gates","volume":"14005","author":"Binyi Chen","year":"2023"},{"key":"ref9:dory","isbn-type":"print","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","author":"Jonathan Lee","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030904524"},{"key":"ref10:Cirrus","volume-title":"$\\mathsf{Cirrus}$: Performant and Accountable Distributed\n  SNARK","author":"Wenhao Wang","year":"2024"},{"key":"ref11:Hekaton","series-title":"CCS '24","isbn-type":"print","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/3658644.3690282","article-title":"Hekaton: Horizontally-Scalable zkSNARKs Via Proof\n  Aggregation","author":"Michael Rosenberg","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400706363"},{"key":"ref12:Mirage","first-page":"2129","article-title":"MIRAGE: Succinct Arguments for Randomized Algorithms with\n  Applications to Universal zk-SNARKs","author":"Ahmed E. Kosba","year":"2020"},{"key":"ref13:Soloist","volume-title":"Soloist: Distributed SNARKs for Rank-One Constraint\n  System","author":"Weihan Li","year":"2025"},{"key":"ref14:zkbrigde","series-title":"CCS '22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"3003","DOI":"10.1145\/3548606.3560652","article-title":"zkBridge: Trustless Cross-chain Bridges Made Practical","author":"Tiancheng Xie","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450394505"},{"key":"ref15:Virgo","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1109\/SP40000.2020.00052","article-title":"Transparent Polynomial Delegation and Its Applications to\n  Zero Knowledge Proof","author":"Jiaheng Zhang","year":"2020"},{"key":"ref16:FRI_PCS","volume-title":"Transparent Polynomial Commitment Scheme with\n  Polylogarithmic Communication Complexity","author":"Alexander Vlasov","year":"2019"},{"key":"ref17:nil","volume-title":"On Distributed FRI-based Proof Generation - HackMD","author":"Alisa Cherniaeva","year":"2024"},{"key":"ref18:plonky2","volume-title":"Plonky2","author":"0xPolygonZero","year":"2021"},{"key":"ref19:FS-security","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-981-99-8724-5_1","article-title":"Fiat-Shamir Security of FRI and Related SNARKs","volume":"14439","author":"Alexander R. Block","year":"2023"},{"key":"ref20:proximity_gap","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1109\/FOCS46700.2020.00088","article-title":"Proximity Gaps for Reed-Solomon Codes","author":"Eli Ben-Sasson","year":"2020"},{"key":"ref21:DARK","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-030-45721-1_24","article-title":"Transparent SNARKs from DARK Compilers","volume":"12105","author":"Benedikt B\u00fcnz","year":"2020"},{"key":"ref22:Lin01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-44647-8_10","article-title":"Parallel Coin-Tossing and Constant-Round Secure Two-Party\n  Computation","volume":"2139","author":"Yehuda Lindell","year":"2001"},{"key":"ref23:BCS","isbn-type":"print","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","article-title":"Interactive Oracle Proofs","author":"Eli Ben-Sasson","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662536438"},{"key":"ref24:FS","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","article-title":"How to Prove Yourself: Practical Solutions to Identification\n  and Signature Problems","volume":"263","author":"Amos Fiat","year":"1986"},{"key":"ref25:BCS_qrom","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-36033-7_1","article-title":"Succinct Arguments in the Quantum Random Oracle Model","author":"Alessandro Chiesa","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030360320"},{"key":"ref26:SNARGs_book","volume-title":"Building Cryptographic Proofs from Hash Functions","author":"Alessandro Chiesa","year":"2024"},{"key":"ref27:FS_from_sponges","isbn-type":"print","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/978-3-032-12287-2_16","article-title":"A Fiat\u2013Shamir Transformation from Duplex Sponges","author":"Alessandro Chiesa","year":"2025","ISBN":"https:\/\/id.crossref.org\/isbn\/9783032122865"},{"key":"ref28:parallel-repetition-theorem","series-title":"STOC '07","isbn-type":"print","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1145\/1250790.1250853","article-title":"An efficient parallel repetition theorem for Arthur-Merlin\n  games","author":"Rafael Pass","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9781595936318"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:41:05Z","timestamp":1767915665000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/4\/26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,1,8]]}},"URL":"https:\/\/doi.org\/10.62056\/akjby76bm","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-10-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-4-53"}}