Treffer: The Bateson One-Way Function: Formal Definition, Cryptographic Hardness, and Empirical Irreversibility

We present a rigorous formalization of the Bateson One-Way Function, a novel framework for cryptographic irreversibility rooted in symbolic grammar theory rather than number theory. We define the function based on a formal grammar comprising messages, interpretive frames, and a canonicalization process. Irreversibility arises from "frame suppression," where the context of interpretation is discarded. We establish the function's potential for cryptographic hardness through two distinct arguments. First, we define the Semantic Inference Problem (SIP)—the difficulty of recovering a hidden frame—and prove its average-case hardness via a reduction from Planted 3-SAT. This demonstrates that the Bateson framework can encode hard inference problems. Second, we characterize the conditions required for a Bateson instantiation to be a secure One-Way Function (OWF) using the established equivalence between OWFs and the hardness of time-bounded Kolmogorov complexity (pKt). We introduce a taxonomy distinguishing between ambiguity-based (compressing) and complexity-based (expanding) Bateson functions, and quantify information loss using Symbolic Degeneracy ($\Delta_{G}$). This work solidifies the Bateson function's theoretical foundation as a candidate for non-algebraic, post-quantum cryptography.