{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T16:03:28Z","timestamp":1780589008830,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1145\/3779208.3785286","type":"proceedings-article","created":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T15:21:58Z","timestamp":1780586518000},"page":"886-902","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Linear Operator Framework for Polynomial Divisions in Cryptography"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4390-3096","authenticated-orcid":false,"given":"Varun","family":"Madathil","sequence":"first","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3770-9982","authenticated-orcid":false,"given":"Arnab","family":"Roy","sequence":"additional","affiliation":[{"name":"Mysten Labs, San Francisco, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3252-9975","authenticated-orcid":false,"given":"Konstantinos","family":"Chalkias","sequence":"additional","affiliation":[{"name":"Mysten Labs, San Francisco, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4921-5481","authenticated-orcid":false,"given":"Charanjit","family":"Jutla","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1989-3019","authenticated-orcid":false,"given":"Jonas","family":"Lindstrom","sequence":"additional","affiliation":[{"name":"Mysten Labs, San Francisco, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,4]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"arkworks contributors. 2022. arkworks zkSNARK ecosystem. https:\/\/arkworks.rs"},{"key":"e_1_3_2_1_2_1","volume-title":"Advancing Scalability in Decentralized Storage: A Novel Approach to Proof-of-Replication via Polynomial Evaluation. Cryptology ePrint Archive","author":"Ateniese Giuseppe","year":"2023","unstructured":"Giuseppe Ateniese, Foteini Baldimtsi, Matteo Campanelli, Danilo Francati, and Ioanna Karantaidou. 2023. Advancing Scalability in Decentralized Storage: A Novel Approach to Proof-of-Replication via Polynomial Evaluation. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_3_1","unstructured":"Eli Ben-Sasson Iddo Bentov Yinon Horesh and Michael Riabzev. 2018. Scalable transparent and post-quantum secure computational integrity. Cryptologye Print Archive Report 2018\/046. https:\/\/eprint.iacr.org\/2018\/046."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_4"},{"key":"e_1_3_2_1_5_1","first-page":"291","article-title":"The tangent FFT. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","volume":"4851","author":"Bernstein Daniel J.","year":"2007","unstructured":"Daniel J. Bernstein. 2007. The tangent FFT. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lecture Notes in Computer Science 4851 (2007), 291\u2013300.","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_3_2_1_6_1","volume-title":"Data Availability Sampling with Repair. Cryptology ePrint Archive","author":"Boneh Dan","year":"2025","unstructured":"Dan Boneh, Joachim Neu, Valeria Nikolaenko, and Aditi Partap. 2025. Data Availability Sampling with Repair. Cryptology ePrint Archive (2025)."},{"key":"e_1_3_2_1_7_1","unstructured":"Alin Bostan. 2003. Algorithmique efficace pour des op\u00e9rations de base en calcul formel. Ph.D. Dissertation. Ecole Polytechnique X."},{"key":"e_1_3_2_1_8_1","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security. Springer, 77\u2013110","author":"B\u00fcnz Benedikt","year":"2023","unstructured":"Benedikt B\u00fcnz and Binyi Chen. 2023. Protostar: generic efficient accumulation\/folding for special-sound protocols. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 77\u2013110."},{"key":"e_1_3_2_1_9_1","volume-title":"IACR International Conference on Public-Key Cryptography. Springer, 337\u2013369","author":"Campanelli Matteo","year":"2024","unstructured":"Matteo Campanelli, Antonio Faonio, Dario Fiore, Tianyu Li, and Helger Lipmaa. 2024. Lookup arguments: improvements, extensions and applications to zero-knowledge decision trees. In IACR International Conference on Public-Key Cryptography. Springer, 337\u2013369."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22972-5_7"},{"key":"e_1_3_2_1_11_1","volume-title":"International Workshop on Public Key Cryptography. Springer, 55\u201372","author":"Catalano Dario","year":"2013","unstructured":"Dario Catalano and Dario Fiore. 2013. Vector commitments and their applications. In International Workshop on Public Key Cryptography. Springer, 55\u201372."},{"key":"e_1_3_2_1_12_1","unstructured":"Kostas Kryptos Chalkias Charanjit Jutla Jonas Lindstrom Varun Madathil and Arnab Roy. 2024. Improved Polynomial Division in Cryptography. Cryptology ePrint Archive Paper 2024\/1279. https:\/\/eprint.iacr.org\/2024\/1279"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_26"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings on Privacy Enhancing Technologies","author":"Choudhuri Arka Rai","year":"2024","unstructured":"Arka Rai Choudhuri, Sanjam Garg, Aarushi Goel, Sruthi Sekar, and Rohit Sinha. 2024. Sublonk: Sublinear prover plonk. Proceedings on Privacy Enhancing Technologies (2024)."},{"key":"e_1_3_2_1_15_1","volume-title":"The different ideal. Expository papers\/Lecture notes. Available at: https:\/\/kconrad.math.uconn.edu\/blurbs\/gradnumthy\/different.pdf, year=2009","author":"Conrad Keith","unstructured":"Keith Conrad. [n.d.]. The different ideal. Expository papers\/Lecture notes. Available at: https:\/\/kconrad.math.uconn.edu\/blurbs\/gradnumthy\/different.pdf, year=2009, publisher=Citeseer."},{"key":"e_1_3_2_1_16_1","volume-title":"An algorithm for the machine calculation of complex Fourier series. Mathematics of computation 19, 90","author":"Cooley James W","year":"1965","unstructured":"James W Cooley and John W Tukey. 1965. An algorithm for the machine calculation of complex Fourier series. Mathematics of computation 19, 90 (1965), 297\u2013301."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45611-8_28"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3576915.3623096"},{"key":"e_1_3_2_1_19_1","volume-title":"Batching-Efficient RAM using Updatable Lookup Arguments. Cryptology ePrint Archive","author":"Dutta Moumita","year":"2024","unstructured":"Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, Shubh Prakash, and Nitin Singh. 2024. Batching-Efficient RAM using Updatable Lookup Arguments. Cryptology ePrint Archive (2024)."},{"key":"e_1_3_2_1_20_1","volume-title":"cq: Cached quotients for fast lookups. Cryptology ePrint Archive","author":"Eagen Liam","year":"2022","unstructured":"Liam Eagen, Dario Fiore, and Ariel Gabizon. 2022. cq: Cached quotients for fast lookups. Cryptology ePrint Archive (2022)."},{"key":"e_1_3_2_1_21_1","volume-title":"cqlin: Efficient linear operations on KZG commitments with cached quotients. Cryptology ePrint Archive","author":"Eagen Liam","year":"2023","unstructured":"Liam Eagen and Ariel Gabizon. 2023. cqlin: Efficient linear operations on KZG commitments with cached quotients. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_22_1","volume-title":"Zero-Knowledge Location Privacy via Accurate Floating Point SNARKs. arXiv preprint arXiv:2404.14983","author":"Ernstberger Jens","year":"2024","unstructured":"Jens Ernstberger, Chengru Zhang, Luca Ciprian, Philipp Jovanovic, and Sebastian Steinhorst. 2024. Zero-Knowledge Location Privacy via Accurate Floating Point SNARKs. arXiv preprint arXiv:2404.14983 (2024)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_8"},{"key":"e_1_3_2_1_24_1","first-page":"30","article-title":"A generalization of synthetic division and a general theorem of division of polynomials","volume":"30","author":"Fan Lianghuo","year":"2003","unstructured":"Lianghuo Fan. 2003. A generalization of synthetic division and a general theorem of division of polynomials. Mathematical Medley 30, 1 (2003), 30\u201337.","journal-title":"Mathematical Medley"},{"key":"e_1_3_2_1_25_1","volume-title":"Fast amortized KZG proofs. Cryptology ePrint Archive","author":"Feist Dankrad","year":"2023","unstructured":"Dankrad Feist and Dmitry Khovratovich. 2023. Fast amortized KZG proofs. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_26_1","volume-title":"Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT. Cryptology ePrint Archive","author":"Fleischhacker Nils","year":"2024","unstructured":"Nils Fleischhacker, Mathias Hall-Andersen, and Mark Simkin. 2024. Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT. Cryptology ePrint Archive (2024)."},{"key":"e_1_3_2_1_27_1","volume-title":"Jackpot: Non-Interactive Aggregatable Lotteries. Cryptology ePrint Archive","author":"Fleischhacker Nils","year":"2023","unstructured":"Nils Fleischhacker, Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner. 2023. Jackpot: Non-Interactive Aggregatable Lotteries. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_28_1","volume-title":"On Decoding BCH Codes","author":"Forney G. D. Jr.","year":"1965","unstructured":"G. D. Jr. Forney. 1965. On Decoding BCH Codes. IEEE Trans. Inf. Theor. IT-11 (1965), 549\u2013557."},{"key":"e_1_3_2_1_29_1","volume-title":"Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive","author":"Gabizon Ariel","year":"2019","unstructured":"Ariel Gabizon, Zachary J Williamson, and Oana Ciobotaru. 2019. Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive (2019)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243845"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"e_1_3_2_1_33_1","volume-title":"Foundations of data availability sampling. Cryptology ePrint Archive","author":"Hall-Andersen Mathias","year":"2023","unstructured":"Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner. 2023. Foundations of data availability sampling. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_34_1","volume-title":"International algorithmic number theory symposium","author":"Joux Antoine","unstructured":"Antoine Joux. 2000. A one round protocol for tripartite Diffie-Hellman. In International algorithmic number theory symposium. Springer, 385\u2013393."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_11"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42033-7_3"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3339817"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103434"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2856449"},{"key":"e_1_3_2_1_40_1","unstructured":"Ethereum Research. [n. d.]. Data Availability Sampling. https:\/\/notes.ethereum.org\/ReasmW86SuKqC2FaX83T1g. Accessed: 2024-08-05."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56877-1_25"},{"key":"e_1_3_2_1_42_1","unstructured":"SNARKJS. [n. d.]. https:\/\/geometry.xyz\/notebook\/the-hidden-little-secret-in-snarkjs."},{"key":"e_1_3_2_1_43_1","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Srinivasan Shravan","year":"2022","unstructured":"Shravan Srinivasan, Alexander Chepurnoy, Charalampos Papamanthou, Alin Tomescu, and Yupeng Zhang. 2022. Hyperproofs: Aggregating and maintaining proofs in vector commitments. In 31st USENIX Security Symposium (USENIX Security 22). 3001\u20133018."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57990-6_3"},{"key":"e_1_3_2_1_45_1","volume-title":"Modern computer algebra","author":"Zur Gathen Joachim Von","unstructured":"Joachim Von Zur Gathen and J\u00fcrgen Gerhard. 2003. Modern computer algebra. Cambridge university press."},{"key":"e_1_3_2_1_46_1","unstructured":"Lloyd R Welch and Elwyn R Berlekamp. 1983. Error correction for algebraic block codes."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560646"},{"key":"e_1_3_2_1_48_1","volume-title":"Baloo: nearly optimal lookup arguments. Cryptology ePrint Archive","author":"Zapico Arantxa","year":"2022","unstructured":"Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, and Carla Rafols. 2022. Baloo: nearly optimal lookup arguments. Cryptology ePrint Archive (2022)."},{"key":"e_1_3_2_1_49_1","volume-title":"Yanxue Jia and Aniket Kate","author":"Ospina Gracia Zhongtang Luo Alejandra Victoria","year":"2025","unstructured":"Alejandra Victoria Ospina Gracia Zhongtang Luo, Yanxue Jia and Aniket Kate. 2025. Cauchyproofs: Efficient Batch-Updatable KZG Proofs via Cauchy Matrices. iacr:2025\/038 https:\/\/eprint.iacr.org\/2025\/038.pdf"}],"event":{"name":"ASIA CCS '26: ACM Asia Conference on Computer and Communications Security","location":"Bangalore India","acronym":"ASIA CCS '26","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the ACM Asia Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3779208.3785286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T15:41:07Z","timestamp":1780587667000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3779208.3785286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":49,"alternative-id":["10.1145\/3779208.3785286","10.1145\/3779208"],"URL":"https:\/\/doi.org\/10.1145\/3779208.3785286","relation":{},"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"2026-06-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}