“You have to have good researchers. Good researchers, all of them.” – Paraphrase of quote from Das Boot.
Sometimes writing a paper can be a challenging slog: goals move as conjectures prove wrong; facts that seem simple turn out to be slippery to prove; experiments must be rerun as the paper evolves; and notation needs to be redone for the sake or readability.
In such a situation, it’s a blessing to have coauthors who will go the extra mile to keep pushing and pushing the paper to completion. So I would now really like to thank my students Jeffrey Knockel and George Saad for their hard work on our latest paper: “Self-Healing of Byzantine Faults” (abstract below, full paper here).
Note: I wouldn’t exactly compare the research process with serving on a U-boat mission during the decline of the Third Reich. For me it’s most similar to mountaineering, whose ethos is captured by the motto of the Seattle mountaineers: “Like fun, only different!”
Paper Abstract:
Recent years have seen significant interest in designing networks that are self-healing in the sense that they can automatically recover from adversarial attack. Previous work shows that it is possible for a network to automatically recover, even when an adversary repeatedly deletes nodes in the network. However, there have not yet been any algorithms that self-heal in the case where an adversary takes over nodes in the network. In this paper, we address this gap.
In particular, we describe a communication network over n nodes that ensures the following properties, even when an adversary controls up to 
Filed under: Uncategorized | Tags: algorithms, secure multiparty computation, security, theory
Attached is a paper on a problem we’ve been working on for a while: an efficient algorithm for Secure Multiparty Computation (SMPC) against a static adversary.
In the SMPC problem, n players each have a private input, and their goal is to compute the value of a n-ary function, f, over the inputs, without revealing any information about the inputs. The problem is complicated by the fact that a hidden subset of the players are controlled by an adversary that actively tries to subvert this goal.
SMPC abstracts several important problems in distributed security, and so, not surprisingly, there have been thousands of papers written
in the last several decades addressing it. However, there is a striking barrier that prevents wide-spread use: current algorithms to solve SMPC are not resource efficient. In particular, if there are n players involved in the computation and the function f can be computed by a circuit with m gates, then most algorithms require each player to send a number of messages and perform a number of computations that is
We describe scalable algorithms for SMPC against a static adversary. We assume a partially synchronous message passing communication model, but unlike most related work, we do not assume the existence of a broadcast channel. Our main result holds for the case where there are $n$ players, of which a 
Filed under: Uncategorized | Tags: distributed computing, secure multiparty computation, security, theory
In this post, I want to talk about a research problem that I think even our new Republican legislatures can get excited about: Yao’s millionaire problem. In this problem, two millionaires want to determine who is richer, but neither wants to reveal their private net worth. Can we develop a protocol to help these millionaires? This problem is important because it kicked off the the study of secure multiparty computation.
Below is a picture of the protocol originally proposed by Yao. Alice and Bob are the two millionaires and i and j are the private net worths of Alice and Bob respectively. The protocol makes use of public key cryptography: Alice is assumed to be able to generate a public encryption key E_a() along with a private decryption key D_a(). To see that the protocol reveals who is richer, note that y_j = D_a(k) = x. Thus w_j = x if j<= i and w_j = x+1 if j>i. Showing that the protocol doesn’t reveal any information beyond who is richer is more challenging and is presented in detail in the paper.
I should point out that this protocol takes exponential time and that this run time has been improved in subsequent papers. However, there is a question about this problem I haven’t been able to answer. In the case where there are n players, do we need private channels or cryptographic assumptions to solve the problem? Are private channels needed even if we’re happy with a Monte Carlo solution? I’ve seen several papers that remove cryptographic assumptions, but none that seem to remove the need for private channels. Conversely, I’ve seen no papers that prove that private channels are necessary…
Filed under: Uncategorized | Tags: distributed computing, game theory, PODC, security
Accepted papers for PODC 2011 are now up on the web here. There are many interesting papers – here are a few that immediately catch my eye:
- “Error-Free Multi-Valued Consensus with Byzantine Failures“ by Guanfeng Liang and Nitin Vaidya. This paper gives a deterministic algorithm for solving multi-valued consensus with Byzantine faults that has asymptotically optimal bandwidth when the number of bits in the input values are large. The cool thing about the paper is that it uses network coding and an interesting amortized analysis. Essentially there are multiple runs of a single bit consensus algorithm. The single bit consensus algorithm has lightweight checks and is 1) very efficient when the checks detect no malicious behavior; and 2) able to “kick out” a Byzantine processor whenever the checks do detect malicious behavior.
- “Xheal: Localized Self-Healing Using Expanders” by Amitabh Trehan and Gopal Pandurangan. Amitabh, my former PhD student, and periodic guest blogger on this blog, is now a postdoc at Technion working with Shay Kutten and Ron Lavi. This paper is still very secret as Amitabh won’t even send me a copy of the submitted version. However, we can guess that the paper describes an algorithm that ensures an overlay network 1) keeps paths between nodes short; and 2) keeps degrees of nodes small. That word “localized” is very tantalizing as it suggests that, unlike previous work, this new self-healing algorithm requires only local communication.
- “Adaptively Secure Broadcast, Revisted” by Juan Garay, Jonathan Katz, Ranjit Kumaresan and Hong-Sheng Zhou. Again this paper doesn’t seem to be up on the web and I didn’t get to read it as a member of the PC. However, the problem itself, described in the paper Adaptively Secure Broadcast by Martin Hirt and Vassilis Zikas, looks interesting: basically the goal is secure broadcast in a scenario where an adaptive adversary can corrupt up to a 1/3 fraction of the players, including the sender. The original paper by Hirt and Zikas shows that past results on the secure broadcast problem are not secure under composition, and they then present a new protocol that is secure under composition, along with a new simulation-basted security notion for the problem.
- “Fault-Tolerant Spanners: Better and Simpler” by Michael Dinitz and Robert Krauthgamer. This paper shows how to create spanners of general graphs that are tolerant to vertex failures. They give a transformation for k >= 3 that converts every k-spanner construction with at most f(n) edges into a k-spanner construction that can tolerate r faults and uses O(r^3 log n)*f(2n/r) edges. For the case k=2, they improve the approximation ratio from O(r log n) to O(log n). Bonus: This last result uses an LP relaxation and the Lovasz Local Lemma.
- There are several papers that did not make it as regular papers that I hope to see as brief announcements. Privacy concerns keep me from mentioning anything in particular here, but there were some nice lower bound results that were invited to be resubmitted as brief announcements. I hope the authors will accept.
Question: Are there no game theory papers this year except the two that we submitted? This seems surprising.
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.
Filed under: Uncategorized | Tags: distributed algorithms, security, theory
I enjoy collecting meta-level tricks for coming up with new research problems. Two tricks I know of are “zooming out” and “zooming in”. I think that “zooming out” is the more obvious trick: find several important problems that share some fundamental similarity and formulate a single abstract problem that allows for simultaneous progress in understanding all the particular problems. Many big problems in complexity theory are of this type.
The other technique, “zooming in” seems to be just as important, but to be used much less frequently, perhaps because it’s harder to determine when it should be applied. One of my most cited research results is on a problem that was devised using the “zooming in” technique: the problem of choosing a random peer in a large network. The story behind this paper is that we wanted to solve some hard problem on peer-to-peer networks, and one part of our solution required as a subroutine an algorithm to choose a peer uniformly at random in the network. Implementing this subroutine seemed like the easiest part of the problem and so we saved it to the end. But then when it came time to solve it, we became more and more annoyed by the difficultly of the problem. Finally we did a thorough literature search on this subproblem, which at first we thought would be the easiest part of the paper. Not only didn’t we find any correct solutions in the literature, but we actually found several incorrect solutions. At this point, we realized the problem was important and interesting in its own right, and we wrote an entire paper on just this one subproblem.
Today I wanted to highlight a recent nice example of the “zooming in” technique, in a ICDCS paper by my former student Maxwell Young. This paper, “Practical Robust Communication in DHTs Tolerating a Byzantine Adversary”, by Maxwell Young, Aniket Kate, Ian Goldberg and Martin Karsten, is a systems paper that presents a clever algorithm for efficient and robust communication in a distributed hash table (DHT). A DHT is basically a distributed data structure that allows for efficient storage and lookup of content based on keywords. The nice trick they use in this paper, is to formulate the research problem by “zooming in”. Instead of designing yet another DHT from scratch that is robust to adversarial control of nodes, they assume that part of the problem is already solved: there is already a DHT that has the property that each “supernode” contains a majority of peers that are not controlled by an adversary (there are any number of papers that show how this property can be maintained). They then focus only on the problem of routing most efficiently through such a DHT. To my knowledge, this is the first paper that focuses only on this important subproblem of robust communication in a DHT. And if you take a look at the paper, you’ll see that the results they achieve are much better than other algorithms that have been proposed, as asides and perhaps without too much thought, in other papers for this problem. While this paper focuses just on the empirical side of this problem, I think there are still many interesting open problems on the theoretical side.
Filed under: Uncategorized | Tags: funding, game theory, grants, security, theory
Dear blog, please forgive me for my neglect these many, long weeks!
About this time last year, I blogged about some tips that I found useful for writing NSF proposals. It turns out that the NSF proposal I submitted last year was funded! Let’s hope that things go as well again this year. I sometimes get requests for full proposals I’ve submitted that have been funded, and like many researchers, I’m a bit uncomfortable posting an entire proposal. However, this time, in the spirit of recommitting myself to interesting and reasonably frequent blogging, I’m going to post the one page project summary for my funded proposal, and I will post it right here. I hope that some readers will find it useful.
attacker-defender-games-summary
Filed under: Uncategorized | Tags: algorithms, game theory, security, theory
Imagine that Alice wants to send a message to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is periodically able to block this channel. Further, it costs Alice $a dollars each time she sends on the channel, Bob $b dollars each time he listens on the channel, and Carol $c dollars each time she blocks the channel. If Alice, Bob and Carol all play this game optimally, how much more will Carol need to spend than Alice and Bob in order to block the message?
This problem abstracts many types of conflict on information networks including: web censorship by nation-states, denial of service attacks on the Internet, and jamming attacks on wireless networks, where the costs to Alice, Bob and Carol can represent expenditure of both computational and human resources. The problem allows us to quantitatively ask: Does information really “want” to be free?
In a new result, Max Young, Valerie King and I answer this question in the affirmative by showing that under optimal play, it is significantly harder for Carol to block the message than for Alice to communicate it to Bob. Specifically, if a,b and c are fixed constants, and Carol spends $X dollars to try to block the message, then Alice and Bob need spend only proportional to $X^{phi – 1} or about $X^{.62} dollars to transmit the message, where phi = (1+ sqrt(5))/2 is the golden ratio. Surprisingly, this result holds even if Alice and Bob do not know the value X, and there are no cryptographic assumptions.
This is probably not surprising if you’ve been reading the last several posts on this blog, but I have an opening for a PhD student that I would like to fill soon. I’m circulating the following announcement about it.
I have one opening for a PhD student with a keen interest in CS theory research and a strong mathematical background to work on a game theoretic project in network security. The project entitled “Beyond Tit-for-Tat: New Techniques for Collaboration in Network Security Games” will focus on how to enable collaboration on the Internet, where populations are highly fluctuating, selfish, and unpredictable. This project will explore a new algorithmic technique for enabling collaboration in network security games which will improve on past approaches such as tit-for-tat in the following ways: (1) it works even in single round games; (2) it works even when the actions of the players of the game are never revealed; (3) it works even in the presence of churn, i.e. players joining and leaving the game.
The position will cover tuition and also pay a stipend of $1,780/month. The position can start in either spring or fall semester of 2011
New Mexico is a hot spot for research in complex systems and interdisciplinary research. The Computer Science department at the University of New Mexico benefits from strong ties with the Santa Fe Institute, and Sandia Labs and Los Alamos Labs. The theory group in our department is particularly strong, having graduated students in the past several years who have performed very well in a challenging job market. Permanent Positions secured by these students include: Asst. Prof. at University of Colorado, Boulder; researcher Sandia Labs; engineer at Microsoft. Post doc positions secured include: University of Waterloo, Technion and University of Victoria.
Interested? Please contact me about the position at: <my last name>@cs.unm.edu
Navin successfully defended his dissertation on July 8th and has recently had his final manuscript accepted. Below is the announcement for his defense, preserved for posterity 
Some of his research results have already been discussed in his previous guest blog posts.
Congratulations Navin!
PhD Dissertation Defense Presented by: Navin Rustagi
Title: Security in Network Games
Committee Chair:
Jared Saia, Associate Professor of Computer Science at UNM
Committee Members:
James Aspnes, Professor of Computer Science at Yale University
Josep Diaz, Universitat Politecnica de Catalunya
Tom Hayes, Assistant Professor of Computer Science at UNM
Abstract:
Attacks on the Internet are characterized by several alarming trends:
1) increases in frequency; 2) increases in speed; and 3) increases in
severity. Modern computer worms simply propagate too quickly for human
detection. Since attacks are now occurring at a speed which prevents
direct human intervention, there is a need to develop automated
defenses. Since the financial, social and political stakes are so
high, we need defenses which are provably good against a worst
case attacks and are not too costly to deploy. In this talk we
present two approaches to tackle these problems.
For the first part of the talk we consider a game between an alert and
a worm over a large network. We show, for this game,
that it is possible to design an algorithm for the alerts that can
prevent any worm from infecting more than a vanishingly small fraction of the
nodes with high probability. Critical to our result is designing
a communication network for spreading the alerts that has high
expansion. The expansion of the network is related to the gap between
the $1^{st}$ and $2^{nd}$ eigenvalues of the adjacency
matrix. Intuitively high expansion ensures redundant connectivity. We
also present results simulating our algorithm on networks of size up to
$2^{25}$.
In the second part of the talk we consider the virus inoculation game
which models the selfish behavior of the nodes involved. We present a technique for this game which makes it possible to achieve the “windfall of malice” even without
the actual presence of malicious players. We also show the limitations
of this technique for congestion games that are known to have a windfall of malice.
This dissertation includes research previously published in WINE and OPODIS.
