DKVE: Decentralized Key Validation for End-to-End Encrypted Messaging

Source: arXiv:2606.26486 · Published 2026-06-25 · By Subin Song, Taekyoung Kwon

TL;DR

Evaluations via simulations on large real-world social graph datasets (Facebook, Pokec, VKontakte) demonstrate DKVE can detect MitM attacks with approximately 97% probability on strong-to-moderate social ties, substantially reducing reliance on OOB or KT checks (by roughly two orders of magnitude). A proof-of-concept implementation on commodity hardware confirms low latency and bandwidth overheads suitable for background operation. DKVE’s approach also permits more storage-efficient key transparency infrastructures, like RSA accumulators, by lowering query frequencies. However, DKVE does not fully replace existing methods due to bootstrapping issues for new users and diminished efficacy in weak-tie networks, positioning it as a practical complementary mechanism for scalable, secure messaging at billion-user scale.

Key findings

• DKVE achieves approx. 97.2% protocol success rate and 0.3% false negative rate, resulting in ~97% MitM detection probability on strong-to-moderate-tie networks (p.2, §6).
• DKVE reduces the frequency of key transparency queries by two orders of magnitude, enabling KT directories to migrate from Merkle trees to space-efficient data structures like RSA accumulators (p.2, §1).
• The Sequential Probability Ratio Test (SPRT) used by DKVE enables detection of server cheating with user-configurable error bounds α (false positive rate) and β (false negative rate), balancing query cost and detection accuracy (p.8, §4.3).
• Simulation across Facebook, Pokec, and VKontakte datasets shows detection remains high (> 97%) even when up to a fixed proportion µmal of mutual contacts are malicious or compromised (p.10, §6).
• Privacy is preserved bidirectionally by combining OPRF and OKVS primitives – the querier’s query targets remain hidden from responders; the responder’s contact lists remain secret from queriers except for existence of queried targets (p.7, §4.2).
• Protocol overhead in latency and bandwidth is low enough for background execution on commodity hardware, making it practical for real-world deployment (p.11, §6.2).
• DKVE cannot cross-validate keys for newly joined users without mutual contacts, requiring fallback on OOB or KT methods for initial key verification (p.9, §4.3).
• Setting α and β too low increases protocol failure rate due to limited responders, requiring tuned trade-offs to minimize fallback validation load (p.9, §4.3.1).

Threat model

DKVE addresses an adversary controlling the key directory server that may maliciously distribute fraudulent public keys to perform man-in-the-middle attacks. The server is rational with reputational incentives to avoid obvious attacks, focusing on covert misbehavior. Up to a bounded fraction µmal of mutual contacts queried for cross-validation may be malicious or compromised, potentially colluding with the server. The querier user is honest-but-curious, and responders may be malicious but do not disrupt protocol besides sending false keys. DKVE does not address detection of malicious responders directly.

Methodology — deep read

1. Threat model and assumptions: DKVE mitigates man-in-the-middle (MitM) attacks from a malicious key directory server capable of distributing false public keys to users. The server has strong reputational incentives to avoid obvious cheating, so attacks are covert and probabilistically detectable. Querier users are honest but curious, following the protocol but potentially trying to learn additional info. Responders (mutual contacts queried) may be malicious or compromised, providing false responses that DKVE tolerates up to a bounded fraction µmal. Collusion between malicious responders and the server is allowed. New users without mutual contacts must rely on OOB or KT fallback.

2. Data provenance and preprocessing: The authors simulate DKVE on large-scale publicly available real-world social graphs: Facebook, Pokec, and VKontakte. The contact relationships form directed graphs representing users and their contacts. These graph structures are used to model social ties and mutual contacts for query selection. Key validity is simulated by injecting server cheating and malicious responder behavior.

3. Architecture and algorithms: DKVE uses Oblivious Pseudorandom Functions (OPRF) allowing a querier to blind their query targets and obliviously evaluate pseudorandom outputs with responders without revealing queries. Oblivious Key-Value Stores (OKVS) encode responders' contact lists so queriers can obliviously decode key responses without learning full contact lists. The core protocol CROSSVALQUERY involves the querier generating OPRF evaluations of target usernames, sending them to responders who encode matched keys in OKVS forms, then sending back to the querier for decoding and comparison with server keys.

The querier aggregates multiple such responses and applies a Sequential Probability Ratio Test (SPRT) for a statistical hypothesis test of server honesty. SPRT iteratively updates a log-likelihood ratio based on match/mismatch responses from mutual contacts, stopping when sufficient evidence is reached or no responders remain. User-configurable error thresholds α (false positive) and β (false negative) control detection sensitivity.

4. Training Regime: As a protocol paper, no traditional ML training is involved. Performance optimizations occur via batch OPRF processing over sets of target usernames to improve efficiency.

5. Evaluation protocol: The authors simulate DKVE over real social graphs by injecting malicious server behavior and varying malicious contact fractions µmal to study detection rates, false positives, false negatives, required number of responders, and bandwidth/latency overhead. Metrics include detection rate (1-β), false positive rate (α), protocol success rate (percentage of queries resolved without fallback), and operational costs. Ablations consider impact of social tie strength and error bound values. The evaluation demonstrates robustness against malicious contacts and scalability gains in reducing KT queries.

6. Reproducibility: The paper provides a proof-of-concept implementation integrated with the Matrix E2EE protocol, showing viability. Simulation datasets (Facebook, Pokec, VKontakte graphs) are publicly known, but full source code or parameters for the implementation or simulation are not explicitly mentioned, which may limit exact reproducibility.

A concrete example: Suppose Alice queries Carol's public key and obtains it from the key server. Alice identifies mutual contacts (e.g., Bob) and performs CROSSVALQUERY by 1) running OPRF to blind Carol's username, sending to Bob; 2) Bob evaluates OPRF on his encoded contact list and encodes keys in OKVS form; 3) Bob sends OKVS to Alice; 4) Alice decodes and compares Bob's reported key for Carol with the key server's; 5) Alice aggregates multiple such comparisons through SPRT, determining if key server is honest within error bounds α, β, or flags misbehavior for fallback verification.

Technical innovations

• A novel protocol (DKVE) that performs privacy-preserving public key cross-validation by leveraging mutual contacts in a user's social graph via OPRF and OKVS primitives.
• Application of Sequential Probability Ratio Test (SPRT) to aggregate probabilistic evidence from multiple responders, allowing configurable error bounds on detection of malicious key servers.
• Use of OKVS labels based on OPRF outputs to prevent queriers from brute-forcing responders' contact lists, thereby preserving responder privacy during cross-validation.
• Architectural integration enabling KT query frequency reduction by two orders of magnitude, facilitating migration from expensive Merkle-tree-based data structures to space-efficient RSA accumulators.

Datasets

• Facebook social graph — size not specified — publicly available social network dataset
• Pokec social network — size not specified — publicly available dataset
• VKontakte social graph — size not specified — publicly available dataset

Baselines vs proposed

• Out-of-Band Verification: High security but not scalable; requires manual per-contact checks.
• Key Transparency (e.g., CONIKS, Parakeet): Scalable automated verification with significant storage costs (~26.9 TB for 1B users).
• DKVE reduces required KT queries by 100x while maintaining approx. 97% MitM detection rate on strong/moderate ties.

Limitations

• DKVE cannot verify the first contact key for newly joined users lacking mutual contacts; reliance on fallback OOB or KT remains necessary.
• Detection guarantees are probabilistic with non-zero false negative rate β, allowing some undetected server misbehavior under collusion with malicious contacts.
• Performance and detection degrade on weak-tie social networks where mutual contacts are sparse.
• Assumption that the fraction of malicious contacts µmal remains bounded per user; adversaries violating this weaken guarantees.
• Protocol success depends on tuning error bounds α and β, balancing false alarms and fallback frequency; extreme settings can cause high protocol failure rate.
• Privacy guarantees assume honest-but-curious queriers and responders, with malicious responders limited to providing false keys but not active protocol disruption.

Open questions / follow-ons

• How can DKVE be extended to support initial key validation for new users lacking mutual contacts?
• What are practical deployment strategies for bootstrapping trusted keys in large, dynamic social graphs where contacts change frequently?
• Could DKVE be adapted to withstand stronger active adversaries, including malicious queriers or denial-of-service behaviors?
• Can the protocol efficiency and cryptographic operations be further optimized for resource-constrained devices while preserving privacy guarantees?

Why it matters for bot defense

Moreover, DKVE’s integration of Oblivious Pseudorandom Functions and Oblivious Key-Value Stores provides a compelling blueprint for privacy-aware query protocols that avoid revealing sensitive attributes—similar concepts that might enhance user query privacy in bot detection systems. While targeted at key validation rather than bot detection, DKVE’s methodology underpins the broader notion of leveraging social structures and privacy-preserving cryptography to improve security in large-scale distributed systems, a valuable insight for CAPTCHA and behavioral bot defense research.

Cite

@article{arxiv2606_26486,
  title={ DKVE: Decentralized Key Validation for End-to-End Encrypted Messaging },
  author={ Subin Song and Taekyoung Kwon },
  journal={arXiv preprint arXiv:2606.26486},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.26486}
}

Read the full paper

• arXiv:2606.26486 (abstract)
• arXiv:2606.26486 (PDF)