Paper 2024/504
Polylogarithmic Proofs for Multilinears over Binary Towers
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- binary fieldssuccinct argumentsproximity testing
- Contact author(s)
-
bdiamond @ ulvetanna io
jposen @ ulvetanna io - History
- 2024-04-01: approved
- 2024-03-29: received
- See all versions
- Short URL
- https://ia.cr/2024/504
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/504,
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{https://eprint.iacr.org/2024/504}},
url = {https://eprint.iacr.org/2024/504}
}
