💻 computer science

PRoVeFL: Private Robust and Verifiable Aggregation in Federated Learning

PRoVeFL is a novel, modular federated learning framework that achieves privacy-preserving, Byzantine-robust, and verifiable aggregation by leveraging multi-key fully homomorphic encryption and a hybrid computation model to significantly reduce overhead while supporting diverse robust aggregation algorithms.

Original authors: Harsh Kasyap, Anil Kumar Pradhan, Ugur Ilker Atmaca, Graham Cormode, Carsten Maple

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Harsh Kasyap, Anil Kumar Pradhan, Ugur Ilker Atmaca, Graham Cormode, Carsten Maple

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

The Big Picture: A Group Project with a Suspicious Teacher

Imagine a group of students (the clients) trying to solve a difficult math problem together. They want to learn the answer without showing their private notes to anyone else.

In a standard setup, they all send their answers to a single teacher (the server) who combines them to find the final solution. But this has two big problems:

Privacy Leak: If the teacher is nosy (or hacked), they can look at the students' answers and guess what private notes they were studying.
Cheating: A bad student might send a fake answer to ruin the whole class's grade. Or, a dishonest teacher might ignore the good students and only count the bad ones.

PRoVeFL is a new, smarter way to run this group project. It uses a team of teachers instead of just one, and it uses a special "magic lockbox" system to ensure privacy, stop cheating, and prove that the final grade is correct.

The Three Superpowers of PRoVeFL

The paper claims PRoVeFL solves three specific problems at once:

1. Privacy (The "Magic Lockbox")

The Problem: If you send your homework to a teacher, they can read it.
The PRoVeFL Solution:
Imagine every student puts their homework inside a locked box. But here's the trick: no single teacher has the key to open it.

The students use a special "Multi-Key" lock. To open the box, all the teachers in the room must work together.
Even if one teacher is a spy, they can't open the box because they don't have the other keys.
The teachers can do math on the locked boxes (like adding them up) without ever seeing what's inside. This is called Homomorphic Encryption.

2. Robustness (The "Anti-Cheating Filter")

The Problem: What if a student tries to submit a fake answer to mess up the class average?
The PRoVeFL Solution:
The teachers need to filter out the bad answers, but they can't do this while the boxes are locked because they can't see the numbers to compare them.

The Clever Trick: The teachers use a "random mask." They multiply the locked answers by a secret random number.
They unlock the boxes just enough to see the masked numbers. Because the random number is the same for everyone, the order of the answers stays the same (the biggest is still the biggest, the smallest is still the smallest), but the actual values are hidden.
Now, the teachers can quickly sort the answers, throw away the weird outliers (the cheaters), and keep the good ones—all while the real data remains private.
Once the bad answers are tossed, they re-lock the good ones and finish the math.

3. Verifiability (The "Receipt Check")

The Problem: How do the students know the teachers didn't just make up the final grade or ignore the good students?
The PRoVeFL Solution:
The system creates a digital "receipt" for every step.

Before the teachers do any math, the students create a cryptographic "fingerprint" (a commitment) of their homework.
After the teachers do the math, they produce a proof that says, "We added these specific fingerprints together correctly."
The students (or other teachers) can check this proof. If the math doesn't match the fingerprints, the system stops immediately. This proves the teachers didn't cheat.

How It Works: The "Hybrid" Kitchen Analogy

The paper mentions a "hybrid computation model." Think of this like a kitchen with two chefs (the servers) and a very strict health inspector (privacy).

The Locked Ingredients: The students send their ingredients (data) in sealed, unopenable jars.
The Mixing: The chefs can shake the jars and mix them together without opening them. This is the encrypted part. It's slow and heavy, but safe.
The "Safe" Zone: Doing complex sorting (like finding the top 3 best ingredients) inside the sealed jars is too slow. So, the chefs use the "random mask" trick. They open the jars just enough to see the relative size of the ingredients, sort them, and throw out the bad ones.
The Check: Before they throw anything away, they show a receipt proving they sorted the right jars.
The Result: They re-seal the good ingredients and finish the recipe.

Why Is This Better Than Before?

The paper compares PRoVeFL to older methods:

Old methods were either too slow (taking forever to do math on locked boxes) or not secure enough (requiring too much trust in the teacher).
PRoVeFL is 10 to 100 times faster than previous secure methods. It achieves this by splitting the work between multiple servers and only doing the heavy "locked box" math when absolutely necessary.

Summary of Claims

The paper claims that PRoVeFL is the first system that successfully does all three of these things at the same time:

Privacy: Keeps student data hidden from the teachers (unless all teachers collude, which is unlikely).
Robustness: Automatically detects and removes bad/cheating answers.
Verifiability: Proves to the students that the teachers actually did the math correctly and didn't cheat.

It works with many different "rules" for deciding which answers are good (like Krum, Trimmed Mean, and FLTrust), making it a flexible tool for secure group learning.

Technical Summary: PRoVeFL

1. Problem Statement

Federated Learning (FL) enables collaborative model training while preserving data locality, yet standard frameworks face a triad of security challenges:

Privacy: Traditional FL assumes an honest-but-curious server, but model updates can leak sensitive information via inference attacks. While technologies like Secure Multi-Party Computation (SMPC) and Fully Homomorphic Encryption (FHE) offer privacy, they often obscure the data so thoroughly that identifying malicious updates becomes difficult.
Byzantine Robustness: Malicious clients can poison the global model through crafted updates. While robust aggregation rules (e.g., Krum, Trimmed Mean) exist, integrating them with strong privacy guarantees often incurs prohibitive computational and communication overhead or relies on relaxed trust assumptions.
Verifiability: Clients must trust that the server correctly aggregates updates and enforces robustness rules. Existing verifiable aggregation protocols often assume all client inputs are legitimate or fail to support complex, state-of-the-art robustness algorithms.

Current solutions struggle to simultaneously achieve privacy, Byzantine robustness, and verifiability without incurring massive performance costs or restricting the types of aggregation rules that can be used.

2. Methodology: The PRoVeFL Framework

The authors propose PRoVeFL (Private Robust and Verifiable FL), a modular framework designed to satisfy all three properties simultaneously. The system employs a multi-server architecture (requiring at least two servers, with the assumption that at least one is honest) and leverages Multi-Key Fully Homomorphic Encryption (MK-FHE).

Core Architectural Principles

Multi-Key FHE & Threshold Decryption: Clients encrypt local model updates under a group public key derived from the servers' individual key shares. No single server holds the full secret key; decryption requires collaboration. This ensures that client updates remain private unless all servers collude.
Hybrid Computation Model (Ciphertext-to-Plaintext Offloading): A central innovation of PRoVeFL is the use of a random multiplicative mask ( $r$ ).
- Clients encrypt their updates and homomorphically multiply them by an encrypted random mask $Enc_{pk}(r)$ .
- Servers perform necessary statistical operations (e.g., distance calculations, sorting) on the encrypted, masked data.
- Servers collaboratively decrypt the results, revealing only the masked intermediate values ( $r \cdot \text{value}$ ).
- Because the random mask $r$ is unknown to any single party and changes per round, the plaintext values remain hidden. However, the mask preserves the relative ordering of values.
- This allows computationally expensive, non-linear operations (such as sorting, comparison, and selection for robustness) to be performed efficiently in the plaintext domain on the masked values, rather than entirely within the expensive ciphertext domain.
Commitment-Based Verification: To ensure integrity, clients publish discrete logarithmic commitments to their data. Servers generate cryptographic proofs for their aggregation steps. Peer servers verify these proofs using bilinear pairings or group laws before proceeding. If verification fails, the protocol aborts, preventing the acceptance of tampered results.

Instantiation of Aggregation Rules

PRoVeFL is designed to be compatible with a wide range of Byzantine-robust algorithms by mapping their logic to four core cryptographic primitives: Linear Aggregation (LA), Pairwise Statistical Evaluation (PSE), Secure Comparison and Ordering (SCO), and Selection and Filtering (SF). The paper demonstrates this by instantiating:

Krum: Computes pairwise Euclidean distances in the encrypted domain, decrypts masked distances, and selects the update with the minimal score in plaintext.
Trimmed Mean: Computes coordinate-wise differences, sorts them using a secure compare-and-swap network (Batcher's odd-even mergesort) on encrypted data, decrypts the masked differences, and trims extremes in plaintext.
FLTrust: Computes cosine similarity weights against a trusted reference vector in the encrypted domain, decrypts masked scores, and performs weighted averaging in plaintext.
MESAS: The framework is noted as extensible to other complex schemes involving clustering and variance calculations.

3. Key Contributions

Unified Framework: PRoVeFL is the first framework to simultaneously guarantee client update privacy, Byzantine robustness, and server-side verifiability under a distributed trust model (assuming at least one honest server).
Efficiency via Hybrid Computation: By offloading complex selection and filtering logic to the plaintext domain using a random multiplicative mask, PRoVeFL significantly reduces the computational burden compared to purely FHE-based approaches.
Algorithmic Flexibility: Unlike prior works that enforce simple heuristics (e.g., norm clipping), PRoVeFL supports complex, state-of-the-art aggregation rules (Krum, Trimmed Mean, FLTrust, MESAS) that require sorting and pairwise comparisons.
Scalability: The multi-server design distributes the computational load. The framework scales with the number of servers without burdening clients with additional communication or computation.

4. Results and Evaluation

The authors evaluate PRoVeFL across varying numbers of parameters, participants, and servers, comparing it against distributed trust-based works Prio and ELSA.

Performance: PRoVeFL demonstrates significant runtime improvements, achieving speedups of up to 100× over Prio and 10× over ELSA, while maintaining comparable security guarantees.
Scalability: The system maintains efficiency as the number of parameters and participants increases, validating the modular multi-server architecture.
Compatibility: The successful implementation of Krum, Trimmed Mean, FLTrust, and MESAS confirms the framework's ability to handle diverse statistical operations required for robust aggregation.

5. Significance and Claims

The paper claims that PRoVeFL addresses the fundamental trade-off between privacy, integrity, and verifiability in Federated Learning. By introducing a modular, multi-server architecture that strategically combines MK-FHE with controlled plaintext computation, the authors argue that PRoVeFL makes robust and verifiable FL practical for real-world deployment.

The significance lies in moving beyond "simple" robustness measures (like norm clipping) to support complex, state-of-the-art defenses without sacrificing privacy or incurring the prohibitive costs of pure homomorphic evaluation. The framework provides a path to deploy FL in high-stakes environments (e.g., healthcare, finance) where data privacy, model integrity, and the ability to audit the aggregation process are simultaneously critical.