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.
