💻 computer science

Hidden Elo: Private Matchmaking through Encrypted Rating Systems

This paper introduces H-Elo, a Fully Homomorphic Encryption-based protocol that enables private matchmaking by securely updating traditional rating systems without exposing sensitive user data, achieving accuracy comparable to plaintext implementations while significantly reducing privacy leakage.

Original authors: Mindaugas Budzys, Bin Liu, Antonis Michalas

Published 2026-03-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mindaugas Budzys, Bin Liu, Antonis Michalas

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 are playing a game of chess online. To make the game fun, the system needs to pair you with an opponent of similar skill. If you are a beginner, you don't want to play against a grandmaster; if you are a pro, you don't want to play against a novice.

Currently, most apps solve this by keeping a secret score (like the famous "Elo" rating) on their servers. They know your exact skill level, but they often hide it from you, or worse, they might let you manipulate the system by picking specific opponents to "farm" easy wins. This creates a trust issue: you don't know your true rank, and the server knows everything about you.

The paper "Hidden Elo" proposes a new way to handle this using a magical mathematical tool called Fully Homomorphic Encryption (FHE).

Here is the concept broken down with simple analogies:

1. The Problem: The "Glass Box" Server

Think of the current matchmaking system as a glass box.

You put your skill level inside.
The Server sees everything inside the box clearly.
The Problem: The server can peek at your score, change it, or use it to spy on your habits. You have to trust them completely. Sometimes, they even keep the box locked so you can't see your own score!

2. The Solution: The "Locked Safe" (H-Elo)

The authors propose a system called H-Elo. Instead of a glass box, imagine a high-tech, unbreakable safe that you keep in your own pocket.

The Magic Lock (FHE): This is the core technology. It allows the server to perform math on the contents of the safe without ever opening it.
- Analogy: Imagine you have a locked box containing a number (your rating). You hand the box to a mathematician. They can add 10 points to the number inside, multiply it, or subtract points, all while the box remains locked. When they hand the box back to you, the number inside has changed, but they never saw what the number was.

3. How It Works in Real Life

Here is the step-by-step process of a match in the H-Elo system:

Registration: You tell the server, "I am a 'Gold' level player." You put your exact score into the locked safe and hand it over. You also provide a Zero-Knowledge Proof.
- Analogy: This is like showing a security guard a sealed envelope that says "I am Gold" without opening the envelope to show the number inside. The guard knows you are telling the truth, but they don't know your exact score.
The Match: You play a game. The server knows who you played and the result (Win, Loss, or Draw).
The Update (The Magic): The server needs to update your score based on the game result.
- In the old system, the server would open your box, do the math, and write a new number.
- In H-Elo, the server takes your locked safe, performs the math inside the lock, and hands it back. The score is updated, but the server never saw the number.
Verification: After a few games, the system reveals your new score to you (so you know your rank), but it remains hidden from the server and other players.

4. Why Is This a Big Deal?

The paper highlights three main benefits:

Privacy: The server (the matchmaking app) cannot see your exact rating. They only know which "tier" you are in (e.g., Gold, Silver) to find you a match. They can't spy on your progress or exploit your data.
Fairness: Because the server can't see your exact score, they can't be tricked by players trying to "game the system" by picking easy opponents. The math happens blindly, ensuring fairness.
Future-Proof Security: The math they use is based on "Lattice Cryptography," which is designed to be unbreakable even by future Quantum Computers. It's like building a fortress with materials that haven't been invented yet, just to be safe.

5. The Catch (The Trade-off)

Is it perfect? Not quite.

Speed: Doing math on locked safes is much slower than doing it on open paper. The paper admits that updating a score takes a few seconds (around 23 seconds in their test) compared to a fraction of a second for normal apps.
Memory: It requires a lot of computer memory to keep these "safes" secure.

The Verdict:
The authors argue that this speed trade-off is worth it for privacy. You wouldn't want a dating app or a competitive game to know your every move and exact skill level if you can avoid it.

In a Nutshell:
H-Elo is like hiring a blindfolded referee to update your score. The referee can do the math perfectly to ensure you get a fair opponent, but because they are blindfolded (encrypted), they can never know who you are or how good you actually are. It brings the trust back to the player, not the platform.

1. Problem Statement

Matchmaking systems (used in dating apps, social media, and online gaming) typically rely on rating systems like Elo to pair users of similar skill levels. However, current implementations suffer from significant privacy and security flaws:

Privacy Leakage: Servers often hold and reveal exact ratings, allowing malicious actors to profile user behavior or exploit the system.
User Opacity: In some systems (e.g., previous Tinder algorithms), users are unaware of their own ratings, leading to a lack of transparency.
Exploitation: Players can exploit rating visibility to engage in "selective pairing" (searching for weak opponents to maximize gains), undermining fair competition.
Lack of Secure Alternatives: Existing private matchmaking solutions (like Matchmaking Encryption) often rely on strong trust assumptions or pre-quantum cryptography, making them less suitable for modern, high-security requirements.

The core challenge is to design a protocol that allows for fair, rating-based matchmaking while keeping the exact rating values private from the service provider and other users, yet allowing the user to know their own rating.

2. Methodology: H-Elo Protocol

The authors propose H-Elo (Hidden Elo), a protocol that combines Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKPs) to secure the rating update and matchmaking process.

Core Cryptographic Primitives

CKKS-RNS (Cheon-Kim-Kim-Song Residual Number System): An FHE scheme chosen for its ability to perform arithmetic on approximate real numbers (essential for Elo calculations involving division and floating-point logic) and its post-quantum security based on the Ring Learning With Errors (RLWE) problem.
Non-Interactive Zero-Knowledge Proofs (NIZK): Used to prove that a user's encrypted rating falls within a specific rank range (e.g., "Gold" or "Diamond") without revealing the exact number.
Commitment-Ciphertext Consistency: A specific ZK relation ensuring that the value committed to (for range proofing) matches the value encrypted in the FHE ciphertext, preventing users from submitting valid proofs for one value while encrypting another.

System Architecture

The system involves three entities:

Service Provider (SP): Hosts the matchmaking service, performs homomorphic rating updates, and verifies proofs. It does not learn the exact ratings.
Clients (Users): Hold their own ratings, encrypt them, and generate ZK proofs.
Trusted Key Curator (KC): A semi-trusted entity (potentially running in a TEE) that generates keys and decrypts the final updated rating to reveal it to the user.

Protocol Workflow

The protocol operates in three phases:

User Registration:
- The user selects an initial rating, adds noise, and encrypts it using CKKS.
- The user generates a commitment and a NIZK proof demonstrating the rating lies within the bounds of their claimed rank.
- The SP verifies the proof. If valid, the user is registered with their encrypted rating stored on the server.
Rating Update (Homomorphic):
- After a set number of matches ( $N$ ), the SP retrieves the user's encrypted rating and the encrypted ratings of their opponents.
- The SP computes the new rating homomorphically using the standard Elo formula: $R' = R_{prev} + K \cdot (S_{real} - S_{exp})$ .
- The SP performs polynomial approximation for the expected win probability ( $S_{exp}$ ) and executes the arithmetic on ciphertexts.
- Bootstrapping is applied to refresh noise levels, ensuring precision is maintained after multiple operations.
Rating Verification & Attestation:
- The KC decrypts the updated ciphertext to reveal the new rating to the user.
- The user generates a new commitment and ciphertext for the new rating.
- The KC attests (signs) the consistency of the new rating.
- The user generates a new NIZK proof and submits it to the SP to update their local record, allowing them to continue matchmaking.

3. Key Contributions

First FHE-based Rating System: H-Elo is one of the first protocols to implement a private, secure rating system using FHE, enabling blind calculations of rating updates.
Post-Quantum Security: By utilizing lattice-based cryptography (CKKS-RNS), the system is secure against quantum attacks, unlike many existing solutions relying on bilinear pairings.
Reduced Trust Assumptions: Unlike Matchmaking Encryption (ME), which requires a Trusted Authority to know user attributes and policies, H-Elo only requires the KC to verify the correctness of the update, not the content of the rating itself.
User Transparency: The protocol ensures users know their exact ratings (via the KC decryption step) while keeping them hidden from the SP and other users.
Formal Security Analysis: The authors provide game-based security proofs for:
- N-round Fair Matchmaking: Ensuring ratings are updated correctly and users are matched fairly.
- Hidden Elo: Proving that the SP learns nothing about the exact rating beyond the validity of the range proof (indistinguishability).

4. Experimental Results

The authors implemented H-Elo using the OpenFHE library and benchmarked it on a standard desktop (Intel i7-12700) with three security levels ( $\lambda \approx 12, 80, 128$ ).

Runtime:
- Key Generation: High cost (up to ~4.87s for $\lambda=128$ ) but performed only once during registration.
- Bootstrapping: The most expensive operation (~15.79s for $\lambda=128$ ).
- Full Rating Update: Approximately 23.25 seconds for $\lambda=128$ .
- Note: The authors suggest that in practice, partial updates could be computed incrementally after each match, reducing the final wait time to ~18 seconds.
Memory:
- The primary overhead is storing the Bootstrapping Key (bsk), which reaches ~7.5 GB for $\lambda=128$ . This is manageable for server-side storage but significant for client-side deployment.
Accuracy:
- Despite CKKS being an approximate scheme, the deviation from plaintext Elo calculations is negligible.
- After 10,000 consecutive updates, the mean difference was only $5.569 \times 10^{-4}$ , with a maximum difference of $34.92 \times 10^{-4}$ . This confirms that noise accumulation does not significantly impact matchmaking fairness.

5. Significance and Comparison

Vs. Matchmaking Encryption (ME): While ME is faster, it relies on the Bilinear Diffie-Hellman (BDH) assumption (vulnerable to quantum attacks) and requires a stronger Trusted Authority that knows user attributes. H-Elo trades performance for post-quantum security and weaker trust assumptions.
Practicality: The latency (approx. 18–23s for a full update) makes H-Elo unsuitable for real-time, instant matchmaking (e.g., "find a match in 1 second"). However, it is highly viable for batched updates in scenarios like online tournaments, marketplace reputation systems, or games where ratings are updated after a session concludes.
Future Impact: This work establishes a foundation for privacy-preserving competitive systems, demonstrating that FHE can be used for complex arithmetic (like Elo) with acceptable accuracy, paving the way for decentralized or more trust-minimized matchmaking architectures.

In conclusion, H-Elo successfully bridges the gap between privacy and functionality in rating systems, offering a robust, post-quantum secure solution where users retain control over their data while participating in fair matchmaking.