⚡ electrical engineering

Stability Buys Time: A Re-Keying Game for Encrypted Multi-Agent Control

This paper models the security of encrypted multi-agent control under advanced persistent threats as a dynamic game where the defender optimally balances control accuracy, cryptographic precision, and re-keying frequency to mitigate inevitable information leakage from approximate homomorphic encryption.

Original authors: Sai Sandeep Damera, John S. Baras

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sai Sandeep Damera, John S. Baras

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 a fleet of autonomous drones or self-driving cars that need to work together perfectly. To keep their locations and commands secret from prying eyes, they send their data to a "cloud" brain that does the math using a special kind of magic lock called Fully Homomorphic Encryption (FHE). This lock lets the cloud crunch the numbers without ever seeing the actual data.

But here's the twist: the math isn't perfect. The "magic lock" (specifically a scheme called CKKS) leaves a tiny bit of static noise in the answer. When the drones finally get their instructions, they have to unlock the message, and that static noise leaks out.

The Two-Part Attack

The paper imagines a sneaky, patient hacker (an "Advanced Persistent Threat") trying to break this system. The attack happens in two distinct phases, like a heist movie:

Phase 1: The Silent Stalker
The hacker just listens. They tap the wire, watching the drones move and collecting the "noisy" answers the cloud sends back. They aren't changing anything yet; they are just gathering clues to figure out the secret key. The defenders (the fleet operators) can't see this because the drones are acting normally. The only defense here is to add more noise to the answers to confuse the hacker. But there's a catch: if you add too much noise, the drones get confused and crash.

Phase 2: The Sneaky Saboteur
Eventually, the hacker decides to act. They start messing with the math to speed up their key recovery. But here's the good news: messing with the math makes the drones wobble. The fleet has a "residual detector" (like a security guard watching for wobbles) that spots these changes immediately.

The Big Discovery: "Stability Buys Time"

The paper's main finding is a clever game of timing. Once the hacker starts messing with things and gets caught, the defender's best move isn't to fix the noise or change the math—it's to change the key entirely.

Think of it like a game of "FlipIt." The hacker is trying to steal the key, and the defender is trying to change the lock before the hacker succeeds.

The Trap: If the defender changes the key too often, it's expensive and disruptive. If they change it too rarely, the hacker steals the key.
The Sweet Spot: The paper finds a "Goldilocks window" where the defender should change the key just often enough to stay ahead, but not so often that it breaks the system.

The Surprising Twist: Topology Matters

Here is the most playful part of the story. How often the defender needs to change the key depends entirely on how the drones are connected to each other.

The "Ring" (Drones in a circle): If the drones are just in a simple ring, they are a bit fragile. The defender has to change the key every 600 cycles to stay safe.
The "Torus" (A donut shape, slightly wobbly): This setup is the most fragile. It's so unstable that the defender must change the key every 200 cycles. The paper calls this "marginally stable," meaning it's barely holding together, so the hacker has less time to work.
The "Complete Graph" (Everyone talks to everyone): This is the strongest setup. Because the network is so robust, the defender can be lazy and only change the key every 1,500 cycles.

The paper proves that the stability of the network itself dictates the security schedule. A wobbly network forces a fast security rhythm; a strong network allows a slow one.

What This Paper Says "No" To

It's important to know what this paper doesn't say.

No, "Bootstrapping" isn't the hero. In encrypted computing, there's a process called "bootstrapping" that refreshes the noise to keep the math running forever. The paper explicitly says this does not help with security. It's like cleaning a dirty window but keeping the same lock; the hacker still has the clues. You must change the key (re-keying) to reset the hacker's progress.
No, you can't just add infinite noise. The paper rules out the idea that you can simply make the noise so loud the hacker gives up. If you make the noise too loud, the drones can't fly. There is a hard limit on how much noise the control system can tolerate.
No, the hacker doesn't need to be a genius. The paper assumes the hacker is smart enough to listen and then mess with the math, but they don't need to break the laws of physics. They just need to be patient and wait for the right moment.

How Sure Are We?

The authors didn't just guess; they built a real simulation. They used a fleet of 9 agents and tested three different network shapes (Ring, Torus, Complete).

They measured exactly how much noise the system could handle before the drones started crashing (finding limits like 0.60 for the ring and 0.30 for the torus).
They simulated the hacker listening and found that the system leaks information at a rate of one observation per cycle.
They calculated that for a specific security level (30 bits), the "safe" precision for the math needs to be around $2^{37}$ (a very large number). If the precision is lower than $2^{32}$ , the system is insecure no matter what. If it's higher than $2^{40}$ , you don't need to change the key at all.

The Bottom Line

The paper suggests that for encrypted fleets, security isn't just about math; it's about the physics of the network. If your network is fragile, you have to change your locks more often. If your network is strong, you can relax. The "price" of keeping the fleet precise and efficient is a carefully timed game of changing keys, and the winner is the one who knows exactly when to strike.

Technical Summary: Stability Buys Time: A Re-Keying Game for Encrypted Multi-Agent Control

Problem Statement
The paper addresses a critical vulnerability in encrypted multi-agent control systems utilizing Fully Homomorphic Encryption (FHE). While FHE allows a cloud server to coordinate a fleet of agents on encrypted data without seeing plaintext, the specific scheme used for real-valued control, CKKS, introduces a security paradox. CKKS is an approximate scheme where decryption returns a value contaminated by encryption noise ( $z + e/\Delta$ ). In a control loop, actuators must decrypt commands to actuate, making these noisy decryptions unavoidable. Recent cryptanalysis has shown that observing these decryptions allows an adversary to reconstruct the secret key.

Existing literature treats this in isolation: FHE security is analyzed statically (noise flooding for a single decryption), encrypted control assumes an "honest-but-curious" cloud, and game-theoretic persistent threat models rarely penetrate the cryptosystem itself. This paper models the interaction between a fleet and an Advanced Persistent Threat (APT) that exploits the unavoidable decryption leakage over time, arguing that static defenses are insufficient for long-horizon missions.

Methodology
The authors model the security of the encrypted control loop as a two-phase game between a cooperative fleet defender and an APT adversary:

Phase I: Passive Reconnaissance (Static Game)
- The adversary eavesdrops on encrypted traffic and observes a subset of agents' decrypted commands.
- The defender commits to a static "noise flooding" level ( $\sigma$ ) added to the decrypted values to obscure the key.
- This phase is modeled as a Stackelberg game where the defender commits to $\sigma$ first. The adversary accumulates observations until the noise is "de-flooded" enough to recover the key.
- The authors establish that leakage accumulates at a rate of one independent observation per control cycle, as the system evolves a single ciphertext in-place under a shared key, and bootstrapping (refreshing noise) does not reset the key or the accumulated leakage.
Phase II: Active Manipulation (Dynamic Timing Game)
- Once the adversary decides to act, it manipulates the encrypted computation to accelerate key recovery or disrupt the fleet.
- This manipulation perturbs the control loop, surfacing in model-based control residuals (detected via a $\chi^2$ test).
- The defender's adaptive move is re-keying: generating a fresh secret key and re-encrypting the fleet state. This resets the adversary's accumulated leakage ledger to zero.
- This phase is modeled as a "FlipIt" style detection-evasion timing game. The defender chooses a re-keying cadence ( $T$ ), while the adversary chooses a posture (passive, stealthy-active, or aggressive-active) to maximize recovery speed while avoiding detection.

Key Contributions

Two-Phase APT Model: The paper formulates the security of an encrypted multi-agent loop as a two-phase game (passive reconnaissance followed by active manipulation), separating the undetectable leakage accumulation from the detectable manipulation phase.
Re-Keying vs. Bootstrapping: The authors distinguish between bootstrapping (which refreshes noise under the same key) and re-keying (which resets the key). They prove that only re-keying resets the adversary's accumulated knowledge, making it the necessary security lever.
Precision-Dependent Regimes: The analysis identifies a three-way tension between FHE precision ( $\Delta$ $Δ$ ), control accuracy (bounded by maximum tolerable flooding $\sigma_{max}$ $σ_{ma x}$ ), and re-key cadence. This leads to three distinct operational regimes:
1. Insecure Floor: Precision is too low; even maximum flooding cannot prevent key recovery within a single cycle.
2. Re-Key Window: Precision is in a bounded range where static flooding is insufficient, but re-keying is feasible. This is the "efficient secure point."
3. Static Sufficiency Ceiling: Precision is high enough that static noise flooding alone secures the key for the mission duration, rendering re-keying unnecessary.
Topology-Dependent Cadence: The optimal re-keying cadence is determined by the control-theoretic fragility of the network topology. More fragile topologies (e.g., marginally stable torus) require more frequent re-keying than well-connected ones (e.g., complete graphs).

Results
The authors instantiate the framework on a nine-agent fleet using the OpenFHE library across three topologies: ring, torus, and complete graph.

Control Tolerance: The maximum tolerable noise flooding ( $\sigma_{max}$ ) is directly linked to the closed-loop spectral radius. The marginally stable torus topology tolerates the least noise ( $\sigma_{max} \approx 0.3$ ), while the complete graph tolerates the most ( $\sigma_{max} \approx 0.75$ ).
Leakage Rate: Experiments confirm that leakage accumulates at one observation per cycle regardless of the closed-loop contraction rate, as each cycle introduces a fresh measurement constraint under the same key.
Regime Mapping: At a precision of $\Delta \approx 2^{37}$ $Δ \approx 2^{37}$ , the system falls into the "re-key window."
- The Torus (most fragile) requires a "Vigilant" cadence (re-key every ~200 cycles).
- The Ring requires a "Moderate" cadence (~600 cycles).
- The Complete Graph tolerates a "Lazy" cadence (~1500 cycles).
Adversary Behavior: The model-based detector effectively foils "aggressive" manipulation (high magnitude attacks), forcing the rational adversary to remain "stealthy." The defender's optimal strategy is to re-key on the "laziest" cadence that still prevents the stealthy adversary from reaching the recovery threshold before detection.

Significance and Claims
The paper claims that security for approximate cryptosystems in feedback loops is fundamentally a dynamic game where the defender's move is the cryptosystem's own refresh mechanism (re-keying).

Stability Buys Time: The paper argues that the control-theoretic stability of the system dictates the cryptographic security cadence. A more stable system (higher $\sigma_{max}$ ) allows for a longer interval between re-keying events.
The "Window" of Efficiency: The authors assert that the efficient secure operating point lies in the bounded precision window where static flooding fails but re-keying is viable. This challenges the assumption that higher precision is always better, suggesting instead that operating in a specific precision range minimizes the cost of re-keying while maintaining security.
Beyond Control: The authors suggest this framework applies to any system that must repeatedly decrypt to act, positioning the re-keying cadence as a dynamic defense against persistent leakage.

The paper remains modest about its scope, noting that the analysis assumes full observation of agents ( $\kappa = M$ ) and a cooperative fleet defender. It identifies partial observation thresholds and strategic/corrupted agents as necessary future extensions.