Paper 2025/737

FICS and FACS: Fast IOPPs and Accumulation via Code-Switching

Pratyush Mishra, University of Pennsylvania

Tushar Mopuri, University of Pennsylvania

Matan Shtepel, Carnegie Mellon University

Abstract

Recent work on IOP-based succinct arguments has focused on developing IOPs that improve prover efficiency by relying on linear-time encodable codes. We present two new schemes for improving the efficiency of such succinct arguments: $\quad \bullet$ $\mathsf{FICS}$, an IOP of proximity for multilinear polynomial evaluation that, like prior work Blaze [EUROCRYPT 2025] achieves linear prover time, but additionally reduces the verifier oracle query complexity to $O(\lambda \log \log n + \log n)$ for codewords of length $n$. $\quad \bullet$ $\mathsf{FACS}$, an accumulation scheme for NP that achieves linear prover time and $O(\lambda)$ oracle queries per step of the accumulation. Both schemes support a large class of linear-time encodable codes, including systematic LDPC codes and tensor codes of linear-time encodable codes. We obtain our results by extending and formalizing the framework of Interactive Oracle Reductions (IORs) introduced by Ben-Sasson et al. [TCC 2019]. In particular, we develop new IORs for "codeswitching" tensor codes (Ron-Zewi and Rothblum [JACM 2024]), and also develop a new notion of knowledge soundness for IORs that allows us to easily compose IORs and to prove the security of our schemes in the non-interactive setting, even if the underlying codes are not known to be decodable in polynomial time.

Note: Changed publication information, and modified pdf to match published version.

@misc{cryptoeprint:2025/737,
      author = {Anubhav Baweja and Pratyush Mishra and Tushar Mopuri and Matan Shtepel},
      title = {{FICS} and {FACS}: Fast {IOPPs} and Accumulation via Code-Switching},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/737},
      year = {2025},
      url = {https://eprint.iacr.org/2025/737}
}