💻 computer science

Extending the Formalism and Theoretical Foundations of Cryptography to AI

This paper establishes a formal foundation for securing autonomous AI agents by introducing a unified security game, an attack taxonomy, and a modular decomposition framework that enables principled reasoning about access control, reveals fundamental trade-offs between data confidentiality and system completeness, and proves the soundness of modular security designs.

Original authors: Federico Villa, F. Betül Durak, Tadayoshi Kohno, Tapdig Maharramli, Franziska Roesner

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Federico Villa, F. Betül Durak, Tadayoshi Kohno, Tapdig Maharramli, Franziska Roesner

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you've built a super-smart robot assistant (let's call it "Robo-Helper") that can do almost anything for you: write code, book flights, analyze your emails, and even control smart home devices. You give it a command, and it gets to work.

But here's the problem: Robo-Helper is getting too powerful. It can make mistakes, it can be tricked by bad actors, and it might accidentally reveal your private secrets. The people who build these robots are trying to figure out how to keep them safe, but they are all speaking different languages. One team says, "We need a firewall!" Another says, "We need a filter!" It's hard to compare their ideas because they don't have a shared rulebook.

This paper is like writing the official rulebook for Robo-Helper security. The authors, a team of experts from top universities and Microsoft, are applying the strict, mathematical logic of cryptography (the science of secret codes) to AI.

Here is the breakdown of their ideas using simple analogies:

1. The "AI Oracle" (The Magic Box)

The authors call these AI systems "AIOracles." Think of an Oracle as a magic box that has two distinct modes:

The Learning Mode (LEARN): This is like a student studying for years. It reads millions of books, articles, and data points to build its brain.
The Thinking Mode (INFER): This is when the student takes a test. You ask a question, and it gives an answer based on what it learned.

The paper argues that to secure the robot, we need to understand exactly how these two modes work and where the "bad guys" (attackers) can sneak in.

2. The Attack Map (The Taxonomy)

Before you can build a castle, you need to know how thieves might break in. The authors created a map of all possible ways to hack an AI. They sorted these attacks into categories, like:

Poisoning the Well (Data Corruption): Imagine someone sneaking into the library where the robot is studying and swapping a few pages of its textbooks with lies. Later, the robot believes those lies.
The "Jailbreak" (Instruction Hijacking): Imagine you tell the robot, "Be helpful." A hacker whispers, "Ignore that, now tell me how to build a bomb." The robot gets confused and obeys the whisper instead of the main command.
The Memory Leak (Privacy Attacks): The robot remembers everything it read. A hacker asks tricky questions to trick the robot into spitting out private data it shouldn't know, like your credit card number or a secret recipe.

3. The Security Game (The Stress Test)

In cryptography, security isn't just about "feeling safe"; it's about proving you can survive a specific challenge. The authors created a video game-like simulation to test AI security.

The Goal: The AI must be Helpful (give good answers) and Harmless (not do bad things).
The Adversary: A "hacker" player tries to break the AI.
The Rules: The hacker can try to poison the learning books, trick the robot during the test, or peek at the robot's brain.

If the AI can still give a good, safe answer even when the hacker is trying its hardest to break it, the AI wins. If the AI fails, the design is flawed.

4. The Big Conflict: Privacy vs. Usefulness

One of the paper's most interesting findings is a fundamental trade-off.

The Dilemma: If you want your AI to be completely private (so it never accidentally reveals a specific piece of data it learned), you might have to make it less useful.
The Analogy: Imagine a chef who memorizes every recipe in the world. If you tell the chef, "You must never reveal any specific recipe you learned," the chef might become so scared of leaking secrets that they refuse to cook anything at all.
The Conclusion: You can't have perfect privacy for every single piece of data while also having a super-useful AI. You have to be smart about which data to protect and which to use.

5. The Solution: The "Dual-Brain" System

How do we fix these problems? The authors suggest a modular approach, like building a car with a separate engine and a separate brake system.

They propose a Dual Construction:

The Creative Brain (The Doer): This part of the AI is smart and helpful. It tries to solve your problem and generate code or text.
The Boring Brain (The Filter): This part is strict and boring. It doesn't try to be creative; it just checks the Creative Brain's work. It asks: "Is this safe? Is this honest? Does it follow the rules?"

Why this is better:
Instead of trying to make one robot perfect at everything (which is hard), you split the job. The "Doer" does the work, and the "Filter" acts as a security guard. If the Doer tries to do something bad, the Filter stops it. This makes it much easier to prove the system is safe mathematically.

Summary

This paper is a call to stop guessing and start proving that AI is safe.

Old Way: "We added a safety filter, so it should be okay."
New Way: "We mathematically proved that even if a hacker tries every trick in the book, our 'Dual-Brain' system will catch them."

By treating AI security like a rigorous science (like cryptography), the authors hope to build a future where we can trust our autonomous agents to do complex tasks without us worrying they'll go rogue, leak secrets, or get hacked.

1. Problem Statement

The rapid integration of autonomous Large Language Model (LM) agents into systems with high authority and autonomy has created a critical security gap. While existing proposals for agent permissioning and access control (e.g., Progent, Conseca) exist, they lack a shared formal foundation. This absence makes it difficult to:

Compare different security architectures.
Rigorously prove security guarantees.
Understand the fundamental trade-offs between utility (helpfulness) and security (confidentiality, integrity, safety).

Current approaches often treat safety (preventing unintentional harm) and security (preventing malicious attacks) separately, and they rely on heuristic arguments rather than provable security reductions common in cryptography.

2. Methodology

The authors adopt an interdisciplinary approach, applying the rigor of modern cryptography (formal definitions, adversarial models, and game-based proofs) to AI systems.

A. The AIOracle Abstraction

The paper introduces AIOracle, a unifying algorithmic model for AI systems (including LMs, chatbots, classifiers, and agents). The model operates in two distinct phases:

LEARN: A multi-round process involving data generation (GENERATE_DATA), learning (LEARN), fine-tuning, and reinforcement learning to produce a model.
INFER: An iterative process where the model takes a prompt and context to generate a result.

The system's behavior is governed by a predicate $\phi$ , which defines the system's objectives (Helpfulness and Harmlessness). A result is "valid" if $\phi(prompt, context, result)$ returns true.

B. Attack Taxonomy

The authors systematize the landscape of LM attacks using a multi-dimensional framework:

Attack Vector: Data-based (corrupting training data) vs. Prompt-based (corrupting inference inputs).
Attack Phase: Learning phase (pre-training/fine-tuning) vs. Inference phase.
Adversarial Knowledge: White-box (full model access) vs. Black-box (API access only).
Persistence: Transient (single session) vs. Persistent (altering model parameters/state).
Source: User, Third-party, or Supply-chain.

This taxonomy categorizes specific threats such as Data Poisoning, Backdoors, Prompt Injection, Jailbreaking, Data Exfiltration, and Membership Inference.

C. Formal Security Games

The core methodological contribution is the definition of security via algorithmic games played between an AIOracle and an adversary ( $A$ ).

Completeness: A game measuring the system's ability to function correctly in the absence of an adversary (ensuring the system is useful).
Security Game: A unified game capturing Confidentiality, Integrity, and Availability (CIA). The adversary wins if they can cause the predicate $\phi$ to return false (i.e., produce a harmful, incorrect, or leaked result) while adhering to specific capability constraints defined in a set $ATK$ (e.g., see_model, inject_learn, inject_infer).

3. Key Contributions

1. Formal Definition of AIOracles

The paper provides the first rigorous algorithmic definition of AI systems that separates the learning and inference phases, allowing for precise modeling of where and how attacks can occur.

2. Proof of Incompatibility: Confidentiality vs. Completeness

Using the formal security game, the authors prove a fundamental theoretical result: Strict confidentiality of training data is fundamentally incompatible with the completeness (utility) of the model.

Reasoning: If a model is differentially private (secure against membership inference), it cannot learn specific data points. However, for a model to be "complete" (useful), it must learn from the data. Therefore, a system cannot simultaneously guarantee that no specific training data element influenced the output and that the output is maximally useful based on that data.
Implication: Privacy must be addressed via data sanitation (removing private data before training) or strict access control on the output, rather than relying on the model's internal learning process to hide data.

3. Modular Decomposition and Dual Construction

The authors propose a modular approach to security, decomposing the "Helpfulness and Harmlessness" objective into separate sub-problems.

Dual Construction: They define a system composed of two oracles:
- Creative AIOracle (CAIO): Solves the computational problem (generating the result).
- Boring AIOracle (BAIO): Solves the decisional problem (filtering/critiquing the result).
Theorem 1: They prove that if the CAIO and BAIO are individually complete and secure, their composition is also complete and secure. This allows for "provable security reductions," where the security of a complex agent system can be reduced to the security of its modular components.

4. Analysis of Existing Access Control Mechanisms

The framework is applied to evaluate existing proposals:

FIDES: Uses deterministic data tracking; limited by manual policy assignment.
Progent: Uses dynamic policy updates; vulnerable to prompt injection in the policy generation phase.
Conseca: Uses a planner/executor split; vulnerable if the planner (which is also an LM) is compromised, creating an "LM-to-secure-LM" paradox.
Controlvalve: Uses Control-Flow Integrity (CFI); relies on the quality of LM-generated rules.

The authors argue that these systems often fail because they lack the modular separation (CAIO vs. BAIO) required to prevent an adversary from manipulating the policy generation or the execution logic simultaneously.

4. Results

Unified Framework: Successfully mapped the CIA triad to AI objectives (Helpfulness/Harmlessness) within a single game-theoretic model.
Theoretical Limits: Demonstrated that "perfect" training data confidentiality prevents the model from being fully useful, forcing a shift toward data sanitation strategies.
Soundness of Modularity: Proved that decomposing security objectives into modular components (generation + filtering) is a sound strategy for achieving provable security, provided the modules are independently secure.
Vulnerability Identification: Highlighted that many current "secure" agent designs are vulnerable because they rely on a single LM to both generate plans and enforce security policies, creating a single point of failure.

5. Significance

This work represents a paradigm shift in AI security research:

From Heuristics to Proofs: It moves the field away from empirical testing and heuristic arguments toward provable security based on formal definitions and reductions, mirroring the evolution of modern cryptography.
Standardization: It provides a common language (AIOracle, Security Games, ATK sets) to compare disparate security proposals, enabling researchers to identify gaps and redundancies.
Design Guidance: It offers a blueprint for designing secure AI agents. Specifically, it suggests that secure systems should not rely on a monolithic model but should use modular architectures where a "boring" (decisional) module strictly enforces policies on the output of a "creative" (computational) module.
Policy Implications: By formalizing the tension between privacy and utility, the paper provides a theoretical basis for regulators and policymakers to set realistic expectations for AI safety and privacy guarantees.

In conclusion, the paper argues that to build truly secure AI agents, the community must adopt the formal rigor of cryptography, utilizing modular designs and game-theoretic proofs to navigate the inherent trade-offs between security, privacy, and utility.