Placement is a Primitive

Abstract

Arithmetization-oriented (AO) hash functions are the dominant cost in zero-knowledge proof systems, and their security against the strongest known attacks rests on the hardness of the constrained-input constrained-output (CICO) problem, solved by Gröbner-basis techniques. Raising the nominal algebraic degree of a design is known not to suffice, as recent attacks (FreeLunch, CheapLunch, resultant methods) have repeatedly shown. This work identifies a positional design lever for AO substitution-permutation networks over the Goldilocks field with the power-map S-box x^7: folding a low-degree quadratic coupling into the input of the S-box adds one bit of CICO ideal degree per round, whereas the same coupling placed in the linear layer or after the S-box adds nothing. The ideal degree follows the measured law D_I = 7^(R·m) · m · 2^(R−1) against a baseline of 7^(R·m), where R is the number of rounds and m the number of free input branches. Measurements in the msolve Gröbner engine indicate that the added degree is genuine rather than a nominal inflation (the F4 solving degree rises; an auxiliary-variable-free model reproduces the ideal degree; a resolved large instance rules out competing laws), that it is generic across four unrelated coupling patterns, that it is independent of the coupling density (one term per round suffices), and that it carries no differential/linear cost. The principle is instantiated as Alaniz-AO, a Goldilocks sponge whose HADES partial-round schedule reaches 0.74x the constraint cost of Poseidon2 at a 128-bit target under an explicit ω=2 cost model. A secondary result: the branch number of the linear layer does not govern algebraic CICO security. Measurements are reproducible and use proxy primes sharing the exponent structure of Goldilocks. Round counts and cost figures are extrapolations from the measured degree law under the stated cost model; instances beyond three rounds exceed the solver on commodity hardware and are reported as gaps. A reference implementation and reproduction scripts accompany the paper.