Papers worth reading: Oblivious Sets

Secret management in distributed systems is on the rise, the need to securely manage sensitive information whilst maintaining performance makes it a hard problem to solve. Currently, there are a couple of open source projects which aim to address this issue, namely:

All of these secret management systems offer some form of encryption, so in general only the service which created the secret can access it. One of the big issues with these systems is that they’re mostly centralised, you have to trust the server which runs the service. You also get all the same problems that any centralised service offers in a distributed system, a centralised bottleneck and potentially a brittle keystone.

While these all offer different services, the big property that they all must share is passing sensitive information between machines, only allowing machines which are aware of the secrets to possess them. Ideally, making it as hard as possible to listen in as possible for an attacker. Conveniently, this relates to the main paper at hand, “Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity”. If you want to jump straight into playing with Oblivious Sets without reading the rest of this post, there’s an implementation of some of these algorithms in Python.

So what exactly are Oblivious Sets?

In essence, it’s literally just set operations with cryptographic-level obfuscation. The most commonly studied set operation is intersection, since it’s the most common useful set operation in practice. “Private and Oblivious Set and Multiset Operations” is a really good paper on dealing with more set operations than just intersections, if you want to read about this area of study in more depth.

Diagram of two private sets and the intersection