SADS: Shielding Mobile Social Networks from Sybil Attacks through Homomorphic Encryption

TL;DR

Mobile Social Networks (MSN) face a critical paradox: how can we stop an attacker from creating a thousand fake "Sybil" identities if the system is designed to keep everyone's real identity anonymous? SADS (Sybil Attack Detection Scheme) resolves this by using Paillier homomorphic encryption and discrete time-stamping. It ensures that while your identity remains a secret, your ability to "multiply" is restricted to exactly one ID per time period—enabling detection without surveillance.

The "Anonymity vs. Accountability" Conflict

In the world of MSNs, Sybil attacks are devastating. A single malicious user can create fake accounts to manipulate community ratings, spread misinformation, or compromise collaborative decision-making.

Existing graph-based defenses (like SybilGuard or SybilLimit) often assume that social networks are "fast mixing"—meaning honest nodes are well-connected and easily distinguishable from tightly-knit clusters of fake accounts. However, mobile networks are chaotic, transient, and rarely meet these mathematical assumptions. Furthermore, most systems that catch Sybils do so by breaking user privacy, which is a non-starter for modern privacy-conscious applications.

Methodology: The Logic of Time-Bound Cryptography

The core innovation of SADS lies in how Pseudo-Identities (PIDs) are constructed. Instead of a static pseudonym, SADS generates a PID that is a function of:

1. The user's real identity (encrypted via AES).
2. A unique security key $r$.
3. A specific time stamp $T_i$.

Architecture Overview

The system involves a Trusted Authority (TA) and the mobile nodes. The TA manages the encryption parameters and the revocation of malicious actors.

Mathematical Intuition

The PID is calculated as: $PI{D}_i=g^{Enc(RID,sk)}\cdot \mathcal{H}(r||T_i{)}^n\mathrm{mod}{n}^2$

By using Paillier encryption, the TA can verify identity-related information without decrypting the $RID$ for every interaction. Because the hash $\mathcal{H}(r||T_i)$ changes with every time interval, a user's ID at 10:00 AM looks completely unrelated to their ID at 10:05 AM (Indistinguishability). However, within that 5-minute window, they can only produce one valid signature. If they try to use two, the collision is detectable.

Revocation and Detection

SADS doesn't just block PIDs; it provides a mechanism for Revocation:

• Algorithm 1 (Sybil Checking): When a user is reported, the TA uses its private key to extract the encrypted real identity. If the same user appears multiple times under different covers, they are flagged.
• Algorithm 2 (User-side Detection): The TA publishes a "Revocation List" containing specific parameters (${\Delta }_k$, $r_k$). Any honest user can perform a local computation to check if the person they are talking to matches a revoked entry, without ever learning that person's true ID.

Performance Benchmarks & Optimization

Cryptographic overhead is a common bottleneck in mobile environments. SADS addresses this by implementing a Rolling Window Strategy.

• Storage Efficiency: The suspicious and revocation lists do not grow indefinitely. Identities are purged after a time $T_0$, assuming that malicious behavior loses its impact over time or the attacker has likely cycled their keys.
• Computational Complexity: By limiting the list length to $l$, both detection and revocation maintain a complexity of $O(l)$, making them viable for modern smartphones.

Critical Insight & Conclusion

The elegance of SADS is that it preserves Past Privacy. Even if a user is caught being a Sybil in the "current" time stamp and revoked, their previous identities from past time stamps remain unlinkable. This offers a "right to be forgotten" while maintaining "duty to be honest" in the present.

Limitations: The scheme still relies heavily on a centralized Trusted Authority. Future research might investigate shifting this architecture toward a Decentralized Identifier (DID) model or using State Space Models for more dynamic behavior analysis beyond simple time-stamping.

Takeaway: SADS successfully shifts the Sybil defense paradigm from "analyzing social connections" to "mathematical enforcement of temporal uniqueness."