Filed under: Uncategorized | Tags: censorship, cryptography, distributed computing, theory
Recently my student Mahdi Zamani presented a paper, Towards Provably-Secure Scalable Anonymous Broadcast, at the FOCI ’13 (Free and Open Communication on the Internet). This is his report on the workshop – Jared
Last week, I attended the third USENIX workshop on Free and Open Communications on the Internet (FOCI’13) in Washington, DC. The workshop consisted of three main sessions for peer-reviewed full papers and a rump session for quick presentations. The first session focused on state-level censorship by discussing various methods used by several governments around the world to suppress freedom of speech. The second session was centered around methods for detection and prevention of censorship in the Internet. These include methods for monitoring censorship, analysis of captured data, and designing efficient infrastructures for censorship prevention. The third session focused on technical methods for anonymous communication, an important approach for protecting against surveillance and censorship. The main sessions were followed by a one-hour rump session aimed at briefly presenting new challenges and ongoing work in this area. In the following, I give a summary of a few interesting papers presented in the workshop.
In the first session, John Verkamp from Indiana University explained how Twitter spam was used by the governments of China, Syria, Russia, and Mexico during five political events from 2011 to 2012 to inhibit political speech. Such spams appear as a large numbers of tweets with similar hashtags, but contents irrelevant to the subject. Effectively, this renders a politically-charged hashtag useless. The paper gives several interesting patterns that can be used to easily distinguish spam tweets from innocent tweets. For example, spam tweets usually use fewer stop words than non-spam tweets. In Mexico, spammers used account names that all had exactly 15 characters. These findings seem extremely helpful for guiding defense mechanisms against political spam in social networks.
Mobin Javed from UC Berkeley presented a paper by Zubair Nabi from Pakistan, where access to the Internet is mostly controlled by the state and is censored in a centralized way at the Internet exchange level. This paper shows several techniques used by the Pakistani government since 2006 to filter Internet content including DNS lookup, IP blacklisting, HTTP filtering, and URL keyword filtering. An interesting thing about this research is that it is the first study of the cause, effect, and mechanism of web censorship in Pakistan.
In the second session, Philipp Winter from the Tor project and Karlstad University presented an analyzer tool that provides usage statistics in order to see how Tor is blocked in various countries and to possibly improve Tor access. One challenging problem in Tor analysis is to find a node (called shell) inside the censoring network to capture and debug Tor traces, while respecting user’s privacy. In their tool, the user is supposed to run the tool voluntarily. I think one issue with this tool is how to incentivize people to use it. The paper does not provide any cost analysis of the tool hence it is unclear how much bandwidth and computation power it needs. Another open question is whether a strong adversary could use information from the tool to attack anonymity.
Shaddi Hasan from UC Berkeley talked about an infrastructure for future censorship-resistant networks (called dissent networks). He motivated the need for such an infrastructure by giving examples of recent Internet blackouts in the Arab Spring in Egypt, Libya, and Syria. They suggest four essential requirements for dissent networks: resilience against disruption, meaningful scalability, innocuous components, and resistance to tracking. They finally argue that anonymity is a necessary property of dissent networks although it can be used by adversaries to send false messages, impersonate other users, or execute sybil attacks. The downsides of anonymity are mainly due to the lack of reputation or accountability.
As part of a technical session in the USENIX Security Symposium, Henry Corrigan-Gibbs from Yale University presented an anonymous messaging system called Verdict, which is built on top of their previous protocol Dissent. Both protocols are based on Dining Cryptographers networks (DC-Nets), which provide anonymity with resistance against traffic analysis attacks. DC-Nets suffer from poor scalability and vulnerability to jamming attacks. Dissent addresses the jamming problem of DC-Nets retroactively while Verdict solves the poor scalability and detects disruptions proactively. Unlike DC-Nets, Verdict is cryptographic in nature and assumes a client-server architecture, where at least one server is honest. Each client attaches non-interactive zero knowledge proofs to its ciphertext to prove correctness. In order to decrease the large bandwidth cost of such proofs, they do some optimizations to make them smaller. Also, the honest server defers the checking of proofs to after a disruption occurs. Although the paper reports several empirical results, it remains unclear how the protocol scales. Moreover, it is not clear from the empirical results how many bits are sent by each party for sending one anonymous message.
Anonymity is known to protect people from the Internet surveillance and censorship. But there is an argument: What if adversaries (e.g. terrorists) use anonymity to escape from legal surveillance that is done to ensure people’s safety? Fortunately, I had a chance during the rump session to talk about this topic. Roger Dingledine, who is a co-founder of the Tor project and William Allen Simpson, an independent network security professional were strong defenders of the availability of full anonymity, without exception. They both disagree with “traceable anonymity” that means anonymity protected by law (see this: http://www.nytimes.com/roomfordebate/2011/06/21/youre-mad-youre-on-youtube/the-virtues-of-anonymity) and generally anything that gives anyone or any authority (including judicial system) the power to control anonymity. Roger gave an example: suppose person A in Syria who is in danger of death because of his speech. Also, suppose person B in the US who is in danger of death because of a terrorist attack. Now, ask “Can Tor save or harm these persons?”. The answer is that it can definitely save person A’s life but it cannot directly harm person B’s life because terrorists have also many other ways to attack. This means that the benefits we get from freedom of speech is much more than the costs we pay for that. See this talk by Roger: http://www.youtube.com/watch?v=35l56KjTCb8
Filed under: Uncategorized | Tags: algorithms, cryptography, game theory, PODC, security, theory
Decisions for PODC 2011 (in San Jose) have just been mailed out this morning. In a later post, I’ll talk about some of the interesting accepted papers this year – there are many. For now I wanted to mention two of my own papers that were accepted and are now up on my web page.
Conflict on a Communication Channel. This is a paper that I had previously blogged about here. I’m still very excited about the idea of maintaining security invariants while spending asymptotically less than an adversary that is trying to break them. In this paper, we were able to do this for a few problems related to jamming in sensor networks and denial of service attacks. However, the application of this kind of game theoretic analysis to security problems is still wide open. Many interesting problems remain.
Scalable Mechanisms for Rational Secret Sharing. This is a paper that I had not previously talked about in this blog. The paper considers the problem of secret sharing when each player is rational. In particular, we assume that each player prefers to learn the secret over not learning it, but prefers to be the only player learning the secret over being one of many players learning it. Much interesting work has been done on this problem in the last few years, with the main goal being to design a mechanism that ensures that ensures that all players learn the secret (thereby maximizing social welfare). The new problem we focus on in this paper is designing mechanisms that both reveal the secret to all players and are scalable in the sense that they require each player to send just a constant number of messages in expectation. Secret sharing is a subroutine for many cryptographic protocols, so one motivation is to develop a scalable tool for problems like rational multiparty computation and implementation of a mediator.
My colleague at UNM, Cris Moore, just had his paper on post-quantum crypto slashdotted. The paper, written with Hang Dinh and Alexander Russel, shows that a particular type of cryptosystem (the McEliece cryptosystem) resists a particular class of quantum attacks (Quantum Fourier Sampling attacks). This looks like a nice paper, and maybe a good reason for me to learn more about quantum computation than Shor’s algorithm.
P.S. Belated congratulations also to my freshly minted PhD student Navin Rustagi (former guest-blogger here) who just accepted a post doc with Marek Kimmel at Rice. A funny story: I first misheard this name as Mark Kimmel, and after googling it (try it yourself) became worried that Navin had been spending too much time in Santa Fe lately…
Filed under: Uncategorized | Tags: algorithms, cryptography, election, leader election, security, theory, Uri Feige
“Whenever a man has cast a longing eye on offices, a rottenness begins in his conduct.” ~Thomas Jefferson
I want to continue my occasional series about consensus today by talking about leader election. Actually, it’s going to be the problem of “committee election”, or as it is referred to more fancily, universe reduction. The problem is basically this: you have a collection of n people, some hidden fraction of which are bad, and you want to elect a small committee of the people such that the fraction of bad people in the committee is not much more than the fraction of bad people in the general population. The problem is complicated by the fact that there is no trusted outside party that can be used to, e.g. count up all the votes. Instead, the problem needs to be solved just through direct communication among the players. We’ll assume everyone has synchronized clocks and, moreover, that there is a way to broadcast a message to everyone (i.e. a consensus algorithm).
We’ll be interested in the very challenging case where the bad guys are computationally unbounded, i.e. no cryptography! Why do we torture ourselves like this? Well there are a few reasons. First, the intellectual interest in determining exactly what is and is not possible with cryptographic assumptions. Second, the practical problem of maybe avoiding some of the computational overhead associated with cryptography e.g. setting up a PKI. Finally, the desire to avoid assumptions about the “hardness” of certain problems, assumptions that may in the end not wind up not being completely correct.
In FOCS 1999, Uri Feige proposed a very clever solution to the committee election problem in his paper “Non-cryptographic Selection Protocols”. I’m going to simplify the algorithm a bit to make it blog friendly. So here’s the setup: we have n people, a hidden fraction of whom are bad and we want to elect a committee of these people such that the fraction of bad people in the committee is not much more than the fraction of bad in the general population. Here’s the algorithm: we put everyone up on a ledge and we put a certain number of large bins under the ledge. Each person then must jump into a bin. We tell the good guys to choose their bins independently and uniformly at random. Then, once everyone has jumped (we give them a fixed amount of time to do so), we take the bin with the smallest number of people in it and select these people as the winners. The rest of the bins are carted off to the politician recycling center.
Why should this work? We have no control over what the bad guys do, and moreover we assume they are omniscient and can secretly collude. Thus, we can expect the bad guys to hem and haw standing on the ledge until all the good guys have jumped, and then carefully decide amongst themselves what bins to jump into in order to try to throw the election. Except it turns out that there’s really nothing much they can do. Assume there are x bins and n people and that t of those people are bad. Then the expected number of good people jumping in each bin is (n-t)/x. Moreover, if x is chosen carefully, we can show that with high probability, the number of good people in every bin is very closely concentrated around the expected value[1]. But then what is the worst the bad people can do? The chosen bin will certainly have no more than n/x people in it. Thus, the chosen bin will have a fraction of good people in it that is very close to the fraction of good people in the general population.
So that’s the idea. Cool no? Much of the technical challenge of Feige’s paper is showing how you can extend this idea to choose a single leader, so that this leader has probability of being bad no more than a fixed constant. The paper is a good read so I won’t reveal any of the details of how to do this. Also I want to point out that Feige’s algorithm is a critical tool in many of the modern consensus algorithms. But doesn’t his algorithm require a consensus algorithm in order to announce bin choices for each person? Yes, the trick is to use his algorithm among small groups where consensus is not that costly and then to create a kind of tournament network to eventually elect a very small representative group after running many election protocols in parallel.
[1] For example, let t = n/3 and x = n/(log n). Then Chernoff bounds and a union bound show that with probability that goes to 1 as n gets large, the number of good players in every bin is between (1-epsilon) and (1+epsilon) times (2/3)log n.
