The Secret Maze

1: Hidden in Plain Sight

Imagine you need to send a secret message to a friend. In a world of surveillance and interception, how can you hide your communication in something that looks completely innocent?

Welcome to the world of steganography: the art of hiding messages in plain sight. In contrast to cryptography, which makes messages undecipherable, steganography makes them invisible.

Today, we'll explore how we can hide binary messages inside the structure of mazes.

We'll start by discussing some foundational material, quickly touch upon a paper this work was inspired by, then go into an explanation of the research behind this work.

2: Creating the Perfect Maze

Before we can hide messages, we need to create a maze to hide it in. We'll stick to perfect mazes A perfect maze is a spanning tree - a graph where every cell connects to every other cell by exactly one path, with no loops or isolated areas. for now.

We use the recursive backtracker algorithm, which works like an explorer carving passages through solid rock. It keeps going forward until it hits a dead end, then backtracks to find unexplored areas. You can actually use whichever algorithm you like here (there are a lot!) - for simplicity we've kept it to just one.

3: The Secret Keys

To hide a message, both the sender and receiver need to agree on two key vertices in the maze. These are a shared secret that determines how and where the message will be hidden.

The unique path between these vertices forms what we call the hidden tree — a connected subtree of the maze that only the sender and the receiver know about. This is where the magic happens — we'll embed our message along its edges in a way that's invisible to anyone who doesn't know the keys.

4: Finding the Hiding Spots

Not every location along the path can hide information. We need to find special cells called embeddable vertices — these are cells ON the solution path that have neighbors NOT on the path. These off-path neighbors provide the walls we can manipulate to encode our message.

function FIND-EMBEDDABLE-EDGES(maze, key):
    hiddenTree = SOLVE-MAZE(key[0], key[1])
    embeddableEdges = []
    
    for vertex in hiddenTree:
        neighbors = GET-NEIGHBORS(vertex) - hiddenTree
        if |neighbors| == 1:
            embeddableEdges.add((vertex, neighbors[0]))
        else if |neighbors| == 2:
            embeddableEdges.add((vertex, neighbors[0]))
            embeddableEdges.add((vertex, neighbors[1]))
    
    return embeddableEdges

function EMBED(maze, message, key):
    edges = FIND-EMBEDDABLE-EDGES(maze, key)
    keepEdges = hiddenTree.edges
    discardEdges = []
    
    for i in 0..message.length:
        if message[i] == 1:
            keepEdges.add(edges[i])
        else:
            discardEdges.add(edges[i])
    
    return REGENERATE-MAZE(keepEdges, discardEdges)

5: Hiding the Message

Using the EEDGE algorithm, we encode our binary message by choosing which walls to keep or remove.

6: Making It Look Natural

We have our embedded walls, but it's not a maze if it just has isolated walls. We use Kruskal's algorithm to regenerate a valid maze that preserves our hidden message.

The algorithm adds random walls while ensuring:

• The maze remains valid (no loops)
• Our embedded walls stay exactly as needed
• The result looks similar to any other random maze

7: Revealing the Secret

The receiver uses the same key vertices to find the solution path, identify the embeddable locations, and read the message from the wall patterns.

The key insight here is that without knowing the exact key vertices, finding the message is computationally difficult. The number of possible key combinations is quite large.

8: The Complete Picture

You've now experienced the full journey of maze steganography — from generating a perfect maze to extracting a hidden message. But this interactive demo only scratches the surface of the research.

Let's peek behind the curtain...

9: Behind the Paper

Every algorithm has a human story. EEDGE began in the Computer Science Labs at LUMS, and was further developed one thanksgiving break in Mountain View, California.

In 2009, Lee et al. published a clever technique for hiding messages in mazes. Their approach used special cells along the solution path — it worked, but but it was not optimal. In early 2010, I was a starry eyed college freshman, doing my CS 100 project. I wanted to show off my coding skills, so for my project I built an interactive maze generator + solver in MATLAB. But that was boring. So I found a way to hide messages in the maze, implementing this algorithm. It was cool! I had a ton of fun.

Fast forward 3 years. I'm in California, interning at SRI, and bored over a holiday break. I've always wanted to learn Haskell, and I decided to give it a shot. I generally like to pick up new languages by implementing projects I've already built (to minimize the complexity, and focus on learning differences). So I go to town. The LLC algorithm was fairly imperative -- and required some translation to work correctly in idiomatic Haskell. But I got it working, and the code was pretty clean when stripped to its core essentials. Haskell has that elegance to it -- I don't want to sound like a Haskell fanboy (the code is hard to read now, 10 years later -- stupid past Hasnain trying to be too smart) -- but just the forcing function of having to write code totally differently made me think about the problem in a different way.

getEmbeddableCells :: EncryptionAlgorithm -> Int -> Int -> [[Cell]] -> [(Cell, [Wall])]
getEmbeddableCells encalgo w h solutions = embeddable
    where
    allCells = concat solutions
    exceptKeys = allCells L.\\ (nub $ fmap head solutions ++ fmap last solutions)
    cells = H.fromList allCells
    predicate = if encalgo == LLC then (== 2) else (> 0)
    list = [ (c, nn) 
                | c <- exceptKeys, let n = neighbours w h c,
                  let nn = [k | k <- n, not (k `H.member` cells)],
                  predicate (length nn)]
    embeddable = sort $ snd $ L.foldl (helper encalgo w h) (H.fromList [], []) list

There really was no reason the code was looking for just 1 neighbor, algorithmically, when formulated this way. I just changed the code in a few more places to have such a check, and ... EEDGE was born. In graph theory terms, I moved from a vertex-based approach to an edge-based one. It sounds simple, but the results speak for themselves: EEDGE could hide 2-3 times more data in the same maze, with the exact improvement depending on the maze generation algorithm used.

I decided to take this and ask my professor if I could get an independent study, because I was lazy and didn't want to take an extra course in my final semester. Senioritis is real. And.. felt like there was enough for a paper here. My gambit worked, kinda. We did get a paper submission out that semester (but it got rejected) and I had to refine the paper and resubmit the following year. Having a good algorithm wasn't enough. I needed to come up with enough material to get a coherent paper. Beyond that, I also needed to come up with a good story, some real world applications, and some results based on that (from surveys). Enter online rogue-like games — games like TOMENET where players explore randomly generated maze-like dungeons. Here was a perfect cover: a legitimate reason to transmit maze data over the internet, happening thousands of times every day. Did I mention I'm a fan of roguelikes? I went to the first few roguelike celebrations in person. They were great.

Aside: Sometimes the best ideas really do come from looking at things differently, or "stupid" shower thoughts. Listen to your heart! Try things out! I'm also personally kinda proud of the way this happened - a publication as an undergrad is nothing to sneeze at -- though I will admit it's not the most impactful publication nor something I like to stand by today (some of the content makes me cringe). It is what it is.

Now that we understand the human story, let's dive deeper into the paper for a bit...

10: Key Insights and Downsides

There were a few key things that were cool in this paper that I'd like to highlight. As well as some things, that, well, I'm not sure how to feel about in hindsight.

1. The simplicity of the idea

Once we frame the problem in terms of graphs, the extension becomes pretty obvious: instead of restricting ourselves to vertices, we can use edges and ... get much higher bang for our buck.

2. Extensibility

A lot of the prior research (at the time! I'm going by memory here, please do not murder me if I get some facts wrong) focused on picking a single algorithm, doing a detailed extension of it, and then some non-trivial proofs to prove things still worked. With the framing here, we are able to extend the steganography to a lot more maze generation algorithms. It became easier to do this when we were able to express this in terms of graphs. There's a much simpler way to prove correctness if your algorithm basically is "We use algorithm X, with just this initial state ..."

Downsides

There's a *lot* to dislike about the paper too, to be fair. In particular a few things I'd like to call out:

• The treatment of steganography is a bit naive. Yes, there's important practical applications. But also... there's harm to just willy nilly enabling it that wasn't called out
• The security argument ... oof. Please slap me if I try to make a a similar case / "proof" of security in the future. With what I know now, I probably wouldn't make such a strong argument.
• The setting could be motivated a bit more clearly, right now it's a bit awkward
• Last, but not least -- the writeup is a bit inscrutable as it's clear the author (me) was trying to sound smart to make a simple idea sound "hard" and justify a publication.

With that said, let's dive into some closing thoughts, both about the paper and this blogpost itself.

11: Closing Thoughts

Every good research paper or blog should end with more questions than it answers. What's that in this context?

Unsolved Challenges

The paper tested EEDGE against multiple detection methods:

• Advanced steganalysis: Could machine learning models trained specifically on EEDGE-generated mazes detect patterns?
• Optimal key selection: Are some key vertex pairs better than others? The paper used random selection, but perhaps strategic choices could increase capacity.
• 3D and beyond: What about hiding data in 3D mazes, or other graph structures entirely? Or fully leaning into roguelike design and generating full on levels>

I'd probably love to explore those questions more over time, as they are definitely interesting. Targeted techniques have often broken steganalysis (and that wasn't attempted in this paper)

Credits & Acknowledgments

Inspiration

This interactive exploration was inspired by the beautiful tradition of explorable explanations and interactive educational content, particularly:

• Bartosz Ciechanowski's stunning visual essays on physics and engineering
• Julia Evans' incredibly helpful zines
• The literate programming movement pioneered by Donald Knuth

Interactive Maze Generation

Special thanks to the maze generation algorithm community:

• Jamis Buck's comprehensive maze algorithm tutorials
• Think Labyrinth by Walter D. Pullen

Thank you to all the researchers and educators who make complex ideas accessible through interactive content. Your work inspires the next generation of learners and creators.