Privacy Preserving OpenPGP Public Key Distribution with Spamming Resistance

OpenPGP public key distribution via Synchronizing KeyServers (SKS) is facing the challenges of user privacy leakage caused by keyword search behaviors and service unavailability of OpenPGP software caused by OpenPGP certificate spamming attack (CVE-2019-13050). Most existing solutions to the problem dispense with the necessary features and functions of SKS or Web of Trust (WoT) for attack mitigation. In this paper, we put forward a solution which is privacy-preserving and spamming-resistant, while maintaining the functionalities of SKS and WoT. Considering the characteristics of our scenario, we protect user privacy by introducing a third-party server, and propose a specific third party-based private set intersection protocol to improve usability of OpenPGP software. Our protocol helps users filter out the required key data by intersection computation between unbalanced sets of keywords. We also propose an enhanced scheme for multi-key query and further privacy protection. We evaluate the usability and privacy of our schemes. Experimental results show that our scheme can largely reduce unnecessary data download with appropriate filter parameters. The proposed solution relies on the security of Elliptic Curve Diffie–Hellman, HMAC-based Key Derivation Function, Bloom filter and symmetric cryptographic encryption to defend against semi-honest adversaries.