IEEE FOCS 2010
TechTalks from event: IEEE FOCS 2010
51st Annual IEEE Symposium on Foundations of Computer Science

On the Queue Number of Planar Graphsallows us to settle a number of both old and recent open problemsWe prove that planar graphs have $O(log^4 n)$ queue number, thus improving upon the previous $O(sqrt n)$ upper bound. Consequently, planar graphs admit 3D straightline crossingfree grid drawings in $O(n log^c n)$ volume, for some constant $c$, thus improving upon the previous $O(n^{3/2})$ upper bound.

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSPValiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #Phard on general graphs but computable in polynomial time on planar graphs.
More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary realvalued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e.,polynomial time computable) on general graphs, or (2) those which are #Phard on general graphs but tractable on planar graphs, or (3) those which are #Phard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Nonnegative WeightsThe complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all nonnegative weighted form of the problem: Given any fixed matrix A with nonnegative entries, the partition function Z_A(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #Phard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

Overcoming the Hole In The Bucket: PublicKey Cryptography Resilient to Continual Memory LeakageIn recent years, there has been a major effort to design cryptographic schemes that remain secure even if part of the secret key is leaked. This is due to a recent proliferation of side channel attacks which, through various physical means, can recover part of the secret key. Micali and Reyzin (2004) suggested the intriguing possibility of achieving security even with continual leakage, i.e., even if some information is leaked each time the key is used. To achieve this impossiblesounding goal, theirs and several subsequent works all required the socalled ``only computation leaks information'' assumption, and it was unclear whether this strong assumption could be removed. We succeed in removing this assumption.
We show how to securely update a secret key while information is leaked, allowing some leakage {em even during the updates} themselves. Namely, we construct schemes that remain secure, even if an attacker {em at each time period}, can probe the {em entire} memory (containing a secret key) and ``leak out'' a $1/4epsilon$ fraction of the secret key . The attacker may also probe the memory {em during the updates}, and leak $O(log k)$ bits, where $k$ is the security parameter (relying on subexponential hardness, allows $k^epsilon$ bits of leakage during each update process).
Specifically, under the decisional linear assumption on bilinear groups, we achieve the above for public key encryption, identitybased encryption, and signature schemes. Prior to this work, it was not known how to construct encryption schemes even under the (stronger) assumption of Micali and Reyzin. One of our technical tools is a new linear algebraic theorem (which is unconditional, and requires no computational assumptions), stating that ``random subspaces are leakageresilient''.
The main contributions of this work are (1) showing how to securely update a secret key while information is leaked (without the aforementioned strong assumption) and (2) giving a public key {em enc

Cryptography Against Continuous Memory AttacksWe say that a cryptographic scheme is Continous LeakageResilient (CLR), if it allows users to refresh their secret keys, using only fresh local randomness, such that:
1. The scheme remains functional after any number of key refreshes, although the public key never changes. Thus, the ?outside world? is neither affected by these key refreshes, nor needs to know about their frequency.
2. The scheme remains secure even if the adversary can continuously leak arbitrary information about the current secretkey of the system, as long as the amount of leaked information is bounded in between any two successive key refreshes. There is no bound on the total amount of information that can be leaked during the lifetime of the system.
In this work, we construct a variety of practical CLR schemes, including CLR oneway relations, CLR signatures, CLR identification schemes, and CLR authenticated key agreement protocols. For each of the above, we give general constructions, and then show how to instantiate them efficiently using a well established assumption on bilinear groups, called the KLinear assumption (for any constant K >= 1).
Our constructions are highly modular, and we develop many interesting techniques and buildingblocks along the way, including: leakageindistinguishable rerandomizable relations, homomorphic NIZKs, and leakageofciphertext nonmalleable encryption schemes.
Prior to our work, no ?truly CLR? schemes were known, as previous leakageresilient schemes suffer from one or more of the following drawbacks: (a) restrictions are placed on the type of allowed leakage, such as the axiom that ?only computation leaks information?; (b) the overall amount of key leakage is bounded apriori for the lifetime of the system and there is no method for refreshing keys ; (c) the efficiency of the scheme degrades proportionally with the number of refreshes; (d) the key updates require an additional leakfree ?master secret key? to be stored securely; (e) the

On the Insecurity of Parallel Repetition for Leakage ResilienceA fundamental question in leakageresilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakageresilient primitive tolerating $ell$ bits of leakage, we can take $n$ copies of it to form a system tolerating $nell$ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most $ell$ bits are leaked, but $n$ copies of the system are insecure when $nell$ bits are leaked. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption emph{or} in prime order bilinear groups under the decisional linear assumption where the public key systems share a common reference parameter.

BlackBox, RoundEfficient Secure Computation via NonMalleability AssumptionWe present new and improved protocols for secure multiparty computation. Our main contributions are as follows:
 a O(log^* n)round protocol for secure multiparty computation with a dishonest majority that relies on blackbox access to dense cryptosystems, homomorphic encryption schemes, or lossy encryption schemes. This improves upon the recent O(1)^{log^* n}round protocol of Lin, Pass and Venkitasubramaniam (STOC 2009) that relies on non blackbox access to a smaller class of primitives.
 a O(1)round protocol requiring in addition, blackbox access to a oneway function with subexponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010).
These are the first blackbox constructions for secure computation with sublinear round complexity. Our constructions build on and improve upon the work of Lin and Pass (STOC 2009) on nonmalleability amplification, as well as that of Ishai et al. (STOC 2006) on blackbox secure computation.
In addition to the results on secure computation, we also obtain a simple, selfcontained construction of a O(log^* n)round nonmalleable commitment scheme based on oneway functions, improving upon the recent O(1)^{log^* n} round protocol of Lin and Pass (STOC 2009). Our construction uses a novel transformation for handling arbitrary maninthe middle scheduling strategies which improves upon a previous construction of Barak (FOCS 2002).

From Standard to Adaptive Hardness And Composable Security With No SetUpWe construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition{em assuming only the existence of enhanced trapdoor permutations.} The notion of security is a generalization of the ``angelbased'' notion of Prabhakaran and Sahai (STOC'04) and implies superpolynomial time simulation security.
A key element in our construction is a new notion of security for commitment schemes. The new notion, security against chosencommitmentattacks (CCA security), means that security holds even if the attacker has access to a {em decommitment oracle.} This notion is stronger than concurrent nonmalleability and is of independent interest. Our main technical contribution is constructing CCAsecure commitments based on standard oneway functions, and with no trusted setup. This provides a construction of a primitive whose emph{adaptive hardness} can be based on standard assumptions without setup.

On the Computational Complexity of Coin FlippingCoin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum~cite{Blum82}, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo~cite{Impagliazzo09talk}, surprisingly little is known about this question.
Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then oneway functions must exist~cite{ImpagliazzoLu89}. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant $epsilon>0$), the only complexitytheoretic implication that was known was that $PSPACE subseteq BPP$.
We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than $frac14  epsilon$ implies that $NP subseteq BPP$. Furthermore, for constantround protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) oneway functions.

Sequential Rationality in Cryptographic ProtocolsMuch of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationallybounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers.
We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threatfree Nash equilibrium that is more permissive but still eliminates the undesirable ``empty threats'' of nonsequential solution concepts.
To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibrium (DodisHaleviRabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a nontrivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.
 All Talks
 Geometric complexity theory (GCT)
 How to Grow Your Lower Bounds
 How To Think About Mechanism Design
 Constructive Algorithms for Discrepancy Minimization
 Bounded Independence Fools Degree2 Threshold Functions
 The Coin Problem, and Pseudorandomness for Branching Programs / Pseudorandom Generators for Regular Branching Programs
 Settling the Polynomial Learnability of Mixtures of Gaussians
 Polynomial Learning of Distribution Families
 Agnostically learning under permutation invariant distributions
 Learning Convex Concepts from Gaussian Distributions with PCA
 Determinant Sums for Undirected Hamiltonicity
 Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
 The Monotone Complexity of kCLIQUE on Random Graphs
 The Complexity of Distributions
 Hardness of Finding Independent Sets in Almost 3Colorable Graphs
 Approximation Algorithms for the EdgeDisjoint Paths Problem via Raecke Decompositions
 Computational Transition at the Uniqueness Threshold
 Avner Magen Memorial Talk
 Clustering with Spectral Norm and the kmeans Algorithm
 Stability yields a PTAS for kMedian and kMeans Clustering
 The Geometry of Manipulation  a Quantitative Proof of the GibbardSatterthwaite Theorem
 Efficient volume sampling for row/column subset selection
 Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
 New Constructive Aspects of the Lovasz Local Lemma
 The Geometry of Scheduling
 Sublinear Time Optimization for Machine Learning
 Estimating the longest increasing sequence in sublinear time
 Testing Properties of Sparse Images
 A Unified Framework for Testing LinearInvariant Properties
 Optimal Testing of ReedMuller Codes
 Subexponential Algorithms for Unique Games and Related problems
 Nevanlinna Prize Talk. Laplacian Gems
 Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
 MinimumCost Network Design with (Dis)economies of Scale
 One Tree Suffices: A Simultaneous O(1)Approximation for SingleSink BuyatBulk
 Min stCut Oracle for Planar Graphs with NearLinear Preprocessing Time
 Subcubic Equivalences Between Path, Matrix, and Triangle Problems
 Replacement Paths via Fast Matrix Multiplication
 AllPairs Shortest Paths in O(n2) Time With High Probability
 Approximating Maximum Weight Matching in Nearlinear Time
 Pure and BayesNash Price of Anarchy for Generalized Second Price Auction
 Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts / Frugal Mechanism Design via Spectral Techniques
 Budget Feasible Mechanisms
 BlackBox Randomized Reductions in Algorithmic Mechanism Design
 Boosting and Differential Privacy
 A Multiplicative Weights Mechanism for Interactive PrivacyPreserving Data Analysis
 Impossibility of Differentially Private Universally Optimal Mechanisms
 The Limits of TwoParty Differential Privacy
 Deciding firstorder properties for sparse graphs
 Logspace Versions of the Theorems of Bodlaender and Courcelle
 A separator theorem in minorclosed classes
 Optimal stochastic planarization
 Solving linear systems through nested dissection
 Approaching optimality for solving SDD linear systems
 Fast approximation algorithms for cutbased graph problems
 Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
 Vertex Sparsifiers and Abstract Rounding Algorithms
 A nonlinear lower bound for planar epsilonnets
 The subexponential upper bound for online chain partitioning
 Improved Bounds for Geometric Permutations
 On the Queue Number of Planar Graphs
 Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
 A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Nonnegative Weights
 Overcoming the Hole In The Bucket: PublicKey Cryptography Resilient to Continual Memory Leakage
 Cryptography Against Continuous Memory Attacks
 On the Insecurity of Parallel Repetition for Leakage Resilience
 BlackBox, RoundEfficient Secure Computation via NonMalleability Assumption
 From Standard to Adaptive Hardness And Composable Security With No SetUp
 On the Computational Complexity of Coin Flipping
 Sequential Rationality in Cryptographic Protocols
 A Fourieranalytic approach to ReedMuller decoding
 Pseudorandom generators for CC0[p] and the Fourier spectrum of lowdegree polynomials over finite fields
 Matching Vector Codes / Local list decoding with a constant number of queries
 Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
 A lower bound for dynamic approximate membership data structures
 Lower Bounds for Near Neighbor Search via Metric Expansion
 Distance Oracles Beyond the Thorup?Zwick Bound