Technical Summary: Exploring the Cryptographic Limits of Transformer Networks

Problem Statement

Recent research has demonstrated that colluding AI agents can utilize steganography to exchange malicious information undetected by observers [1]. A critical security implication of this finding is that if a transformer model can implement a cryptographic hash function, it possesses "source-free randomness access," enabling it to generate steganographic channels. While prior work has established the circuit-theoretic limits of saturated transformers (class $\text{TC}^0$) [2] and highlighted the security risks of interacting agents, no concrete work has mapped specific cryptographic constructions—namely Keccak functions, Merkle–Damgård constructions (MDC), and Merkle Trees (MT)—to transformer architectures. This gap leaves open the question of what specific structural resources (depth and width) a transformer requires to compute these cryptographic primitives, which is essential for evaluating the computational capacity and safety of transformer-based AI systems.

Methodology

The authors adopt a systematic circuit-level analysis approach, bridging cryptographic constructions and transformer architectures through the lens of threshold circuits.

1. Circuit Compilation: Using the Reifier library [15], the authors compile boolean functions representing Keccak, MDC, and MT into layered threshold circuits. These circuits are implemented as Multi-Layer Perceptrons (MLPs) with SwiGLU-gated layers. The compiler traces bit operations (AND, OR, NOT) into threshold gates, inserting identity nodes to satisfy the strictly layered structure required by MLPs.
2. Scaling Law Derivation: The authors analyze the compiled circuits to derive verified scaling laws for depth and width. They examine the topology of the circuits to determine how input size, block counts, and cryptographic parameters (e.g., number of rounds, state width) influence the circuit dimensions.
3. Mapping to Transformers: Two distinct mappings from the derived threshold circuits to transformer architectures are proposed:
   • No-Attention Mapping: This approach ignores the attention mechanism, reducing the transformer to its Feed-Forward Network (FFN) sublayers. The entire circuit state is stored within a single token, where the token dimension must accommodate the circuit's maximum width. Each FFN layer simulates one layer of the circuit.
   • Tokens-as-Gates Mapping: This approach assigns each token to represent a single gate in the circuit. Intermediate and output gates are stored in "scratch tokens." The attention mechanism simulates the circuit wiring (summing predecessor values), while the FFN simulates the gate computation (comparing the sum against a threshold). This mapping utilizes unnormalized hard attention to simulate the threshold logic.

Key Contributions

The paper makes three primary contributions:

• Derivation of Scaling Laws: The authors derive and verify constructive scaling laws for the depth and width of threshold circuits implementing Keccak functions, Merkle–Damgård constructions, and Merkle Trees. These laws account for arbitrary input lengths and output sizes.
• Concrete Transformer Mappings: Two specific mappings are proposed that establish constructive upper bounds on the required transformer depth and FFN width to implement these cryptographic constructions.
• Methodology for Capability Evaluation: The work establishes a methodology for deriving structural guarantees on the computational capacity of transformers, offering a principled foundation for evaluating what a transformer of a given depth and width can plausibly compute.

Results

The experiments were conducted on toy instances of the cryptographic constructions (e.g., small state widths and round counts) to understand circuit topology. The results confirm that the derived scaling laws match the actual compiled circuits exactly across all tested configurations.

• Keccak Functions: The circuit depth scales linearly with the number of rounds ($O(n_{rounds})$) and the number of input blocks ($O(n_b)$). The width depends on the state size and the input/output lengths, with specific bottlenecks identified during the absorb and squeeze phases.
• Merkle–Damgård (MDC): These constructions produce deeper but narrower circuits compared to Merkle Trees. The depth scales linearly with the number of input blocks ($O(n_b)$), while the width scales with the compression function width plus the unabsorbed bits.
• Merkle Trees (MT): These constructions produce shallower but wider circuits. The depth scales logarithmically with the number of leaves ($O(\log n_{leaves})$), while the width scales linearly with the number of leaves ($O(n_{leaves})$).
• Mapping Comparison:
  • The No-Attention Mapping results in transformers with depth proportional to the circuit depth but requires FFN widths that grow linearly with the circuit width (and thus input size).
  • The Tokens-as-Gates Mapping maintains constant FFN width (independent of input size) but requires a number of tokens proportional to the total number of gates in the circuit and relies on specific attention routing.

Significance and Limitations

The paper claims to provide the first systematic circuit-level analysis of these cryptographic constructions in the context of transformer expressivity. By establishing constructive upper bounds, the work offers a theoretical framework for AI safety evaluations driven by the computational capacity of the agent. This allows for structural guarantees on what a transformer-based system could compute, which is vital for assessing risks related to steganography and backdoors.

The authors explicitly note several limitations and caveats:

• Constructive vs. Empirical: The mappings are constructive; it remains an open question whether gradient descent can learn to implement these constructions in practice.
• Theoretical Assumptions: The "tokens-as-gates" mapping assumes unnormalized hard attention, which differs from standard softmax-based transformers used in practice.
• Toy Instances: Experiments were conducted on toy instances. The scaling laws contain constants that are artifacts of the Reifier compiler, and it is unconfirmed whether these laws hold without qualification for full-scale Keccak permutations (as used in SHA-3) or production-scale MDCs.

Despite these limitations, the work lays the foundation for a novel class of AI safety evaluations and suggests future directions, such as constructing explicit transformers with specified attention heads, testing learning capabilities via gradient descent, and developing alternative mappings like "tokens-as-states."