Paper 2024/504

Polylogarithmic Proofs for Multilinears over Binary Towers

Benjamin E. Diamond, Ulvetanna
Jim Posen, Ulvetanna

We introduce a polylogarithmic-verifier polynomial commitment scheme for multilinears over towers of binary fields. To achieve this, we adapt an idea of Zeilberger, Chen and Fisch's BaseFold ('23) to the setting of binary towers, using FRI (ICALP '18)'s binary-field variant. In the process, we reinterpret Lin, Chung and Han (FOCS '14)'s novel polynomial basis so as to make apparent its compatibility with FRI. We moreover introduce a "packed" version of our protocol, which supports—with no embedding overhead during its commitment phase—multilinears over tiny fields (including that with just two elements). Our protocol leverages a new multilinear FRI-folding technique, and exploits the recent tensor proximity gap of Diamond and Posen (Commun. Cryptol. '24). We achieve concretely small proofs for enormous binary multilinears, shrinking the proofs of Diamond and Posen ('23) by an order of magnitude.

Available format(s)
Cryptographic protocols
Publication info
binary fieldssuccinct argumentsproximity testing
Contact author(s)
bdiamond @ ulvetanna io
jposen @ ulvetanna io
2024-04-01: approved
2024-03-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin E. Diamond and Jim Posen},
      title = {Polylogarithmic Proofs for Multilinears over Binary Towers},
      howpublished = {Cryptology ePrint Archive, Paper 2024/504},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.