Paper 2024/504
Polylogarithmic Proofs for Multilinears over Binary Towers
Abstract
We present a succinct polynomial commitment scheme for multilinears over tiny binary fields, including that with just two elements. To achieve this, we develop two main ideas. Our first adapts Zeilberger, Chen and Fisch's BaseFold ('23) PCS to the binary setting; it uses FRI (ICALP '18)'s lesser-known binary variant, and reveals a new connection between that work and Lin, Chung and Han (FOCS '14)'s additive NTT. We moreover present a novel large-field-to-small-field compiler for polynomial commitment schemes. Using a technique we call "ring-switching", our compiler generically bootstraps any multilinear PCS over a large, power-of-two degree extension field into a further PCS over that field's ground field. The resulting small-field PCS lacks embedding overhead, in that its commitment cost is identical to that of the large-field scheme on each input size (measured in bits). We attain concretely small proofs for enormous binary multilinears, shrinking the proofs of Diamond and Posen ('23) by an order of magnitude.
Note: Clarified and improved Subsection 3.1; fixed a few minor typos.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- binary fieldssuccinct argumentsproximity testing
- Contact author(s)
-
bdiamond @ irreducible com
jposen @ irreducible com - History
- 2024-11-01: last of 4 revisions
- 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},
url = {https://eprint.iacr.org/2024/504}
}
