# Exploring the Cryptographic Limits of Transformer Networks

arXiv: https://arxiv.org/abs/2606.29389 · HTML: https://mlsanity.com/paper/2606.29389/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 28 Jun 2026.

## Builds on (most cited first, 6 of 6)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Secret Collusion among AI Agents: Multi-Agent Deception via Steganography](https://mlsanity.com/paper/2402.07510/) (2024)
- [Revealing Robust Oil and Gas Company Macro-Strategies using Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.11043/) (2022)
- [Unelicitable Backdoors in Language Models via Cryptographic Transformer Circuits](https://mlsanity.com/paper/2406.02619/) (2024)

## Built on by (most cited first, 1 of 1)

- [Hidden Reasoning Must Leak, but Need Not Be Readable: Fundamental Opportunities and Limits for Chain-of-Thought Monitoring](https://mlsanity.com/paper/2609.37312/) (2026)

## Abstract (arXiv)

In recent work it has been shown that colluding AI agents can use steganographic methods to exchange malicious information. Whether a transformer can implement steganographic methods depends on what cryptographic functions it can implement, since a transformer that can implement a cryptographic function within its layers has source-free randomness access. Despite existing circuit-complexity results, no prior work maps specific cryptographic constructions to transformer architectures. As Merrill et al. have shown that saturated transformers can be seen as threshold circuits, we first generate threshold circuits for three different cryptographic constructions (Keccak functions, Merkle--Damgard constructions and Merkle Trees) and then map these circuits to different transformer architectures. We derive verified scaling laws for the width and depth of the circuits which implement each cryptographic construction and propose two different mappings: no-attention mapping, tokens-as-gates mapping. Beyond its security implications, this work contributes to by establishing a methodology for deriving structural guarantees on transformer computational capacity. Specifically, we derive constructive upper bounds on what a transformer of a given depth and width could plausibly compute, providing a principled foundation for capability evaluations of transformer-based AI systems.