Technical Summary: MAGIQ - A Post-Quantum Multi-Agentic AI Governance System with Provable Security

1. Problem Statement

The rapid deployment of agentic AI systems, capable of autonomous planning and multi-step task execution, introduces critical governance challenges. Existing frameworks often lack secure architectures that ensure agents adhere to owner-defined communication policies, maintain accountability for interactions, and resist future quantum computing threats.

Current solutions face two primary limitations:

1. Lack of Policy Enforcement: While protocols like Agent2Agent (A2A) and Model Context Protocol (MCP) promote interoperability, they lack runtime mediation and policy enforcement mechanisms, leaving agents vulnerable to documented attacks. The only practical system, SAGA, enforces access control based on tokens but lacks a formal security model for policy definition and relies on classical cryptographic primitives (e.g., RSA, ECC) vulnerable to Shor's and Grover's algorithms.
2. Quantum Vulnerability: NIST recommends deprecating standard public-key algorithms (RSA, DH, ECC) by 2030 due to the threat of quantum computers. Simply replacing SAGA's primitives with post-quantum counterparts would incur significant overhead and fail to address the fundamental limitations in policy definition and formal security guarantees.

The core problem is the absence of a governance framework that simultaneously offers rich, semantics-aware policy enforcement for multi-agent interactions and provable post-quantum security.

2. Methodology

The authors propose MAGIQ, a framework designed to define and enforce policies for multi-agentic AI systems using efficient, post-quantum cryptographic (PQC) protocols.

2.1 Core Abstractions

MAGIQ introduces two application-level communication abstractions to capture agent semantics, distinct from low-level transport messages:

• A-session: Models one-to-one communication between two agents (Initiator $A_I$ and Responder $A_R$).
• C-session: Models one-to-many communication between an orchestrator agent and a set of other agents.
• Task-msg: The unit of communication within these sessions, combining intent, data (payload), context, and agent identity.

2.2 Policy Definition

Users define "budgets" governing agent interactions. MAGIQ enforces four specific policy types:

1. Authorized Contact List ($ACL_A$): Defines which agents can initiate contact and which can respond.
2. A-session Participation Budget: Limits the number of sessions an agent can initiate or respond to.
3. Task-msg Budget ($Q_A$): Limits the number of messages an agent can send within a session.
4. Time Budget ($\Delta_A$): Limits the duration an agent remains active for a task.

2.3 Cryptographic Enforcement Mechanisms

MAGIQ utilizes post-quantum primitives to enforce these policies without relying on a trusted third party for every interaction:

• Hash Chains: Used for efficient, secure counting of task-msgs. Agents construct hash chains corresponding to their message budgets. Each message reveals a pre-image of the current committed value, allowing the counterparty to verify the budget has not been exceeded. These chains are bound to specific sessions and agents to prevent reuse.
• Merkle Trees: Used in C-sessions to aggregate the terminal values of multiple hash chains (one for each responder) into a single root. This allows the orchestrator to prove membership in a user-authorized session with a single signature, rather than requiring $m$ separate signatures for $m$ sessions.
• Post-Quantum Signatures: The system employs hash-based signatures (specifically XMSS) for long-term identity and policy authorization, ensuring security against quantum adversaries.
• PQ-TLS: All communication occurs over mutually authenticated Post-Quantum TLS channels.

2.4 System Architecture

The system involves three entities:

• Users ($U$): Define policies and own agents.
• Agents ($A$): Autonomous entities executing tasks.
• Provider ($TA$): An honest-but-curious entity managing a registry of users and agents, facilitating discovery and initial authorization.

The workflow includes:

1. Registration: Users and agents register with the Provider, obtaining certificates and signing keys.
2. Agent Discovery: An initiator queries the Provider to verify if a responder is authorized under their respective contact policies.
3. Session Establishment: Agents perform a handshake involving the exchange of signed authorization tokens and hash chain commitments.
4. Message Transmission: Agents exchange task-msgs, updating hash chain tokens and verifying HMAC tags for integrity.

3. Key Contributions

The paper claims the following contributions:

1. MAGIQ Framework: A system allowing users to define rich communication and access control policy budgets, enforced via post-quantum cryptographic primitives, providing accountability through task-msg attribution.
2. Formal Security Model: A Universal Composability (UC) framework model for policy-defined and policy-enforced secure agent communication. The authors prove that MAGIQ protocols securely realize the defined ideal functionalities ($F_{Reg}$, $F_{A-auth}$, $F_{Ases}$, $F_{Cses}$).
3. Efficiency Evaluation: An empirical evaluation demonstrating that MAGIQ is practical compared to the state-of-the-art classical system SAGA, showing that post-quantum overhead is negligible in realistic network conditions.

4. Experimental Results

The authors evaluated MAGIQ against SAGA using various LLM backends (GPT-4.1, GPT-5.4, Qwen) and task types (Calendar, Email, Writing).

• Computation Overhead:
  • Registration: MAGIQ incurs a one-time cost of 36 seconds for user/agent registration due to XMSS key tree pre-computation. Provider-side registration remains low (5.4 ms).
  • Per-Session: Recurring costs are uniformly under 5 ms.
  • Data Transfer: MAGIQ reduces data transfer overhead significantly (0.03 ms vs. 1.44 ms in SAGA for initiating agents) due to efficient token handling.
• Protocol Overhead:
  • Amortized overhead decreases sharply as the number of requests per session ($Q_{max}$) increases.
  • At practical session sizes ($Q_{max} \ge 15$), the overhead of MAGIQ converges to within 10 ms of SAGA, regardless of geographic latency. The additional PQC cost is subsumed by network latency variations.
• Task Completion:
  • MAGIQ adds a constant overhead of ~0.176s (two-agent) to ~0.336s (multi-agent) to task execution.
  • This represents less than 2% of total execution time across all tested models and tasks, confirming the cost is effectively negligible compared to LLM inference latency.
• Bandwidth:
  • MAGIQ requires higher bandwidth during session establishment (88.65 KB vs. 2.12 KB in SAGA) due to PQC certificates and signatures.
  • However, per-request data transfer is comparable (0.56 KB vs. 0.59 KB).
• Scalability:
  • Provider overhead scales linearly with the number of agents but remains negligible even for 100 agents with short session lifetimes.
  • Orchestrator overhead scales linearly with the number of receiving agents but drops significantly as session lifetimes increase.

5. Significance and Claims

The paper positions MAGIQ as the first step towards post-quantum secure solutions for agentic AI systems. Its significance lies in:

• Provable Security: Unlike previous theoretical proposals, MAGIQ provides formal UC-based proofs for policy enforcement and security guarantees against quantum polynomial-time adversaries.
• Practicality: The evaluation demonstrates that the transition to post-quantum cryptography does not impose a prohibitive performance penalty on agentic workflows, making it a viable solution for immediate deployment.
• Semantic Awareness: By moving policy enforcement from the transport layer to the application layer (task-msgs), MAGIQ ensures that governance is aligned with the actual semantics of agent tasks, preventing attacks that bypass transport-level security.

The authors conclude that MAGIQ successfully balances the need for rigorous, future-proof security with the operational efficiency required for complex multi-agent AI systems.