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

• URL: http://arxiv.org/abs/2606.26486v1
• Date: Thu, 25 Jun 2026 00:43:59 GMT
• Title: DKVE: Decentralized Key Validation for End-to-End Encrypted Messaging
• Abstract summary: End-to-end encrypted messaging systems depend on authentic public key distribution to prevent man-in-the-middle (MitM) attacks.<n>Current solutions present a stark trade-off: out-of-band (OOB) verification provides strong security but lacks scalability for large contact lists.<n>We propose DKVE, a protocol that validates public keys through privacy-preserving cross-validation within users' social graphs.
• Score: 0.7978226788634308
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: End-to-end encrypted messaging systems depend on authentic public key distribution to prevent man-in-the-middle (MitM) attacks. Current solutions present a stark trade-off: out-of-band (OOB) verification provides strong security but lacks scalability for large contact lists, while key transparency (KT) systems enable automated verification at high storage costs and operational complexity. We propose DKVE, a protocol that validates public keys through privacy-preserving cross-validation within users' social graphs. When obtaining a contact's public key from a key server, clients query mutual contacts to verify they hold the same key, combining Oblivious Pseudorandom Functions (OPRF) and Oblivious Key-Value Stores (OKVS) to preserve privacy of both queries and contact lists. DKVE employs a Sequential Probability Ratio Test (SPRT) to aggregate responses and detect server misbehavior with user-configurable error bounds. We evaluate DKVE through simulations on real social network datasets, demonstrating DKVE can detect MitM attacks with exceeding 97% for strong-to-moderate-tie networks. The remaining 3% of cases require validation through alternative methods such as KT and OOB verification. Our proof-of-concept implementation confirms feasibility for background operation on commodity hardware, in terms of the latency and bandwidth. As DKVE can reduce the frequency of KT queries by two orders of magnitude, it enables fundamental architectural shifts: KT directories can migrate from fast but space-inefficient Merkle trees to space-efficient data structures like RSA accumulators. While DKVE cannot replace existing methods entirely -- suffering from bootstrapping problems and degraded performance on weak-tie networks -- it provides a practical complementary key validation mechanism, making secure messaging more deployable for billion-user systems.

Related papers

• GCVE: A Decentralized Model for Vulnerability Identification, Publication, and Operational Enrichment [51.77969450792284]
  The Global CVE initiative (G) proposes a decentralized, open, and identifier model for vulnerability identification, publication, and enrichment.<n>This paper presents G as socio-technical effort combining autonomous G Numbering Authorities, lightweight allocation rules, distributed publication, open Best Current Practices, and practical reference implementations.
  arXiv  Detail & Related papers  (2026-05-30T19:03:39Z)
• Towards Privacy-Preserving Federated Learning using Hybrid Homomorphic Encryption [2.1095754823099657]
  Federated Learning (FL) enables collaborative training while keeping sensitive data on clients' devices, but local model updates can still leak private information.<n> Hybrid Homomorphic Encryption (HHE) has recently been applied to FL to mitigate client overhead while preserving privacy.<n>We integrate two alternative key protection mechanisms into the HHE-FL workflow.
  arXiv  Detail & Related papers  (2026-03-27T13:46:29Z)
• Send the Key in Cleartext: Halving Key Consumption while Preserving Unconditional Security in QKD Authentication [59.664950447941386]
  Quantum Key Distribution (QKD) protocols require Information-Theoretically Secure (ITS) authentication of the classical channel to preserve the unconditional security of the distilled key.<n>Since QKD requires mutual authentication, two independent one-time keys are typically consumed per round, imposing a non-trivial overhead on the net secure key rate.<n>We present a novel ITS authentication scheme based on $varepsilon$-Almost Strongly Universal$ ($varepsilon$-ASU$)
  arXiv  Detail & Related papers  (2026-03-26T14:36:05Z)
• Publicly Verifiable Private Information Retrieval Protocols Based on Function Secret Sharing [45.68069331331365]
  Private Information Retrieval (PIR) is a cryptographic primitive that enables users to retrieve data from a database without revealing which item is being accessed.<n>We propose two effective constructions of publicly verifiable PIR (PVPIR) in the multi-server setting, which achieve query privacy, correctness, and verifiability simultaneously.
  arXiv  Detail & Related papers  (2025-09-17T04:28:47Z)
• Trusted Compute Units: A Framework for Chained Verifiable Computations [41.94295877935867]
  This paper introduces the Trusted Compute Unit (TCU), a unifying framework that enables composable and interoperable computations across heterogeneous technologies.<n>By enabling secure off-chain interactions without incurring on-chain confirmation delays or gas fees, TCUs significantly improve system performance and scalability.
  arXiv  Detail & Related papers  (2025-04-22T09:01:55Z)
• Privacy Enhanced QKD Networks: Zero Trust Relay Architecture based on Homomorphic Encryption [0.0]
  Quantum key distribution (QKD) enables unconditionally secure symmetric key exchange between parties.<n>Traditional solutions rely on trusted relay nodes, which perform intermediate re-encryption of keys using one-time pad (OTP) encryption.<n>We propose a zero-trust relay design that applies fully homomorphic encryption (FHE) to perform intermediate OTP re-encryption.
  arXiv  Detail & Related papers  (2025-03-21T10:20:06Z)
• HOPE: Homomorphic Order-Preserving Encryption for Outsourced Databases -- A Stateless Approach [0.7770535067924795]
  Homomorphic OPE (HOPE) is a new OPE scheme that eliminates client-side storage and avoids additional client-server interaction during query execution.<n>We provide a formal cryptographic analysis of HOPE, proving its security under the widely accepted IND-OCPA model.
  arXiv  Detail & Related papers  (2024-11-26T00:38:46Z)
• CryptoFormalEval: Integrating LLMs and Formal Verification for Automated Cryptographic Protocol Vulnerability Detection [41.94295877935867]
  We introduce a benchmark to assess the ability of Large Language Models to autonomously identify vulnerabilities in new cryptographic protocols. We created a dataset of novel, flawed, communication protocols and designed a method to automatically verify the vulnerabilities found by the AI agents.
  arXiv  Detail & Related papers  (2024-11-20T14:16:55Z)
• Distributed Symmetric Key Establishment: a Scalable Quantum-Safe Key Distribution Protocol [4.1010893028706255]
  Pre-shared keys (PSK) have been widely used in network security. Existing PSK solutions are not scalable. We propose a new protocol called Distributed Symmetric Key Establishment (DSKE)
  arXiv  Detail & Related papers  (2024-07-30T16:55:17Z)
• A Survey and Comparative Analysis of Security Properties of CAN Authentication Protocols [92.81385447582882]
  The Controller Area Network (CAN) bus leaves in-vehicle communications inherently non-secure. This paper reviews and compares the 15 most prominent authentication protocols for the CAN bus. We evaluate protocols based on essential operational criteria that contribute to ease of implementation.
  arXiv  Detail & Related papers  (2024-01-19T14:52:04Z)
• Upper bounds on key rates in device-independent quantum key distribution based on convex-combination attacks [1.118478900782898]
  We present the convex-combination attack as an efficient, easy-to-use technique for upper-bounding DIQKD key rates. It allows verifying the accuracy of lower bounds on key rates for state-of-the-art protocols.
  arXiv  Detail & Related papers  (2022-06-13T15:27:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.