Riposte

Combining cryptographic primitives in creative ways often results in interesting applications. In this mini-series, we'll look at Riposte, an anonymizing micro-blogging platform for millions of users[GgBM15].

A Riposte system consists of a cluster of Riposte servers, which are ideally located in different jurisdictions. Hundreds to thousands of whistleblowers connect to these servers to anonymously send messages that can't be tracked back to them, so long as at least one server doesn't collude with the others. At the same time, millions of readers can fetch those messages, and by doing so, they too participate in the anonymity set.

To implement such a system, three cryptographic primitives are being leveraged:

  • secret sharing, a technique which allows one to spread a secret to many different recipients, such that no recipient is able to find out on its own what that secret is,
  • writable PIR, a technique which allows users to write to a random row of a database, without the database server knowing which row was actually updated,
  • distributed point functions, a mathematical tool that dramatically reduces the required bandwidth from a writing client to the servers.

We set the stage by introducing Riposte on a high-level. Before looking under Riposte's hood, we'll look at mix-nets, which is how anonymization services have traditionally been implemented, to get a feeling of what needs to be done in order to anonymize users. Then, we'll see how to move from mix-nets to writable PIR, by studying a Riposte toy example with a very simple and easy to understand, but terribly wasteful distributed point function.

Distributed point functions are such a useful tool that we'll spend some more time introducing them in a general way, both informally and formally. Learning DPFs this way is time well-spent, when we set out to look at the special case of an efficient \((2,1)\)-distributed point function.

This mini-series doesn't yet cover the audit server, which is necessary to prevent malicious users from corrupting the database. It also doesn't yet investigate \((n, n-1)\)-DPFs with \(n \gt 2\), which require more sophisticated cryptographic primitives than the efficient pseudo random generator used in the \((2,1)\)-DPF. Former aspect has been fully taken care of by Riposte's creators, but the latter aspect requires additional work.

Further Reading

Source

Dan Boneh's presentation of Riposte:

Literature