Structural Action Bounds for Algebraic Constraint Systems: Toward Complexity-Theoretic ZK Security

Abstract

Zero-knowledge proof security rests on cryptographic reductions: breaking a ZK scheme requires breaking an underlying hard problem. We introduce an independent, complementary security analysis based on the Structural Action Principle. We extend the discrete action functional S[psi] = sum_t lambda(s_t) from Boolean CDCL trajectories to algebraic constraint systems over finite fields F_p, defining an Algebraic Structural Action with density functions that recover Groebner basis complexity, Polynomial Calculus proof size, algebraic degree growth, and elimination ordering as mechanical analogues. We prove a non-circular lower bound for preimage search in substitution-permutation network (SPN) hash functions: for a k-round SPN with S-box degree alpha and state width t, the preimage search system is a square polynomial system of k*t degree-alpha equations in k*t variables. Under the semi-regularity assumption (standard in algebraic cryptanalysis, empirically verifiable, and independent of any cryptographic security conjecture), the solving degree d_reg is determined by the Hilbert series H(z) = (1 - z^alpha)^{k*t}/(1-z)^{k*t}. We establish two action bounds: a peak bound S[psi] >= d_reg (any trajectory must encounter degree d_reg), and a stronger cumulative bound S[psi] >= sum_{d=alpha}^{d_reg-1} h_d using the Hilbert function coefficients as density, which captures the total algebraic work rather than just the peak degree. For Poseidon (alpha=5, t=3, k=8): d_reg = 97 and the cumulative bound gives S[psi] >= 2^{56}. The result applies to ANY SPN hash function (Rescue, Griffin, Anemoi, MiMC) and provides a second line of defense for Behavior-Bound Signature (BBS) security, grounded in algebraic proof complexity rather than crypto- graphic hardness assumptions. Keywords: structural action principle, algebraic proof complexity, polynomial calculus, semi-regularity, Hilbert function, SPN hash functions, zero-knowledge security, behavior-bound signatures