The Ariadne Protocol

The Challenge: From an Explicit to an Implicit Path

Conventional ciphers like AES are periodic: they represent a single, fixed algorithm that is applied repeatedly. Our initial research into Path-Dependent Encryption (PDE) first solved this by creating a stateful Cryptographic Virtual Machine (CVM) whose operations were dictated by a programmable, explicit Path object.

While powerful, the PDE model introduced a new design trade-off: the Path itself was a dependency that had to be generated and shared. This led our research to its next logical question: could we eliminate the explicit Path object entirely, and instead make the path implicit and emergent?

Our Solution: The Labyrinth and the Thread

The Ariadne Protocol is the definitive answer to that question. It is an architecture we designed to make the cryptographic path a secret that is woven into the data stream itself at zero overhead. It is composed of two core components:

• The Labyrinth is a vast, deterministically generated binary tree of cryptographic operations. This map can be a public parameter, not a secret.
• The Thread is the secret path taken through this map during an operation.

The Thread is not stored or transmitted. It is rediscovered dynamically for each block of data. The CVM determines the next turn (left or right) in the Labyrinth by computing a keyed hash of its own secret state and the public ciphertext chunk. An attacker, lacking the key and state, cannot compute this hash. The path remains secret.

Core Property of the Protocol: Aperiodic by Design

The Labyrinth Construction, the core of the Ariadne Protocol, is designed to be fundamentally aperiodic. After processing each data block, the CVM's internal state is updated using a keyed hash that incorporates the previous state and the new data. This state transition functions as a forward-only cryptographic ratchet.

Because the state is guaranteed (with cryptographic probability) to never repeat, the transformation applied at each step—which depends on the state to derive its keys and path—also never repeats. This ensures that the entire sequence of cryptographic operations is non-repeating. No two blocks, even within the same message, are ever processed in the exact same way. Each step is a unique function of the entire history of the operation up to that point.

Architectural Consequences of the Protocol

The protocol's design commitment to aperiodic, stateful processing yields several profound architectural properties that are not present in conventional static ciphers.

1. Inherent Tamper Evidence: The Snapped Thread

The system's dependency on the exact, unmodified output of the previous step provides inherent tamper evidence. If an attacker reorders, truncates, or modifies any part of the ciphertext stream, the causal chain is broken. The CVM's internal state will irrevocably diverge from the legitimate path, and all subsequent data will be processed into non-meaningful, pseudorandom noise. This "snapped thread" provides immediate and definitive evidence of tampering.

2. Verifiable Computation: The Cryptographic Receipt

The CVM's final state after processing a stream of data is effectively an unforgeable digest of the entire interaction: sFinal_State = HASH(key, initial_state, message_stream, labyrinth_path). No one without the secret key could have produced this final state value.

This allows for powerful auditability. A server processing a sequence of commands can publish the intermediate state hash after each command. A client or auditor can later verify the integrity and order of the entire sequence by re-running the same commands and ensuring their CVM produces the same chain of state hashes.

3. Emergent Access Control: Sub-Labyrinths as Capabilities

The Labyrinth is a vast public tree, and any node within it can be the root of its own valid sub-tree. This allows for a novel form of cryptographic access control inherent to the protocol's design. A key can be partitioned into a public Sub-Tree_Selector and a secret Navigation_Key. The selector tells the software which node to use as the "root" for a given operation (e.g., `root.left.right` for "File Storage"), and the navigation key is used as the CVM's master key. A key issued for one capability literally cannot perform cryptographic operations outside of its designated sub-tree. The access control is not a layer on top of the crypto; it is embedded in the primitive itself.

The Ariadne Suite: The Reference Implementation

The Ariadne Suite is our canonical Rust implementation of the Ariadne Protocol. It provides a composable ecosystem of crates that translate the theoretical design into practical tools. These include low-level primitives for stream ciphers and MACs, and high-level constructions for stateless AEADs and forward-secret transport protocols.

The implementation is organized for clarity, auditability, and performance, with a strong emphasis on correctness and security. For those interested in the specific algorithms and data structures, the source code is the ultimate specification.