Crypto Seminar - Hadas Zeilberger March 13, 2025 4:30pm — 5:30pm Location: In Person and Virtual - ET - Blelloch-Skees Conference Room and Zoom Speaker: HADAS ZEILBERGER, Ph.D. Student, Department of Computer Science, Yale University https://scholar.google.com/citations?user=Mk9aWG0AAAAJ&hl=en Two successful techniques have recently emerged in the construction of SNARKs with extremely fast provers; The use of multilinear (instead of univariate) polynomial commitment schemes (PCS) and the construction of PCS from error-correcting codes. Recently, BaseFold (Crypto 2024) introduced a family of PCS that combine these two techniques, thereby achieving a better tradeoff between prover and verifier costs than the state of the art. Despite its impressive overall efficiency, BaseFold suffered from larger proof sizes than its univariate counterparts, due to unproven claims about linear codes, which were not relevant in the univariate setting. This work closes this gap by proving a new fact about linear codes – that if if πL, πR are two vectors in 𝔽n and if πL + r πR is close to C, then πL, πR and (πL + r πR) all agree with codewords at positions indexed by the same set S, except with negligible probability over r ← 𝔽. Our result holds as long as |S| > (1 - ΔC + ε)1/3, and with failure probability smaller than 2/ε2|𝔽| . Furthermore, our results extend to any finite field and any linear code. In Person and Zoom Participation. See announcement. Event Website: https://sites.google.com/view/crypto-seminar/home Add event to Google Add event to iCal
