Private Resource Allocators and Their Applications

Explore a new cryptographic primitive called private resource allocators (PRAs) for allocating resources without revealing allocation information to clients. Learn about various PRA constructions offering guarantees from information-theoretic to differential privacy. Discover how PRAs prevent allocation-based side-channel attacks, which can compromise privacy in anonymous messaging systems. Examine the implementation of PRAs in Alpenhorn and its impact on network resources. Delve into allocation indistinguishability, avoiding trivial allocators, and the challenges of achieving privacy and liveness in allocators. Compare different PRA efficiencies and understand their applications in various settings, including those with unbounded active processes.

Intro
When an application consumes resources...
Attack on anonymous messengers [WPES '18]
Other examples of resource allocation
Allocation indistinguishability
Avoiding trivial allocators
Easy to distinguish FIFO allocator
Easy to distinguish Random allocator
Giving up work conservation is not enough
It is impossible for an allocator to be private and live unless the number of processes is bounded a priori
Slot-based allocator (bounded universe)
Random w/ dummies (bounded active proc.)
In many settings it is hard to bound #active processes due to, e.g., sybils
Diff. private allocator (bounded active honest)
Comparison of PRA efficiency
Our paper also describes