Bicategorical Semantics for Nondeterministic Computation

Mike Stay, Jamie Vicary

Abstract

This paper introduces a high-level graphical language based on bicategory theory to model classical cryptographic protocols. By representing public and private information as different geometric dimensions, the authors reveal a startling mathematical identity: classical one-time pad encryption is formally identical to quantum teleportation.

Introduction

In classical information theory and computer science, reasoning about "public" and "private" data often relies on type systems or logic. However, these methods can feel disconnected from the structural reality of information flow. Public information is typically stored redundantly across systems, making it accessible but difficult to modify locally. Conversely, private information is local and mutable by its owner. This paper addresses the lack of a unified structural framework that captures these distinctions naturally through geometry.

Methodology: Symmetric Monoidal Bicategories

The authors utilize Symmetric Monoidal Bicategories, specifically 2Rel (the bicategory of matrices of relations), to build their model.

Graphical Calculus

The core of the methodology is a 2D "spacetime diagram" calculus where information flow is visualized geometrically:

  • 1D Lines: Represent private computational systems or "worldlines."
  • 2D Shaded Regions: Represent public information distributed across space.
  • Vertices: Represent computational processes such as encryption, decryption, or publication.
Figure 1: Graphical identity representing a cryptographic protocol, showing the equivalence between a complex process and its simplified effect.

Nondeterminism and Topology

To model the randomness essential for cryptography (e.g., key generation), the authors use the category Rel (sets and relations). In this setting, a "function" can have multiple possible outputs, representing nondeterministic choice. Security protocols are verified using topological reasoning. If a protocol's diagram can be deformed into its intended effect without breaking lines, the protocol is mathematically sound.

Key Insights

Dimensional Security

The most elegant idea is the geometric distinction: private info is a 1D string (local), while public info is a 2D region (distributed). This makes it physically impossible within the diagrammatic language to "locally" modify a public region, enforcing a strong form of locality that mirrors real-world security constraints.

The Quantum-Classical Connection

A significant discovery is that the graphical equation for a one-time pad (classical encryption) is identical to the equation for quantum teleportation. Similarly, secret sharing maps perfectly to quantum dense coding. This suggests a deep structural unity between classical and quantum information processing that is often obscured by traditional algebraic notation.

Figure 2: A complex graphical representation of interacting processes within the bicategorical framework.

Results and Conclusion

The authors successfully modeled one-time pads, secret sharing, and Diffie-Hellman key exchange. They demonstrated that primary security properties—such as the fact that deleting a key renders ciphertext indistinguishable from noise—can be proven by simply sliding boxes along lines and simplifying regions, rather than through complex algebraic manipulation.

While currently limited to discrete groupoids and nondeterminism (rather than full probability), this work provides a concrete semantics in 2Rel where abstract diagrams correspond to actual classical procedures. Future work aims to extend this to arbitrary abelian groupoids and probabilistic analysis to capture more complex real-world security parameters.

Summary updated

BibTeX
@inproceedings{stay2013bicategorical,
  author = {Mike Stay and Jamie Vicary},
  title = {{Bicategorical Semantics for Nondeterministic Computation}},
  booktitle = {MFPS},
  year = {2013},
  url = {https://openreview.net/forum?id=QiIWs9O6xV},
}
Figure