Proximity Gaps for Multilinear Interactive Oracle Proofs

Add to your list(s) Download to your calendar using vCal

• Hadas Zeilberger (Yale)
• Thursday 25 September 2025, 10:00-11:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

A set displays a (delta, gamma)-proximity gap to a linear code, C, if either all elements are delta-close in relative Hamming distance to a codeword in C or only gamma of them are. Proximity gaps of the set A_{v,u} := {v + r u : r in F }, for fixed vectors v,u, are fundamental to the security and efficiency of an extremely efficient family of Interactive Oracle Proofs (IOPs) from FRI (ICALP 2018), where larger delta implies more efficient verifiers and smaller gamma implies more efficient provers.

Building on FRI , the authors of BaseFold (Crypto 2024) introduced a new family of IOPs with concretely faster provers. However, BaseFold additionally requires that if all elements of A_{v,u} are close to the code, then they all agree with their respective nearest codewords in a fixed, shared set of locations.

We prove this to be true for all linear codes when delta < 1 – (1 – Delta + epsilon)^{1/3} – eta and gamma < 1/(epsilon eta) (where Delta is the relative minimum distance of the code). This improves the previous bound of delta < 1 – (1 – Delta/3) – eta from BaseFold, and it recovers the original proximity gaps result for linear codes, which is proven to be tight in DEEP -FRI (ITCS 2020).

link to paper: https://eprint.iacr.org/2024/1843.pdf

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk449

Note that ex-directory lists are not shown.