This talk is about the security of Incrementally Verifiable Computation (IVC) and will describe a recent work with Dario Fiore and Mahak Pancholi with the same title. (see link at the end of the abstract) IVC allows one to prove the correctness of a computation of potentially unbounded length (or depth) in an incremental way, while a computationally weak client can efficiently check its correctness in time sublinear in the computation’s length. IVC systems are of practical relevance; yet, most existing IVC schemes are only provably secure for constant-depth computations. Arguing their security for computations of polynomial depth relies on heuristic assumptions, raising both theoretical and practical concerns. More generally, it remains unclear whether these schemes are genuinely insecure at superconstant depths or whether our current proof techniques are simply insufficient.

In this work, we delve into the security foundations of incremental proof systems, while at the same time looking for new approaches to prove (or disprove) security at superconstant depths. To this end, we study the relation between the depth of the target computation and IVC security as a question in its own right. Specifically, we ask:

1) How does a proof system’s security degrade with depth? We show an inherent pattern in the security of IVC: either an IVC is secure for computations of arbitrary depths, or it will show a “finite ladder” of security degradation at faster growing depths.

2) Can we prove an IVC secure at depth d = ω(1) if it satisfies a “weak” security property at some larger depth D? We uncover an intriguing connection between infinitely-often soundness (guaranteed to hold only for some infinite set of parameters) and standard soundness in IVC: a scheme that is infinitely-often sound at depth D achieves standard soundness at some smaller depth d that grows more slowly than D.

3) Depth boosting: If there exists an IVC scheme secure at depth d, does there exist one secure at a greater depth? We show a general boosting technique: given an IVC secure at depth d, we can construct one secure at depth D = d^ρ for any function ρ such that d^ρ remains polynomially bounded (ρ may even be superconstant). This allows us to systematically amplify security from modest depths to much greater ones–for example, from constant to polynomial depth–with only a logarithmic overhead.

Our results apply to both deterministic and non-deterministic computations across various soundness notions, including those for incremental functional commitments (IFC), a streaming variant of functional commitments that we introduce. The current version of our work is available at: https://eprint.iacr.org/2025/1413