We design FrodoPIR — a highly configurable, stateful, single-server Private Information Retrieval (PIR) scheme that involves an offline phase that is completely client-independent. Coupled with small online overheads, it leads to much smaller amortized financial costs on the server-side than previous approaches. In terms of performance for a database of 1 million 1KB elements, FrodoPIR requires < 1 second for responding to a client query, has a server response size blow-up factor of < 3.6x, and financial costs are ~$1 for answering 100,000 client queries. Our experimental analysis is built upon a simple, non-optimized Rust implementation, illustrating that FrodoPIR is particularly suitable for deployments that involve large numbers of clients.

Distributed Virtual Private Networks (dVPNs) are new solutions aiming to solve the trust-privacy concern of a VPN's central authority by leveraging a distributed architecture. In this paper, we discuss the requirements of a successful dVPN system and we present VPN-Zero: a dVPN system with strong privacy guarantees that provides traffic accounting and has minimal performance impact on its users. VPN-Zero guarantees that a dVPN node only carries traffic it has “allowlisted”, without revealing its allowlist or knowing the traffic it tunnels. This is achieved via three main innovations: (a) an attestation mechanism which leverages TLS to certify a user visit to a specific domain, (b) a zero-knowledge proof to certify that some incoming traffic is authorized (e.g., falls in a node's allowlist, without disclosing the target domain), and (c) a dynamic chain of VPN tunnels to both increase privacy and guarantee service continuation while traffic certification is in place. The paper demonstrates VPN-Zero functioning when integrated with two production systems: BitTorrent's Distributed Hash Table and ProtonVPN. Early evaluation results show that the median setup time of VPN-Zero is about 10 seconds.