This paper presents Riposte, a new system for anonymous broadcast messaging. Riposte is the first such system, to our knowledge, that simultaneously protects against traffic-analysis attacks, prevents anonymous denial-of-service by malicious clients, and scales to million-user anonymity sets. To achieve these properties, Riposte makes novel use of techniques used in systems for private information retrieval and secure multi-party computation. For latency-tolerant workloads with many more readers than writers (e.g. Twitter, Wikileaks), we demonstrate that a three-server Riposte cluster can build an anonymity set of 2,895,216 users in 32 hours.
Our DPF constructions make extensive use of prior work on private information retrieval (PIR) @cite_20 @cite_48 @cite_30 @cite_60 . Recent work demonstrates that it is possible to make theoretical PIR fast enough for practical use @cite_80 @cite_51 @cite_56 . Function secret sharing @cite_78 generalizes DPFs to allow sharing of more sophisticated functions (rather than just point functions). This more powerful primitive may prove useful for PIR and anonymous messaging applications in the future.
@cite_30 @cite_78 @cite_60 @cite_48 @cite_56 @cite_80 @cite_51 @cite_20
171567834 644599125 139740867 74041048 2136631923 2105037262 2073346043
Alice wants to query a database but she does not want the database to learn what she is querying. She can ask for the entire database. Can she get her query answered with less communication? One model of this problem is Private Information Retrieval , henceforth PIR. We survey results obtained about the PIR model including partial answers to the following questions. (1) What if there are k non-communicating copies of the database but they are computationally unbounded? (2) What if there is only one copy of the database and it is computationally bounded? Motivated by the goal of securely searching and updating distributed data, we introduce and study the notion of function secret sharing (FSS). This new notion is a natural generalization of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and Ishai (Eurocrypt 2014). Given a positive integer (p 2 ) and a class ( F ) of functions (f: 0,1 ^n G ), where ( G ) is an Abelian group, a (p )-party FSS scheme for ( F ) allows one to split each (f F ) into (p ) succinctly described functions (f_i: 0,1 ^n G ), (1 i p ), such that: (1) ( _ i=1 ^p f_i=f ), and (2) any strict subset of the (f_i ) hides (f ). Thus, an FSS for ( F ) can be thought of as method for succinctly performing an “additive secret sharing” of functions from ( F ). The original definition of DPF coincides with a two-party FSS for the class of point functions, namely the class of functions that have a nonzero output on at most one input. For x,y ∈ 0,1 *, the point function P x,y is defined by P x,y (x) = y and P x,y (x′) = 0|y| for all x′ ≠ x. We introduce the notion of a distributed point function (DPF), which is a keyed function family F k with the following property. Given x,y specifying a point function, one can efficiently generate a key pair (k 0,k 1) such that: (1) (F_ k_0 F_ k_1 =P_ x,y ), and (2) each of k 0 and k 1 hides x and y. Our main result is an efficient construction of a DPF under the (minimal) assumption that a one-way function exists. The goal of Private Information Retrieval (PIR) is the ability to query a database successfully without the operator of the database server discovering which record(s) of the database the querier is interested in. There are two main classes of PIR protocols: those that provide privacy guarantees based on the computational limitations of servers (CPIR) and those that rely on multiple servers not colluding for privacy (IT-PIR). These two classes have different advantages and disadvantages that make them more or less attractive to designers of PIR-enabled privacy enhancing technologies. Since 1995, much work has been done creating protocols for private information retrieval (PIR). Many variants of the basic PIR model have been proposed, including such modifications as computational vs. information-theoretic privacy protection, correctness in the face of servers that fail to respond or that respond incorrectly, and protection of sensitive data against the database servers themselves. In this paper, we improve on the robustness of PIR in a number of ways. First, we present a Byzantine-robust PIR protocol which provides information-theoretic privacy protection against coalitions of up to all but one of the responding servers, improving the previous result by a factor of 3. In addition, our protocol allows for more of the responding servers to return incorrect information while still enabling the user to compute the correct result. We then extend our protocol so that queries have information-theoretic protection if a limited number of servers collude, as before, but still retain computational protection if they all collude. We also extend the protocol to provide information-theoretic protection to the contents of the database against collusions of limited numbers of the database servers, at no additional communication cost or increase in the number of servers. All of our protocols retrieve a block of data with communication cost only O(lscr) times the size of the block, where lscr is the number of servers. Finally, we discuss our implementation of these protocols, and measure their performance in order to determine their practicality. Publicly accessible databases are an indispensable resource for retrieving up-to-date information. But they also pose a significant risk to the privacy of the user, since a curious database operator can follow the user's queries and infer what the user is after. Indeed, in cases where the users' intentions are to be kept secret, users are often cautious about accessing the database. It can be shown that when accessing a single database, to completely guarantee the privacy of the user, the whole database should be down-loaded; namely n bits should be communicated (where n is the number of bits in the database). In this work, we investigate whether by replicating the database, more efficient solutions to the private retrieval problem can be obtained. We describe schemes that enable a user to access k replicated copies of a database ( k ≥2) and privately retrieve information stored in the database. This means that each individual server (holding a replicated copy of the database) gets no information on the identity of the item retrieved by the user. Our schemes use the replication to gain substantial saving. In particular, we present a two-server scheme with communication complexity O(n 1 3 ).