Cryptology ePrint Archive: Report 2020/287

Private resource allocators and their applications

Sebastian Angel and Sampath Kannan and Zachary Ratliff

Abstract: This paper introduces a new cryptographic primitive called a private resource allocator (PRA) that can be used to allocate resources (e.g., network bandwidth, CPUs) to a set of clients without revealing to the clients whether any other clients received resources. We give several constructions of PRAs that provide guarantees ranging from information-theoretic to differential privacy. PRAs are useful in preventing a new class of attacks that we call allocation-based side-channel attacks. These attacks can be used, for example, to break the privacy guarantees of anonymous messaging systems that were designed specifically to defend against side-channel and traffic analysis attacks. Our implementation of PRAs in Alpenhorn, which is a recent anonymous messaging system, shows that PRAs increase the network resources required to start a conversation by up to 16X (can be made as low as 4X in some cases), but add no overhead once the conversation has been established.

Category / Keywords: cryptographic protocols / resource allocation, side channels, information theory,

Original Publication (in the same form): IEEE Security and Privacy (S&P) 2020

Date: received 4 Mar 2020

Contact author: sebastian angel at cis upenn edu

Available format(s): PDF | BibTeX Citation

Version: 20200306:084943 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]