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

Image generated by AI

TLDR

• What: A game-theoretic framework that dynamically schedules cryptographic re-keying cadences for approximate homomorphic (CKKS) multi-agent control loops based on the control-theoretic stability of the network topology.
• Who's at risk: Cloud-coordinated autonomous vehicle fleets, collaborative robotic systems, and industrial cyber-physical networks utilizing CKKS Fully Homomorphic Encryption (FHE) to protect control commands.
• Key number: A minimum precision floor of $\Delta_{min} \approx 2^{32}$ is mathematically required to mount any viable defense; below this floor, an adversary can reconstruct the master secret key within a single control cycle.

As collaborative robotic fleets, autonomous delivery networks, and distributed industrial systems increasingly offload coordination to cloud servers, securing these channels against untrusted infrastructure has led to the adoption of Fully Homomorphic Encryption (FHE). Real-world control pipelines rely on the CKKS approximate scheme to process continuous, real-valued state vectors. However, because physical actuators must decrypt control commands at every cycle to execute movements, they inevitably leak encryption noise—a vulnerability that malicious cloud servers or advanced persistent threats (APTs) can exploit to systematically reconstruct the system's secret master key.

Threat Model

Background and Problem Setup

The security of approximate FHE schemes like CKKS is traditionally analyzed statically—determining how much noise to inject into a single released decryption to maintain security. This paper bridges the gap between static cryptography and dynamic control theory. Unlike classical encrypted control literature that assumes an "honest-but-curious" cloud, this work models an active, adaptive adversary.

Crucially, the authors distinguish between bootstrapping and re-keying: bootstrapping merely refreshes ciphertext noise under the same key, leaving the attacker's accumulated leakage history intact. Only re-keying generates a fresh master key and resets the adversary's leakage ledger to zero.

The table below illustrates how this framework positions itself against related work cited in the paper:

Methodology

The framework decomposes the interaction into a two-phase game linked by a leakage ledger:

Phase I: Passive Reconnaissance

The adversary passively taps the encrypted traffic and observes the physical states of a subset of agents ($\kappa$). Each released decryption $z$ under the secret key $s$ exposes a noisy linear constraint:

where $e$ is the ciphertext error, and $\Delta$ is the scaling factor. The defender commits to a static noise-flooding level $\sigma \le \sigma_{max}$. The leakage accumulates at one observation per cycle.

Phase II: Active Manipulation

To accelerate key recovery or disrupt the fleet, the adversary actively perturbs the ciphertext computations. This active manipulation shifts the game to a chosen-ciphertext setting, accelerating key leakage by a factor of $a_s > 1$. However, this manipulation perturbs the physical control loop, making the adversary detectable via a model-based $\chi^2$ anomaly detector running on the observer innovations.

The Precision Regimes

The key-recovery horizon $H_{rk}$ (the number of cycles before the key is compromised) is given by:

This induces three distinct precision regimes based on the FHE scale factor $\Delta$:

1. Insecure Regime ($\Delta \le 2^{32}$): $H_{rk} < 1$. No defense is possible; the key is recovered within a single cycle.
2. Re-Keying Window ($2^{32} \le \Delta \le 2^{38}$): Cadence is an interior Stackelberg game. Re-keying is required, and its cadence is bounded by control stability.
3. Vacuous Regime ($\Delta \ge 2^{40}$): Static flooding alone secures the key for the entire mission duration; re-keying is unnecessary.

The Re-Keying Game & Stackelberg Equilibrium

Inside the active window, the game is solved as a Stackelberg game where the defender leads by committing to a blind re-keying cadence $T$. The rational adversary chooses whether to remain stealthy ($a_s$) or act aggressively. Since aggressive attacks are caught by the defender's detector, the rational adversary stays stealthy. The defender's optimal cadence $T^*$ is the laziest interval that still prevents key compromise:

# Conceptual implementation of the Re-Keying Cadence Solver
function compute_optimal_cadence(topology, delta, s_bits, e_noise, a_s)
    # 1. Retrieve the maximum control-tolerable flooding (σ_max) for the topology
    sigma_max = get_topology_flooding_limit(topology)
    
    # 2. Calculate the key-recovery horizon H_rk in cycles
    H_rk = (sigma_max * delta)^2 / (12 * (2^s_bits) * e_noise^2)
    
    # 3. Classify into security regimes
    if H_rk < 1
        return :Insecure, "No feasible defense"
    elseif H_rk > MISSION_LENGTH
        return :Vacuous, "Static flooding suffices"
    else
        # 4. Compute Stackelberg optimal cadence under stealthy acceleration a_s
        T_star = floor(Int, H_rk / a_s)
        return :Window, T_star
    end
end

Key Results

The authors evaluated their framework on a 9-agent fleet ($M = 9, n = 4$) simulated on the OpenFHE.jl backend across three topologies. The table below compiles the control-tolerable flooding limits ($\sigma_{max}$) measured in the paper (Table 1) and the corresponding optimal re-keying cadences ($T^*$) at a precision of $\Delta = 2^{37}$:

Fig. 2 Game Matrix Summary

As detailed in Figure 2, the Stackelberg equilibrium (gold) dynamically shifts with the network topology's physical stability. The marginally-stable Torus, being highly fragile to command noise, can only tolerate $\sigma_{max} = 0.30$. This low threshold limits the amount of static security noise the defender can inject, forcing the defender to adopt an aggressive Vigilant re-keying schedule ($T = 200$) to preempt key extraction. In contrast, the highly connected Complete Graph tolerates $\sigma_{max} = 0.75$, allowing a Lazy cadence ($T = 1500$).

Critical Evaluation & Skepticism

While the theoretical integration of control theory and cryptography is elegant, practitioners should approach the empirical evaluation with caution:

• Assumed Threat Parameters: The active leakage acceleration factor $a_s$ is treated as a declared parameter rather than being dynamically measured from concrete key-recovery attacks. If an adversary develops a more efficient chosen-ciphertext attack, $a_s$ will spike, rendering the pre-calculated $T^*$ cadences insecure.
• Simplistic Detector: The active manipulation phase relies on a basic $\chi^2$ anomaly detector. Highly sophisticated "stealthy" attacks (e.g., replay or zero-dynamics attacks) could inject malicious control inputs while keeping the innovations below the detector's knee, effectively decoupling detectability from active manipulation.

Limitations and Open Questions

1. Full Observation Assumption ($\kappa = M$): The primary mathematical analysis assumes the attacker physically observes all agents. While Section 8 touches on a partial-observation infection threshold ($\kappa^*/M$), a formal game-theoretic derivation for arbitrary $\kappa < M$ remains an open research question.
2. Monolithic Key Single-Point-of-Failure: The entire fleet operates under a single, shared cryptographic key $s$. A physical compromise of a single agent's actuator instantly exposes the decryption oracle for the entire system. Implementing distributed or threshold homomorphic setups is mentioned but excluded due to massive latency overheads.
3. Static Graph Topologies: The game assumes the graph Laplacian $L$ is time-invariant. In real-world robotic deployments, topologies are highly dynamic (e.g., ad-hoc link formations), meaning $\sigma_{max}$ and the resulting $T^*$ would need to be computed dynamically in real-time.

What Practitioners Should Do

1. Perform Topology-Aware Noise Profiling

Before deploying any homomorphic controller, do not rely on generic precision settings. Map the network topology's spectral radius ($\rho_{cl}$) and empirically determine the maximum command-domain noise deviation ($\sigma_{max}$) your control loop can tolerate before exceeding performance bounds (e.g., $25%$ RMS position error).

2. Avoid Over-Provisioning the Scale Factor ($\Delta$)

Evaluate your system's operational needs against the three precision regimes. Avoid setting excessively high scaling factors (e.g., $\Delta = 2^{59}$) which are computationally expensive. Instead, design within the optimal re-keying window ($\Delta \approx 2^{32}$ to $2^{38}$) and implement active re-keying to manage key exposure.

3. Implement Cryptographic Re-Keying in OpenFHE

Do not mistake bootstrapping for a security refresh. Set up an automated re-keying pipeline in your control stack. When the control cycle counter reaches the computed Stackelberg cadence $T^*$, trigger a key regeneration and state re-encryption:

# Explicitly regenerate key and re-encrypt state (Do not rely on bootstrapping)
if current_cycle % T_star == 0
    new_private_key, new_public_key = KeyGen(crypto_context)
    encrypted_state = re_encrypt(encrypted_state, old_private_key, new_public_key)
    old_private_key = new_private_key
end

4. Deploy Innovation-Based Anomaly Detectors

Integrate model-based anomaly detection (such as a $\chi^2$ test on Kalman filter innovations) directly on the physical actuators. Program the actuator to trigger an immediate, unscheduled out-of-band re-keying sequence the moment an anomaly is flagged.

The Takeaway

FHE-encrypted control loops are not static, self-contained cryptographic shields. Their real-world security is fundamentally bound to the physical plant's stability and network topology. Cryptographic re-keying is the operational tax practitioners must pay to run efficient homomorphic controllers, and a system's control-theoretic robustness is the asset that buys the time needed to defer that tax.

Den's Take

I love seeing research that bridges the gap between pure cryptography and dynamic physical systems. Too many practitioners treat CKKS Fully Homomorphic Encryption (FHE) as a magic bullet for cloud-coordinated robotics, completely ignoring that physical actuators decrypting control commands at every cycle inevitably leak noise. This paper's critical distinction between bootstrapping—which merely refreshes ciphertext noise—and actual re-keying to reset the adversary's leakage ledger is spot on.

The math here delivers a stark reality check: a minimum precision floor of $\Delta_{min} \approx 2^{32}$ is strictly required just to mount a defense. Fall below this, and an active adversary observing a 9-agent fleet (across Ring, Torus, or Complete topologies) can reconstruct the master secret key in a single control cycle. This highlights how security properties must be evaluated holistically across the network's physical control topology, as decentralized multi-agent coordination introduces unique compositional vulnerabilities that local nodes completely miss.

My main reservation is the real-world computational overhead of their game-theoretic scheduling. While using control-loop stability to buy time and optimize re-keying cadences is mathematically elegant, executing frequent FHE re-keying on resource-constrained actuators remains a massive operational bottleneck that this theoretical model glosses over.