Paper 2026/2019

The Residue Is the Resource: Exact Fresh-State Complexity, Reconstruction Limits, and Challenge Design in Folding

Abstract

Folding protocols cross public-randomness boundaries: input-dependent information must be fixed before a challenge is known, while the required output may depend on it. We ask how much state must be retained after accounting for information already available at the boundary. With unrestricted prechallenge preprocessing and linear postchallenge readout, a retained representation is feasible exactly when its coordinates span, modulo this available information, every output direction induced by the supported challenges. Thus the minimum retained width is the dimension of this residual output space. The width depends on both the admissible source domain and the actual challenge support. Coordinatewise multiplication of length-\(n^2\) vectors has width \(n^2\) on the full product domain but \(2n-1\) when both inputs lie in the dimension-\(n\) Reed--Solomon code evaluated at \(n^2\) distinct points. Below the exact-width threshold, for independent uniform inputs to a bilinear map, we characterize the optimal exact-reconstruction probability by a rank-weighted subspace optimization. Bilinear side information couples the missing directions through a common linear correction, so optimizing them independently can fail. Applying the framework to direct homogeneous quadratic folding on a full product domain, an algebraic separation condition on the challenge family forces width at least \(rk\), where \(r\) is the dimension of the span of mixed bilinear outputs. Scaled-Cauchy challenges attain this bound on any support of at least \(2k+1\) distinct non-pole values and yield an explicit matching \(rk\)-coordinate polynomial representation.