Exploring the Cryptographic Limits of Transformer Networks

• URL: http://arxiv.org/abs/2606.29389v1
• Date: Sun, 28 Jun 2026 13:26:01 GMT
• Title: Exploring the Cryptographic Limits of Transformer Networks
• Abstract summary: In recent work it has been shown that colluding AI agents can use steganographic methods to exchange malicious information.<n>This work contributes to by establishing a methodology for deriving structural guarantees on transformer computational capacity.
• Score: 20.614828377572348
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers [50.98108117044413]
  We show that the choice of a graph-to-token map is a fundamental component of transformer expressivity.<n>We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations.
  arXiv  Detail & Related papers  (2026-05-21T13:32:20Z)
• Seeing Through Circuits: Faithful Mechanistic Interpretability for Vision Transformers [54.2202951543048]
  We investigate whether useful mechanistic circuits can be identified through computational graphs in vision transformers.<n>We propose an effective method for Automatic Visual Circuit Discovery (Vi-CD) that recovers class-specific circuits for classification.<n>We find that insightful and actionable edge-based circuits can be recovered from vision transformers, adding transparency to the internal computations of these models.
  arXiv  Detail & Related papers  (2026-04-15T23:25:46Z)
• Distinct mechanisms underlying in-context learning in transformers [5.844274234531923]
  Modern distributed networks, notably transformers, acquire a remarkable ability (termed in-context learning') to adapt their computation to input statistics.<n>We provide a complete mechanistic characterization of this behavior in transformers trained on a finite set $S$ of discrete Markov chains.
  arXiv  Detail & Related papers  (2026-04-14T00:01:14Z)
• Finding Clustering Algorithms in the Transformer Architecture [16.336124248778496]
  We show that transformers can implement a fundamental and widely used algorithm for $k$-means clustering: Lloyd's algorithm.<n>We numerically implement this transformer and demonstrate in experiments the exact correspondence between our architecture and Lloyd's algorithm.<n>Our findings offer a clear and interpretable perspective on implementing precise algorithms in transformers.
  arXiv  Detail & Related papers  (2025-06-23T20:52:01Z)
• On the Existence of Universal Simulators of Attention [17.01811978811789]
  We present solutions to identically replicate attention outputs and the underlying elementary matrix and activation operations via RASP.<n>Our proofs, for the first time, show the existence of an algorithmically achievable data-agnostic solution, previously known to be approximated only by learning.
  arXiv  Detail & Related papers  (2025-06-23T15:15:25Z)
• Algorithmic Capabilities of Random Transformers [49.73113518329544]
  We investigate what functions can be learned by randomly transformers in which only the embedding layers are optimized. We find that these random transformers can perform a wide range of meaningful algorithmic tasks. Our results indicate that some algorithmic capabilities are present in transformers even before these models are trained.
  arXiv  Detail & Related papers  (2024-10-06T06:04:23Z)
• How Transformers Learn Causal Structure with Gradient Descent [44.31729147722701]
  Self-attention allows transformers to encode causal structure. We introduce an in-context learning task that requires learning latent causal structure. We show that transformers trained on our in-context learning task are able to recover a wide variety of causal structures.
  arXiv  Detail & Related papers  (2024-02-22T17:47:03Z)
• AlgoFormer: An Efficient Transformer Framework with Algorithmic Structures [80.28359222380733]
  We design a novel transformer framework, dubbed AlgoFormer, to empower transformers with algorithmic capabilities.<n>In particular, inspired by the structure of human-designed learning algorithms, our transformer framework consists of a pre-transformer that is responsible for task preprocessing.<n>Some theoretical and empirical results are presented to show that the designed transformer has the potential to perform algorithm representation and learning.
  arXiv  Detail & Related papers  (2024-02-21T07:07:54Z)
• TransCMD: Cross-Modal Decoder Equipped with Transformer for RGB-D Salient Object Detection [86.94578023985677]
  In this work, we rethink this task from the perspective of global information alignment and transformation. Specifically, the proposed method (TransCMD) cascades several cross-modal integration units to construct a top-down transformer-based information propagation path. Experimental results on seven RGB-D SOD benchmark datasets demonstrate that a simple two-stream encoder-decoder framework can surpass the state-of-the-art purely CNN-based methods.
  arXiv  Detail & Related papers  (2021-12-04T15:45:34Z)
• Transformers Solve the Limited Receptive Field for Monocular Depth Prediction [82.90445525977904]
  We propose TransDepth, an architecture which benefits from both convolutional neural networks and transformers. This is the first paper which applies transformers into pixel-wise prediction problems involving continuous labels.
  arXiv  Detail & Related papers  (2021-03-22T18:00:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.