Beyond Passwords: How OSNs Can Authenticate Identity Through Shared Memories

TL;DR

Authenticating a friend in an Online Social Network (OSN) shouldn't require a pre-shared PGP key or a Trusted Third Party. This paper proposes a protocol that uses exclusive secrets—shared answers to personal questions—to generate a high-entropy session key. By utilizing error-correcting codes, it remains robust even if your friend forgets whether you had dinner last Friday or Saturday.

The Problem: The Authentication Paradox in Social Media

Most security protocols operate on a "catch-22": to communicate securely, you need to share a secret first. But in OSNs, users often connect with real-life acquaintances without a secure channel to exchange keys (like encrypted email).

The authors identify three fatal flaws in current approaches:

1. The TTP Vulnerability: Relying on service providers (like Facebook or Email hosts) to hold public keys allows those providers to impersonate users.
2. The Rigidity of Secrets: Existing "shared knowledge" protocols require 100% character-perfect matches. If one user types "Last Friday" and the other types "last friday," the authentication fails.
3. Low-Entropy Weakness: Human-memorable secrets are short and vulnerable to brute-force attacks.

The Solution: Error-Tolerant Authenticated Key Exchange (AKE)

The core insight is to treat shared human memories as "noisy data." Just as biometrics use Fuzzy Extractors to handle noise, this protocol uses Information Reconciliation.

1. The Question-Answer Paradigm

The authenticator (Alice) picks $n$ binary questions (e.g., "Is Jack a mutual friend?"). These form an "answer string."

2. Information Reconciliation with BCH Codes

To handle the "noise" (human error), the protocol employs $[n,t,d]$ error-correcting codes (specifically binary BCH codes).

• Alice picks a random codeword $cw$.
• She generates a "syndrome" $syn=cw\oplus ans$.
• The authenticatee (Bob) can recover $cw$ even if his answer $an{s}^{\prime }$ is slightly different, provided the distance is $\le \delta$.

3. Cryptographic Hardening

To prevent passive observers from learning the answers, the protocol utilizes Cramer-Shoup Encryption and Zero-Knowledge Proofs (ZKP). This ensures that even if an attacker intercepts the messages, they can't brute-force the low-entropy answers without being detected.

Figure 1: The high-level flow of the identity authentication protocol.

Proving Security: The UC Framework

A major contribution of this paper is proving the protocol in the Universal Composability (UC) framework. This means the protocol remains secure even when it is used as a building block for other complex tasks (like private messaging or Sybil defense). The proof relies on a "Simulator" that shows an attacker in the real world can do no more harm than an attacker in an "ideal" world where a trusted party manages the keys.

Experimental Results: Performance and Accuracy

The authors implemented the protocol using both Discrete Logarithm (DL) and Elliptic Curve Cryptography (ECC).

The ECC version is significantly faster due to shorter ciphertexts and smaller group sizes. More importantly, the protocol handles a standard [31, 21, 5] BCH code, which tolerates 3 errors out of 31 questions—a reasonable margin for human memory.

Figure 2: Execution time across different security parameters for DL groups.

Practical Insight: Why This Matters

This protocol bridges the gap between human intuition and mathematical rigor. It acknowledges that while humans are bad at managing 256-bit hex strings, they are excellent at remembering shared experiences. By providing a mathematical "buffer" for memory errors, it opens the door for decentralized, third-party-free authentication in social apps.

Limitations

• Question Quality: The security depends on the "exclusivity" of the secrets. If the questions are public knowledge (e.g., "What is my birthday?"), the protocol collapses.
• Interaction Overhead: Asking 31 questions might be tedious for casual users, highlighting the need for automatically generated questions based on social graph data.

Conclusion

This OSN-specific AKE protocol provides a robust, error-tolerant way to verify identities. In an era where Sybil attacks and social engineering are rampant, leveraging "naturally pre-distributed" shared memories offers a promising path toward decentralized trust.