The authors of this paper begin by calling into question whether encryption of data is sufficient for hiding the data in its entirety. It’s clear that through metadata associated with encrypted data, using an encryption scheme is a necessary, but not sufficient requirement to communicate in a truly anonymous fashion. The goal of Riposte is to provide a service where, across a day, multiple users may be pinging a web app that is hosted on multiple servers. The end goal is such that while the users may be public and the persistence tier contains all the plaintext messages, the databases should not be able to recover which user wrote which message. Hiding metadata, whether it be private messaging or anonymous services, is an important building block to anonymous communication. The authors also argue that existing systems like Tor or Mix-nets either do not protect against a global adversary or require expensive ZKPs to protect against active attacks. The ultimate goal of Riposte is to be an anonymous messaging system that protects against a near-global active adversary while handling millions of users and their requests.

From the scenario of a service with multiple users pinging multiple servers running the same app, the paper first describes an ideal scheme that proves how perfect anonymity and practical efficiency can be achieved by simply using “blinding vectors” when writing values to the database. Multiple servers can come together, sum their copies of each value, and determine the original plain text messages without knowing who wrote which message. This scheme would protect against up to k-1 colluding servers, and there’s no real costly operations that are involved. However, write collisions, malicious clients, and the bandwidth cost are all vulnerabilities. The paper addresses write collisions by setting the size of the database table such that it has a high likelihood of enough space to accommodate for all write requests. To guard against malicious users, the paper uses existing techniques including zero knowledge proofs and the three-server protocol to mitigate such attempts. Bandwidth efficiency is a bit more interesting, where instead of forcing users to send a DB sized blind vector with each message, a PIR technique is employed to compress the vector (i.e., Distributed Point Function).

I think the performance of this system at scale would be the most straightforward next step. As the number of users and messages increase, simply scaling up the number of servers may not be a satisfactory solution. It’d be interesting to see if more PIR techniques could be employed, since there is a lot of retrieval that is required whether it be users writing data or the databases summing the values together to generate the resulting plaintext. I thought the evaluation provided a lot of strong bounds to complement the theory previously put forth. However, tests involving running this system in a real production system subject to actively malicious users could be a good test of some of the security primitives that were mentioned. I thought section 6.3 was interesting, but more complementary graphics would’ve been helpful.

From a more entrepreneurial standpoint, if this system were to work at scale, it could be interesting to see it adopted in existing platforms that should have an immediate interest in such work (i.e., anonymous communities with < 1 million people). Apps like YikYak or Whisper fit the bill of a product that users could trust to effectively protect communication.