💻 computer science

Sharing The Secret: Distributed Privacy-Preserving Monitoring

This paper proposes a distributed, privacy-preserving monitoring protocol that leverages secret-sharing schemes across multiple parties to enable efficient, continuous runtime verification with significantly reduced computational overhead compared to traditional monolithic cryptographic approaches.

Original authors: Mahyar Karimi, K. S. Thejaswini, Roderick Bloem, Thomas A. Henzinger

Published 2026-03-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mahyar Karimi, K. S. Thejaswini, Roderick Bloem, Thomas A. Henzinger

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 have a secret recipe for the world's best cake (this is your Monitor). You want to hire a baker (the System) to make the cake for you, but you have two big problems:

You don't want the baker to see your recipe. If they see it, they might steal it or sell it.
The baker doesn't want you to see their secret ingredients. Maybe they use a special, expensive flour that they don't want you to know about.

In the past, trying to check if the baker followed your recipe without seeing the ingredients was like trying to solve a puzzle while wearing thick, heavy welding goggles and gloves. It was so slow and clumsy that you could never check the cake while it was actually baking. This is what the paper calls "traditional privacy-preserving monitoring." It relied on heavy, slow math (cryptography) that made real-time checking impossible.

The New Idea: The "Secret Team"

This paper proposes a clever new way to do it. Instead of hiring one giant, all-powerful auditor to check the cake, you hire a team of three independent people (let's call them Alice, Bob, and Charlie) to act as the Monitor.

Here is the magic rule: At least one of them is honest. Even if Alice and Bob are in cahoots, as long as Charlie is honest, the secret stays safe.

How it works (The "Secret Sharing" Analogy)

Instead of giving the whole recipe or the whole cake to one person, you slice the information into pieces and give a piece to each person.

The Recipe (Specification): You don't give Alice, Bob, or Charlie the whole recipe. You split the recipe into three parts. No single person knows the full recipe. Only when they put their pieces together do they know if the cake is good.
The Ingredients (System Data): The baker doesn't give the whole bag of flour to the team. They slice the flour into three bags. Alice gets a bag, Bob gets a bag, Charlie gets a bag. Individually, a bag of flour looks like nothing special.

The Magic Trick:
The team can now do math on their separate bags of flour without ever opening them to see what's inside.

If they need to add the weight of the flour, they can just add the numbers on their bags.
If they need to compare the flour to a limit (e.g., "Is this less than 500 grams?"), they can do a special dance (a protocol) to find the answer without ever revealing the actual weight.

Because they are working with "shards" of data rather than the whole thing, the math is incredibly fast. It's like doing a math problem on a napkin instead of building a supercomputer.

Why is this a big deal?

1. Speed:
The old way (using heavy cryptography) was like trying to drive a car through a wall of concrete. It took minutes to check a simple rule. The new way is like driving a sports car on an open highway. The paper shows their method is 100 to 1,000 times faster. This means you can check the cake while it's baking, in real-time.

2. Continuous Monitoring:
Old methods were like taking a photo of the cake once and checking it. If the cake changed later, you had to start over. This new method allows the team to keep checking the cake every second, remembering the state of the cake (is it rising? is it burning?) without ever forgetting or revealing the secret details.

3. Real-World Examples:
The paper tested this on four scenarios:

Office Security: Checking if too many people of one type are in a building compared to another, without revealing who entered.
Locks: Making sure a computer program doesn't get stuck trying to lock the same door twice.
Blood Sugar: Checking if a patient's sugar levels stay safe over time without the hospital seeing the specific numbers.
Presidential Car: Tracking a car's location to ensure it stays within a safe zone, without revealing the exact coordinates to the tracker.

The Catch (The Trade-off)

There is one condition for this to work: You need a trustworthy team.
The system assumes that in the group of monitors, at least one person is honest. If everyone in the monitoring team is corrupt and they all share their notes, the secret is broken. But in the real world, it's usually very hard to corrupt everyone in a distributed team, making this a very safe bet.

Summary

Think of this paper as inventing a fast, secure, and continuous way to check a secret recipe against secret ingredients.

Instead of using a slow, heavy shield (old cryptography), they use a team of people holding puzzle pieces (secret sharing). As long as one person in the team is honest, the secrets remain safe, and the checking happens so fast that it can be done instantly, every single second. This makes it possible to protect privacy in real-time systems like banks, hospitals, and self-driving cars for the first time.

1. Problem Definition

The paper addresses the challenge of Privacy-Preserving Runtime Verification (PPRV). In traditional settings, a system (e.g., a bank, medical device, or proprietary software) must be monitored against a formal specification (e.g., safety rules, regulatory compliance) by a third-party verifier.

The Conflict: Both the System and the Monitor require privacy. The System holds sensitive data (trade secrets, user data) that must not be revealed to the Monitor. Conversely, the Monitor holds a proprietary specification (e.g., a specific compliance algorithm) that must not be revealed to the System.
The Limitation of Existing Solutions: Current approaches rely on heavy cryptographic primitives like Fully Homomorphic Encryption (FHE) or Garbled Circuits (GC). While these offer strong security, they are computationally expensive, often requiring minutes to verify simple specifications. This makes them impractical for real-time, continuous monitoring where the system state evolves indefinitely.
The Gap: Existing secret-sharing methods are typically limited to "one-shot" (stateless) computations. They cannot maintain an internal state across a stream of events, which is essential for runtime verification of temporal logic (e.g., "the temperature must never exceed X for 10 consecutive seconds").

2. Methodology

The authors propose a Distributed Monitoring Architecture that replaces heavy cryptography with Secret Sharing (SS) under the assumption of an honest majority among distributed monitor parties.

Core Architecture

Entities:
- System (S): A monolithic entity generating a stream of observable outputs ( $\sigma_t$ ).
- Monitor (M): A distributed entity consisting of $k$ computers ( $M_1, \dots, M_k$ ). The security model assumes at least one computer is honest (semi-honest adversary model).
Secret Sharing Mechanism:
- The System splits its output $\sigma_t$ into shares and distributes them to the Monitor parties.
- The Monitor parties jointly hold the specification state ( $\mu_t$ ) in a shared form. No single party knows the full state.
- Stateful Execution: Unlike standard MPC which is often stateless, this protocol maintains a persistent, secret-shared internal state ( $\mu_t$ ) that evolves with every time step $t$ .
Mixed-Protocol Computation:
- The protocol utilizes Share Conversion to switch between different sharing representations efficiently:
  - Arithmetic Shares: Efficient for addition and multiplication (e.g., summing values).
  - Boolean Shares: Efficient for logical comparisons (e.g., $x < y$ ).
- The system uses a typed instruction set (inspired by MP-SPDZ) to compile specifications into sequences of operations, minimizing the overhead of converting between share types.
Execution Flow:
1. Sharing: System generates shares of $\sigma_t$ and sends them to Monitor parties.
2. Evaluation: Monitor parties perform Secure Multi-Party Computation (MPC) on the shared inputs and the shared previous state $\mu_t$ to compute the next state $\mu_{t+1}$ and a violation flag $\phi$ .
3. Reconstruction: Only the violation flag (a single bit) is reconstructed and revealed. The internal state $\mu_{t+1}$ remains secret-shared for the next round.

3. Key Contributions

Stateful Secret-Sharing Protocol: The primary contribution is a protocol tailored for continuous monitoring. It supports repeated evaluations over an evolving internal state, a capability missing in standard one-shot secret-sharing schemes.
Architectural Trade-off for Scalability: The authors trade the "computational hardness" assumptions of FHE/GC for an "architectural" assumption (honest majority). This allows the use of lightweight secret sharing, reducing overhead by orders of magnitude.
Formal Framework for Share Conversion: They extend the theoretical framework of Cramer, Damgård, and Maurer to treat share conversion as a first-class primitive. This allows for a unified analysis of protocols that switch between arithmetic and Boolean representations.
Information-Theoretic Privacy: Under the honest-majority assumption and using schemes like Shamir's Secret Sharing, the protocol offers information-theoretic security (secure even against computationally unbounded adversaries), unlike FHE which relies on computational hardness.

4. Experimental Results

The authors implemented the protocol using the MP-SPDZ framework with Shamir secret sharing (3 parties, 1 corruption threshold). They evaluated four diverse scenarios:

Scenario	Description	Performance (Per Iteration)	Comparison
Access Control (ACS)	Monitoring door entries/exits for employee types.	0.07s – 0.18s	100–250× faster than Garbled Circuits (GC).
Distributed Locks	Checking lock/unlock state transitions (Boolean heavy).	0.16s – 1.27s	14–112× faster than GC.
Presidential Geofence	Tracking a car in high-dimensional space (Non-linear arithmetic).	0.06s – 0.18s	Previous methods (FHE/GC) could not handle this efficiently.
Blood Sugar	Sliding window threshold check.	0.08s	Matches the best existing FHE results but with better scalability.

Scalability: For the Access Control and Geofence scenarios, computation time remained nearly constant regardless of system size (e.g., number of doors or dimensions), with communication scaling linearly.
Comparison: Previous works using Garbled Circuits (Henzinger et al.) required 18+ seconds per iteration for similar tasks. FHE-based approaches (Banno et al.) were often infeasible for complex stateful specifications.

5. Significance

Real-Time Viability: This work bridges the gap between theoretical privacy and practical application. By reducing monitoring latency from minutes to milliseconds, it enables privacy-preserving verification for real-time systems (e.g., autonomous vehicles, high-frequency trading, medical devices).
Stateful Verification: It solves the critical limitation of existing MPC approaches that cannot handle infinite streams or stateful temporal logic, opening the door to verifying complex, evolving system behaviors without compromising confidentiality.
Security Model: It demonstrates that by relaxing the trust model slightly (requiring an honest majority of monitors rather than a single trusted party), one can achieve perfect (information-theoretic) privacy without the massive computational cost of homomorphic encryption.

Conclusion

The paper presents a paradigm shift in privacy-preserving runtime verification. By distributing the monitor and leveraging secret sharing, the authors achieve a 2–3 orders of magnitude speedup over state-of-the-art cryptographic methods. This makes it possible to verify complex, stateful specifications on sensitive data in real-time, provided the monitoring infrastructure can be distributed among multiple parties with at least one honest participant.