Security and Privacy

Anonymous Information Dissemination

In recent years, various governments have shut down the Internet in their respective countries on numerous occasions. So under these very restrictive conditions, how can people communicate and spread information? Blackout circumvention introduces a number of interesting questions regarding networking, privacy, and security. For instance, how can people spread information without being held personally liable? How can network users privately access and consume this information? How can the information be spread throughout a population in the absence of standard communication infrastructure?

  • G. Fanti, Y. B. David, E. Brewer, and S. Shenker, “Rangzen: Circumventing Government-Imposed Communication Blackouts,” Technical Report UCB/EECS-2013-128, EECS Department, University of California, Berkeley.

Private Media Search

In a private media searches, a client possesses a query image or video file and wants to find similar objects in a database without the server learning anything about his query file. A block diagram of the problem is shown below:


Intuitively, this is like asking someone a question and getting a meaningful answer, despite asking the question in jibberish. This problem is challenging because most cryptographic privacy tools only allow exact computations, but media searches are often inexact (i.e., you might want to find similar results to your query, not identical results). To get around this, we need to either develop better and more efficient privacy tools or use existing tools in a more efficient fashion. This line of work is a necessary precursor to privacy-preserving surveillance.

  • G. Fanti, M. Finiasz, and K. Ramchandran, “One-Way Private Media Search on Public Databases: The Role of Signal Processing,” Signal Processing Magazine, IEEE, 30(2), 53-61. 2013.

Private Stream Search


Given a set of keywords, the aim of a stream search algorithm is to go through a stream of datadocuments and extract the datadocuments matching the keywords. Usually, the set of keywords is chosen by a user and the stream search is performed on a distant server hosting the data. Private Stream Search (PSS) simply consists in doing this privately, that is, without disclosing the keywords to the server.

Possible applications:

There are many applications to PSS and the most obvious one is privacy protection. Typically, when doing a web search on Google or Bing, a user might prefer not to disclose the keywords he is searching for to the search engine. You probably do not care if the search engine knows that you are a big fan of your local baseball team, but you will be more concerned if it knows all the patents people from your company have been searching for recently.

How can Private Stream Search be possible?

One very natural question that arises when talking about PSS is: “How can one search for keywords in a document without knowing which keywords he is looking for?” This is indeed impossible in general, but if one relaxes the privacy constraint a little, it becomes feasible. Instead of requiring that the server does not learn anything about the keywords, we assume that both the user and the server share a public dictionary of keywords: queries are limited to keywords in the dictionary, and the privacy constraint is that the server should not get any information about which keywords in the dictionary the user is searching for.


Using homomorphic encryption

In order to hide the user query, homomorphic encryption is used. Homomorphic encryption is a special form of encryption that allows basic operations to be performed on messages by manipulating only the associated ciphertexts. The query the user sends to the server is an encrypted bit for each element in the dictionary: if this keyword is part of the user query, the user sends an encryption of 1, if it is not, he sends an encryption of 0. As the query is encrypted, the server cannot tell which keywords the user is requesting, yet, thanks to the homomorphic property of the encryption, the server can perform some basic operations on the query. These basic operations are enough for it to compute encryptions of all the documents matching the query.

Security in Distributed Storage Systems

We address the problem of providing (information-theoretic) security in distributed storage systems that can guard against leakage of any information to an eavesdropper and also protect from any malicious acts of corrupting the data. More details on this topic can be found in these works:

  • K. V. Rashmi, Nihar B. Shah, Kannan Ramchandran, and P. Vijay Kumar, “Regenerating Codes for Errors and Erasures in Distributed Storage,” IEEE International Symposium on Information Theory (ISIT), Cambridge, Jul. 2012.

  • Nihar B. Shah, K. V. Rashmi, and P. Vijay Kumar, “Information-theoretically Secure Regenerating Codes for Distributed Storage,” Globecom 2011.