FOCI Travel Report
August 21, 2013, 7:58 pm
Filed under: Uncategorized | Tags: , , ,

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: 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:

PODC 2011
March 7, 2011, 5:39 pm
Filed under: Uncategorized | Tags: , , , , ,

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.

Post Quantum Crypto
August 19, 2010, 4:02 pm
Filed under: Uncategorized | Tags: , ,

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…

Consensus (II) : Feige’s Leader Election Protocol
September 21, 2009, 6:36 pm
Filed under: Uncategorized | Tags: , , , , , ,

“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.


Consensus[1] is arguably one of the most fundamental problem in distributed computing.  The basic idea of the problem is: n players each vote on one of two choices, and the players  want to hold an election to decide which choice “wins”.  The problem is made more interesting by the fact that there is no leader, i.e. no single player who everyone knows is trustworthy and can be counted on to tabulate all the votes accurately.

Here’s a more precise statement of the problem.  Each of n players starts with either a 0 or a 1 as input.  A certain fraction of the players (say 1/3) are bad, and will collude to thwart the remaining good players.  Unfortunately, the good players have no idea who the bad players are.  Our goal is to create an algorithm for the good players that ensures that

  • All good players output the same bit in the end
  • The bit output by all good players is the same as the input bit of at least one good player

At first, the second condition may seem ridiculously easy to satisfy and completely useless.  In fact, it’s ridiculously hard to satisfy and extremely useful.  To show the problem is hard, consider a naive algorithm where all players send out their bits to each other and then each player outputs the bit that it received from the majority of other players.  This algorithm fails because the bad guys can send different messages to different people.  In particular, when the vote is close, the bad guys can make one good guy commit to the bit 0 and another good guy commit to the bit 1.

The next thing I want to talk about is how useful this problem is.   First, the problem is broadly useful in the engineering sense of helping us build tools.  If you can solve consensus, you can solve the problem of how to build a system that is more robust than any of its components.  Think about it: each component votes on the outcome of a computation and then with consensus it’s easy to determine which outcome is decided by a plurality of the components (e.g. first everyone sends out their votes, then everyone calculates the majority vote, then everyone solves the consensus problem to commit to a majority vote.)   It’s not surprising then that solutions to the consensus problem have been used in all kinds of systems ranging from flight control, to data bases, to peer-to-peer; Google uses consensus in the Chubby system; Microsoft uses consensus in Farsite; most structured peer-to-peer systems (e.g. Tapestry, Oceanstore) use consensus in some way or another.  Any distributed system built with any pretension towards robustness that is not using consensus probably should be.

But that’s just the engineering side of things.  Consensus is useful because it allows us to study synchronization in complex systems.  How can systems like birds, bees, bacteria, markets come to a decision even when there is no leader.  We know they do it, and that they do it robustly, but exactly how do they do it and what is the trade-off they pay between robustness and the time and communication costs of doing it?  Studying upper and lower bounds on the consensus problem gives insight into these natural systems.  The study of how these agreement building processes, or quorum sensing, occur in nature has become quite popular lately, since they occur so pervasively.

Consensus is also useful because it helps us study fundamental properties of computation.  One of the first major result on consensus due to Fischer, Lynch and Patterson, in 1982, was that consensus is impossible for any deterministic algorithm with even one bad player (in the asynchronous communication model).  However, a follow up paper by Ben-Or showed that with a randomized algorithm, it was possible to solve this problem even with a constant fraction of bad players, albeit in exponential time.  This was a fundamental result giving some idea of how useful randomization can be for computation under an adversarial model.  As a grad student, I remember taking a class with Paul Beame telling us how impressed he was by what these two results said about the power of randomness when they first came out.  Cryptography was also shown to be useful for circumventing the Fischer, Lynch and Patterson result, and I’ve heard of several prominent cryptographers  who were first drawn to that area at the time because of its usefulness in solving consensus.

In the next week or two, I’ll go into some of the details of recent results on this problem that make use of randomness and cryptography.  Early randomized algorithms for consensus like Ben-Or’s used very clever tricks, but no heavy duty mathematical machinery.  More recent results, which run in polynomial time, make use of more modern tricks like the probabilistic method, expanders, extractors, samplers and connections with error-correcting codes, along with assorted cryptographic tricks.  I’ve been involved on the work using randomness, so I’ll probably start there.

[1] The consensus problem is also frequently referred to as the Byzantine agreement problem or simply agreement.  I prefer the name consensus, since it is more succinct and descriptive. While the research community has not yet reached a “consensus” on a single name for this problem, in recent years, the name consensus is being used most frequently.