For Spring 2010, the usual time for the meetings will be Mondays at 11:00-12:00 in the CS conference room, CSB 453. Abstracts for talks are given below the talk schedule.

Tsvi Kopelowitz

Bar-Ilan University

**Abstract:**
Suffix trees and suffix arrays are two of the most widely used
data structures for text indexing. Each uses linear space and can
be constructed in linear time (under some reasonable constraints).
However, when it comes to answering queries, the prior does so in
$O(m\log|\Sigma| +occ)$ time, where $m$ is the query size,
$|\Sigma|$ is the alphabet size and $occ$ is the size of the
output, and the latter does so in $O(m+\log n+occ)$, where $n$ is
the text size.
We propose a novel way of combining the two into, what we call, a
suffix tray. The space and construction time remain linear
and the query time improves to $O(m+\log|\Sigma|+occ)$. Furthermore,
the query time can be maintained through online updates to the text.

The talk will not assume prior knowlege in these structures.

This is joint work with Richard Cole and Moshe Lewenstein.

Ilias Diakonikolas

Columbia University

**Abstract:**
In multi-objective optimization, solutions to an optimization problem
are evaluated
with respect to several cost criteria, and we are interested in a
class of solutions
that capture the trade-off between these objectives, the so-called
Pareto curve.
The problem is that the Pareto curve has typically exponential size
and hence we
cannot efficiently construct the full curve. Instead, we want to
compute efficiently
a small set of solutions (as small as possible) that provides a "good
enough"
representation (as good as possible) of the whole design space.

In recent years we initiated a systematic investigation to develop
the theory of
multi-objective approximation along similar rigorous lines as the
__approximation__ of
single objective problems. We address the problem of efficiently
computing
a __succinct__ approximation to the Pareto curve using as few solutions
as possible. If we are to select only a certain number of solutions, how shall we
pick them so that
they represent as accurately as possible the whole spectrum of
possibilities?

The talk will survey joint works with Mihalis Yannakakis.

David Xiao

Universite Paris-Sud

**Abstract:**
Collision-finding is a fundamental task in cryptanalysis,
and understanding the power of collision finders affords us insights
into building hash functions that are resistant to these attacks.
Simon (EUROCRYPT '98) studied the following "canonical collision
finder": given a shrinking function h, sample a random x, and then
sample a random x' satisfying h(x) = h(x'). This was then
generalized to a recursive collision-finder "Sam_d" by Haitner et al. (FOCS 2007), where d denotes the maximum recursion depth allowed.
Simon and Haitner et al. showed that in a relativized world with
random oracles, neither Simon's oracle nor Sam_d for d = o(n / log n)
permits one to invert the random oracle, which one may interpret as
saying that collision finding is weaker than inverting.

In this work, we study the power of these collision finders in the standard setting, i.e. *without* random oracles. We will give evidence that even in the standard setting, collision finding is not too powerful. More formally, let BPP^{Sam_d[k]} denote the class of languages that are decidable by a randomized k-adaptive oracle algorithm with access to a depth-d Sam oracle. We show that if d = O(1) and k = O(1), then BPP^{Sam_d[k]} is contained in AM intersect coAM. We also derive weaker though non-trivial conclusions for larger values of k.

We will also discuss two applications of our result: the first says that it is implausible to base collision-resistant hash functions (or even O(1)-round statistically hiding commitments) on NP-hardness. In a second application with Gordon et al., we show it is implausible to construct constant-round (possibly private-coin) ZK proofs from one-way permutations.

This is joint work Iftach Haitner and Mohammad Mahmoody.

Shai Halevi

IBM TJ Watson

**Abstract:**
We construct a simple fully homomorphic encryption scheme, using only
elementary modular arithmetic. We use Gentry's technique to construct
fully homomorphic scheme from a "bootstrappable" somewhat homomorphic
scheme. However, instead of using ideal lattices over a polynomial ring,
our bootstrappable encryption scheme merely uses addition and
multiplication over the integers. The main appeal of our scheme is the
conceptual simplicity.

We reduce the security of our scheme to finding an approximate integer gcd -- i.e., given a list of integers that are near-multiples of a hidden integer, output that hidden integer. We investigate the hardness of this task, building on earlier work of Howgrave-Graham.

Joint work with Marten van Dijk, Craig Gentry, and Vinod Vaikuntanathan

Zvi Galil

Columbia University / Tel Aviv University

**Abstract:**
The classical string matching problem is about finding all occurrences of
a pattern P in a text T, which are strings of length m and n, respectively.
A number of algorithms have been published including algorithms that work
in real time (i.e. constant time per symbol), with constant additional space
and without random access, and even on a finite automaton with one head
reading T and 5 heads reading P.

In the streaming model neither the pattern nor parts of the text are stored and only small amount of space is available. Simple information theoretical arguments imply that no deterministic algorithm is possible in the streaming model and one can only hope for a randomized algorithm which makes errors with small probability. The algorithms mentioned above are not streaming since they store the pattern.

In the last FOCS conference, Porat and Porat described a surprising result: a streaming randomized O(n log m) algorithm that uses O(log m) space. Each space unit is an O(log n) register. The pattern is first preprocessed and certain information of size O(log m) is computed. Porat and Porat do not give a streaming algorithm for the preprocessing and it is not clear if such an algorithm is possible for their preprocessing. In addition their randomized algorithm may have two sided errors with small probability; in particular, it may miss occurrences of the pattern.

We design two algorithms for the problem. The first one, like Porat and Porat, is an O(n log m) time streaming randomized algorithms using O(log m) space. The preprocessing of our algorithm is a trivial real-time streaming algorithm. Our algorithm allows with small probability only one sided (false positive) errors, which are unavoidable. In particular, it never misses any occurrence. We then modify the first algorithm and obtain a real-time O(log m) space streaming algorithm that uses the same trivial preprocessing and allows only one sided errors.

Porat and Porat used their algorithm as a black box to obtain streaming algorithms for the 1-mismatch and k-mismatch string matching problem. Using our algorithm we shave an O(log m) factor (an order of magnitude) from their time bounds.

The talk is self contained.

Joint work with Danny Breslauer

Vahab Mirrokni

**Abstract:**
In this talk, we survey recent results about the convergence time of
game dynamics, and describe two specific results in matching markets and potential games.

For uncoordinated two-sided matching markets, we show that best-response dynamics of players may cycle, but any random dynamics will converge to a stable matching with probability 1, and the expected time for this random convergence might be exponential.

For a general class of (exact) potential games (including congestion games and selfish routing games), we show that approximate Nash dynamics will converge to approximately optimal solutions in terms of a social welfare in polynomial time. This is in contrast to exponential-time convergence ofapproximately Nash dynamics to approximate equilibria, and exponential-time convergence of Nash dynamics to approximately optimal solution.

Jonathan Gross

Columbia University

Dov Gordon

University of Maryland

**Abstract:**
In the problem of secure two-party computation, two distrusting players
interact to compute a function of their private inputs. General
solutions to this problem have been known since the 80's, and they guarantee
every security property we might desire, with the single exception of
\emph{fairness}. Fairness in secure computation is a guarantee that if one
player receives output, then both players receive output. This is an
important security property for many applications, such as purchasing
electronic goods, exchanging signatures on a contract, and others.
Unfortunately, it was proven by Cleve in 1986 that without simultaneous
message exchange (e.g. when communicating over the Internet), we cannot even
guarantee fairness in computing boolean XOR.

In this talk we cover two results relating to fairness in secure computation. Although fair coin flipping is impossible, we describe the first fair protocols for other functions of interest (STOC 2008). We also describe a new relaxation allowing "partial" fairness that will appear this year at Eurocrypt 2010.

Xi Chen

University of Southern California

**Abstract:**
In the past decade, models and approaches from Game Theory and Economics
have been widely applied in the study of large-scale competitive
environments such as the Internet and e-commerce. The concept of
equilibria, i.e., that of stable states, serves as one of the key tools in
such studies, and its computation has attracted great attention. In this
talk, we will focus on the problem of computing equilibria in two of the
most fundamental models of competitions in Game Theory and Economics:
games and markets.

Both problems have a long intellectual history. In 1950, Nash showed that every game has an equilibrium. In 1954, Arrow and Debreu showed that under very mild conditions, every market has an equilibrium. While games and Nash equilibria are used to predict the behavior of selfish agents in conflicting situations, the study of markets and market equilibria laid down the foundation of competitive pricing. Other than the fact that both existence proofs heavily rely on fixed point theorems, the two models look very different from each other.

In this talk, we will review the recent characterizations of how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show that these results also significantly advanced our understanding about equilibria in the market setting.

No prior knowledge of Game Theory will be assumed for this talk.

Muthuramakrishnan Venkitasubramaniam

Cornell University

**Abstract:**
Cryptographic protocols have been developed for a variety
of tasks, including electronic auctions,
electronic voting systems, privacy preserving data mining and more.
The Internet allows for the concurrent
execution of cryptographic protocols. Such concurrency severely
challenges their security.

In this talk, I will introduce a unified framework for implementing cryptographic tasks that are secure under concurrent executions. Essentially all results on concurrently secure protocols are obtained as special cases of our framework. This not only leads to conceptually simpler and more efficient solutions, but also allows us to minimize the reliance on trusted infrastructure and simplify complexity assumptions.

Joint work with Huijia (Rachel) Lin and Rafael Pass.

Yevgeniy Vahlis

University of Toronto

**Abstract:**
Recent trends in computing increasingly rely on delegating
computation both to centralized cloud computing environments, and to
mobile computers such as smart cards and mobile phones. This creates
new security risks and consequently new challenges for cryptography.

One such challenge stems from the fact that physical computational devices leak information to the outside world through a variety of side-channels-- physical characteristics of the device such as power consumption, electromagnetic radiation, and timing. An attacker that has physical possession of the device, or is within a short distance, may use this information to learn about the internal state of the device and about the computation that is currently being performed. Such side-channel attacks have often been shown to break the security of widely used cryptographic schemes without violating any of the mathematical assumptions that underly the security of the scheme.

In this talk I will present a general compiler that immunizes any cryptographic functionality against long-term leakage through side-channels. Our construction uses a single leak-free hardware component and any fully homomorphic encryption scheme with randomizable ciphertexts. The hardware component samples from a publicly known distribution which does not depend on the functionality that we wish to protect or its internal state. We prove the security of our construction against an adversary that obtains leakage each time the cryptographic functionality is used. The information leaked can be any suitably length-bounded polynomial time computable function of the active part of memory during computation. The total amount of leakage that the construction can withstand is unbounded.

Our construction constitutes a first feasibility result, showing that resilience against polynomial time leakage is possible without performing any leak-free computation on the state of the protected primitive. However, many directions remain open. I will describe several such directions, and mention recent progress.

Joint work with Ali Juma and Charles Rackoff.

Guy Rothblum

Institute for Advanced Study

**Abstract:**
Boosting is a general method for improving the accuracy of learning
algorithms. We use boosting to construct privacy-preserving synopses
of an input database. These are data structures that yield, for a
given set Q of queries over an input database, reasonably accurate
estimates of the responses to every query in Q.

We provide an (inefficient) base synopsis generator for sets of arbitrary low-sensitivity queries (queries whose answers do not vary much under the addition or deletion of a single row). This yields the first privacy-preserving synopsis generator for arbitrary low-sensitivity queries.

This result is enabled by a new ``boosting for queries'' algorithm. Given a base synopsis generator that takes a distribution on Q and produces a ``weak'' synopsis that yields ``good'' answers for a majority of the weight in Q, our Boosting for Queries algorithm obtains a synopsis that is good for *all of* Q. We ensure privacy for the rows of the database, but the boosting is performed on the queries.

Joint work with Cynthia Dwork and Salil Vadhan.

Mohammad Mahmoody

Princeton University

**Abstract:**
Motivated by the question of basing cryptographic protocols on
stateless tamper-proof hardware tokens, we revisit the question of
unconditional two-prover zero-knowledge proofs for NP. We show that
such protocols exist in the {\em interactive PCP} model of Kalai and
Raz (ICALP '08), where one of the provers is replaced by a PCP
oracle. This strengthens the feasibility result of Ben-Or,
Goldwasser, Kilian, and Wigderson (STOC '88) which requires two
stateful provers. In contrast to previous zero-knowledge PCPs of
Kilian, Petrank, and
Tardos (STOC '97), in our protocol both the prover and the PCP oracle
are efficient given an $NP$ witness.

Our main technical tool is a new primitive that we call interactive locking, an efficient realization of an unconditionally secure commitment scheme in the interactive PCP model. We implement interactive locking by adapting previous constructions of interactive hashing protocols to our setting, and also provide a direct construction which uses a minimal amount of interaction and improves over our interactive hashing based constructions.

Finally, we apply the above results towards showing the feasibility of basing unconditional cryptography on stateless tamper-proof hardware tokens, and obtain the following results: (1) We show that if tokens can be used to encapsulate other tokens, then there exist unconditional and statistically secure (in fact, UC secure) protocols for general secure computation. (2) Even if token encapsulation is not possible, there are unconditional and statistically secure commitment protocols and zero-knowledge proofs for NP. (3) Finally, if token encapsulation is not possible, then no protocol can realize statistically secure oblivious transfer.

Contact

There is a mailing list for the reading group. General information about the mailing list (including how to subscribe yourself to it) is available here. If you want to unsubscribe or change your options, send email to theoryread-request@lists.cs.columbia.edu with the word `help' in the subject or body (don't include the quotes), and you will get back a message with instructions.

Comments on this page are welcome; please send them to
` rocco-at-cs.columbia.edu
`

Last updated 1/19/2010.