The Labyrinth on the Lattice: A structural analogy between maze navigation and lattice-based post-quantum cryptography

• Introduction
• Integer lattices and hard problems
• The maze as a combinatorial structure
• The maze–lattice correspondence
  • Lattice points as intersections
  • Walls as basis constraints
  • CVP as pathfinding
• Complexity parallel
  • Dimensional scaling
  • The basis-quality gap
  • Trapdoor one-way functions
• Interactive visualisation
• Limitations of the analogy
• References

Lattice-based cryptography underpins the recently standardised post-quantum key-encapsulation and digital-signature schemes ML-KEM (FIPS 203) and ML-DSA (FIPS 204). The computational hardness assumptions on which these schemes rely — the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) — are defined over high-dimensional integer lattices, a setting that resists everyday geometric intuition. This post establishes a structural analogy between two-dimensional lattice problems and the classic maze navigation problem, as embodied by the Atari-era labyrinth game, and provides an interactive HTML visualisation to accompany the discussion.

Introduction

The National Institute of Standards and Technology (NIST) completed its post-quantum standardisation process in 2024 with the publication of FIPS 203 (ML-KEM, derived from CRYSTALS-Kyber) and FIPS 204 (ML-DSA, derived from CRYSTALS-Dilithium) [1, 2]. Both standards rely on the presumed hardness of problems defined over module lattices, specifically the Module Learning With Errors (MLWE) problem, which reduces to approximate versions of SVP and CVP.

A persistent obstacle in teaching lattice cryptography to new audiences — system administrators, security engineers, and policy stakeholders who must deploy these algorithms — is that the underlying geometry lives in dimensions far beyond direct visualisation. Two-dimensional lattice diagrams appear in every introductory textbook, yet they convey structure without conveying hardness: in two dimensions, both SVP and CVP are solvable in polynomial time, and the diagrams offer no experiential intuition for why the problems become intractable at higher dimensions.

This post proposes a remedy by mapping the lattice problem onto a structure the audience already understands: a maze. Specifically, we show that the classic labyrinth game — a perfect maze on a rectangular grid, navigated by a player who sees only local surroundings — reproduces, in miniature, the essential features of a lattice-based cryptographic scheme:

1. A regular grid of points generated by basis vectors (the lattice).
2. A target point that the solver must reach (the CVP instance).
3. A secret short path that the key holder can traverse directly (the good basis / trapdoor).
4. A combinatorial explosion that forces an uninformed solver into exhaustive search (the bad basis / public key).

Integer lattices and hard problems

Let b₁, …, b_n ∈ ℝ^m be linearly independent vectors. The lattice generated by these vectors is

ℒ(B) = { ∑ z_i b_i : z_i ∈ ℤ }

where B = [b₁ | … | b_n] is the basis matrix.

A lattice admits infinitely many bases. Two bases B and B′ generate the same lattice if and only if B′ = UB for some unimodular matrix U with |det U| = 1. A good basis consists of short, nearly orthogonal vectors; a bad basis consists of long, highly skewed vectors. The Lenstra–Lenstra–Lovász (LLL) algorithm [3] can reduce a basis to a moderately short form in polynomial time, but producing a basis whose vectors are close to the successive minima remains hard in general.

The Shortest Vector Problem (SVP): given a basis B of a lattice ℒ, find a nonzero lattice vector v ∈ ℒ such that ‖v‖ is minimised.

The Closest Vector Problem (CVP): given a basis B of a lattice ℒ and a target vector t ∈ ℝ^m, find v ∈ ℒ that minimises ‖t − v‖.

Both SVP and CVP are NP-hard under randomised reductions [4, 5]. The best known algorithms for exact SVP run in time 2^Θ(n) where n is the lattice dimension [6].

The maze as a combinatorial structure

A perfect maze on an N × N grid is a spanning tree of the N²-vertex grid graph G = (V, E) where V = {0, …, N−1}² and E connects each vertex to its horizontal and vertical neighbours. Removing edges from E that are not in the spanning tree produces the walls of the maze. Because a spanning tree is connected and acyclic, exactly one path exists between any two vertices — in particular, between the start cell (0, 0) and the target cell (N−1, N−1).

The standard recursive-backtracker algorithm generates such a maze by performing a randomised depth-first traversal of G, carving passages by removing walls between the current cell and an unvisited neighbour chosen uniformly at random [8].

The maze–lattice correspondence

Let ℳ be a perfect maze on an N × N grid and let ℒ = ℤ² be the standard two-dimensional integer lattice. The following table summarises the correspondence.

Maze element	Lattice-crypto concept
Grid intersection	Lattice point v ∈ ℒ
Cell adjacency	Basis vector direction
Maze walls	Constraints induced by the public basis
Unique path start→target	Babai-like decoding with trapdoor
Knowledge of the path	Possession of a good (short) basis
Fog of war (local view only)	Possession of only the public (bad) basis
Path length	‖t − v‖ (CVP distance)
Grid size N	Lattice dimension n

Lattice points as intersections

The (N+1)² intersections of the N × N grid are in natural bijection with the lattice points {0, 1, …, N}² ⊂ ℤ². The two standard basis vectors e₁ = (1, 0) and e₂ = (0, 1) generate horizontal and vertical adjacency, respectively. Every cell of the maze is bounded by four lattice points, and every passage connects two cells that share a pair of lattice points.

Walls as basis constraints

In a lattice cryptosystem the public key is a “bad” representation of the lattice: the basis vectors are long and nearly parallel, so that enumerating short vectors requires exponential work. In the maze analogy, the walls play an equivalent role. Although the underlying grid (the lattice) is regular, the walls remove most direct connections, forcing the solver onto a winding path. The solver who knows the spanning tree (the good basis / private key) traverses the maze in the minimum number of steps; the solver who sees only a local neighbourhood (the bad basis / public key) must search.

CVP as pathfinding

The target cell (N−1, N−1) serves as the target vector t. The solver’s task — navigate from (0, 0) to (N−1, N−1) through the constrained graph — is structurally parallel to CVP: find the lattice point closest to t using only the information encoded in the basis. In the maze, “closest” is measured in passage steps (the graph metric on the spanning tree) rather than Euclidean distance, but the qualitative role is identical: the solver seeks the shortest connection in a high-branching search space.

A solver with full knowledge of the maze (the good basis) reaches the target in exactly |P*| steps. A solver restricted to observing only cells within radius r of its current position (the bad basis) requires, in the worst case, Θ(N²) steps — the entire maze must be explored.

Complexity parallel

The analogy is qualitative rather than reduction-theoretic: solving a two-dimensional maze is in P (breadth-first search runs in O(N²) time), while SVP and CVP are NP-hard. The pedagogical value lies not in equating the two complexities but in mapping the structure of the hardness gap onto a lived experience.

Dimensional scaling

In lattice cryptography the security parameter is the lattice dimension n. The best known algorithms for exact SVP have running time 2^Θ(n); for the approximate versions used in ML-KEM, the concrete dimension n = 512 or n = 768 places the problem beyond feasible computation.

In the maze the corresponding parameter is the grid side length N. A solver under fog of war (bad basis) faces a search space that grows as N², and the ratio of actual search cost to the optimal path length grows with N. While the growth is polynomial rather than exponential, the experiential effect is the same: increasing N from 10 to 24 makes the maze feel qualitatively different, and this felt transition is the point of the analogy.

The basis-quality gap

The central intuition that the analogy conveys is the basis-quality gap: the same lattice, presented through a good basis, admits efficient algorithms (Babai’s nearest-plane algorithm, for instance, runs in polynomial time given a sufficiently reduced basis [7]), while the same lattice presented through a bad basis resists all known approaches. In the interactive visualisation below, toggling between “good basis” mode (the solution path is highlighted) and “bad basis” mode (fog of war, radius-limited visibility) lets the user experience this gap directly. The maze is unchanged; only the solver’s information changes.

Trapdoor one-way functions

A lattice-based key-encapsulation mechanism (ML-KEM) works as follows, at a high level:

1. Key generation produces a lattice together with a short (good) basis, which is kept secret, and publishes a description of the same lattice through a bad basis.
2. Encapsulation adds a small error vector to a lattice point, producing a ciphertext that is close to the lattice but not on it.
3. Decapsulation uses the good basis to round the ciphertext back to the nearest lattice point (solving a CVP instance), recovering the shared secret.

In the maze analogy:

1. The maze is published (walls visible to all); the spanning-tree structure (the solution) is kept secret.
2. A target cell is announced.
3. The key holder walks directly to the target (using the known path); an attacker must search under fog of war.

Interactive visualisation

The game below implements the analogy as a playable Atari-era labyrinth. Grid intersections are marked as lattice points (amber dots). Toggle between “good basis” (shortest path highlighted) and “bad basis” (fog of war: only cells within radius 2 are visible). The step counter alongside the optimal path length makes the cost of uninformed search quantitative. Four selectable grid sizes (10×10 to 24×24) demonstrate dimensional scaling. Controls: arrow keys, WASD, touch swipe, or the on-screen D-pad.

PQC LATTICE LABYRINTH

Post-Quantum Cryptography — Lattice Problem Visualiser

STEPS: 0

OPTIMAL: ?

SIZE: 10×10

VECTOR FOUND

You solved the Closest Vector Problem in 0 steps. The optimal path was 0 steps.

In a real lattice the dimension is 512+, making brute-force search infeasible — this is the security guarantee behind ML-KEM and ML-DSA.

Lattice point Search agent Target vector

LATTICE ANALOGY
Each intersection is a lattice point in Z². The maze walls encode a basis representation: a good basis (short, nearly orthogonal vectors) reveals the shortest path; a bad basis (long, skewed) forces local search with no global view — analogous to the Closest Vector Problem (CVP) that underpins ML-KEM / CRYSTALS-Kyber.

Navigate the agent to the target vector. Arrow keys, WASD, or the D-pad.

Limitations of the analogy

The maze–lattice correspondence is pedagogical, not formal in the complexity-theoretic sense. Several caveats apply.

1. The maze is two-dimensional. Lattice problems become hard only at high dimensions (n ≥ 256 in practice). The analogy communicates the qualitative shape of the hardness gap but cannot reproduce its quantitative strength.
2. Maze solving is in P. Even under fog of war, a systematic solver (depth-first search with backtracking, Trémaux’s algorithm) visits every cell in O(N²) time. SVP and CVP are NP-hard, and their approximate versions are conjectured to require super-polynomial time.
3. The maze has exactly one path between any two cells (it is a tree). A lattice has infinitely many short vectors, and approximate SVP/CVP may have many valid solutions.
4. The error term in Learning With Errors (LWE) — the small random perturbation that makes decryption a rounding problem — has no direct analogue in the maze. One could introduce stochastic wall placement or noisy movement, but the resulting game would obscure rather than clarify the core analogy.
5. The maze walls are visible in both modes; only the solution path is hidden. In the cryptographic setting, the “walls” (the bad basis) are all the attacker has — the lattice structure itself is public, and the attacker has no forbidden directions, only an astronomically large search space.

These limitations should be stated explicitly when the visualisation is used in a teaching context. The analogy is a scaffold, not a proof.

References

1. National Institute of Standards and Technology, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 2024. doi:10.6028/NIST.FIPS.203
2. National Institute of Standards and Technology, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 2024. doi:10.6028/NIST.FIPS.204
3. A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol. 261, no. 4, pp. 515–534, 1982. doi:10.1007/BF01457454
4. M. Ajtai, “The shortest vector problem in L₂ is NP-hard for randomized reductions (extended abstract),” in Proc. 30th ACM Symposium on Theory of Computing (STOC), pp. 10–19, 1998. doi:10.1145/276698.276705
5. D. Micciancio, “The shortest vector problem is NP-hard to approximate to within some constant,” SIAM Journal on Computing, vol. 30, no. 6, pp. 2008–2035, 2001. doi:10.1137/S0097539700373039
6. D. Aggarwal, D. Dadush, O. Regev, and N. Stephens-Davidowitz, “Solving the Shortest Vector Problem in 2ⁿ time using discrete Gaussian sampling,” in Proc. 47th ACM Symposium on Theory of Computing (STOC), pp. 733–742, 2015. doi:10.1145/2746539.2746606
7. L. Babai, “On Lovász’ lattice reduction and the nearest lattice point problem,” Combinatorica, vol. 6, no. 1, pp. 1–13, 1986. doi:10.1007/BF02579403
8. D. B. Wilson, “Generating random spanning trees more quickly than the cover time,” in Proc. 28th ACM Symposium on Theory of Computing (STOC), pp. 296–303, 1996. doi:10.1145/237814.237880

Categories: ATARI, basis, CRYSTALS-Dilithium, CRYSTALS-Kyber, CVP, FIPS 203, FIPS 204, game, labyrinth, lattice, maze, ML-DSA, ML-KEM, post-quantum cryptography, PQC, SVP, vectors