Search papers, labs, and topics across Lattice.
This paper introduces DKVE, a decentralized protocol that enhances public key validation in end-to-end encrypted messaging by leveraging privacy-preserving cross-validation within users' social graphs. By combining Oblivious Pseudorandom Functions and Oblivious Key-Value Stores, DKVE effectively mitigates man-in-the-middle attacks while maintaining user privacy and significantly reducing the reliance on traditional key transparency methods. Simulations show that DKVE achieves over 97% detection of MitM attacks in strong-to-moderate-tie networks, offering a scalable solution for secure messaging in large user bases.
DKVE slashes the need for traditional key transparency queries by two orders of magnitude, making secure messaging feasible for billion-user systems.
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.
