## Columbia Theory Seminar, Spring 2010

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.

• Monday January 25, 11am, CS Conference Room: Tsvi Kopelowitz: Suffix Trays and Suffix Trists - Structures for Faster Text Indexing (Abstract)

• Thursday, February 11, 3pm, CSB 477 (note unusual date, time and place): Conference Room: Ilias Diakonikolas: Approximating Multiobjective Optimization Problems (Abstract)

• Wednesday, February 17, 4pm, CS Open Area: (note unusual date, time and place) David Xiao: Finding collisions on a Hamiltonian Cycle (Abstract)

• Mon, February 22, 11am, CS Conference Room: Shai Halevi: Fully Homomorphic Encryption over the Integers (Abstract)

• Monday, March 1, 11am, Davis Auditorium (note unusual place): Special CS Department / CS Theory Seminar: Zvi Galil: Real-Time Streaming String-Matching (Abstract)

• Thursday, March 11, CUNY graduate center: New York Area Cryptography Day

• Mon, March 22, 11am, CS Conference Room: Vahab Mirrokni: Two Results in Game Dynamics: Matching Markets and Potential Games (Abstract)

• Monday, March 29, 11am, CS Conference Room: Jonathan Gross: A Celtic Framework for Knots and Links (Abstract)

• Thursday, April 8, 3pm, CS Conference Room: Dov Gordon: Fairness in Secure Computation (Abstract)

• Monday, April 12, 11am, Interschool Lab: Xi Chen: On the Computational of Equilibria (Abstract)

• Tuesday, April 20, NYU Courant Institute Room 1302: New York Area Cryptography Day

• Friday, April 23, 10am, CS Open Area (note unusual date, time and place) Muthuramakrishnan Venkitasubramaniam: A Unified Framework for Concurrent Security (Abstract)

• Monday, April 26, 11am, CS Conference Room: Yevgeniy Vahlis: Cryptography in The Presence of Continuous Side-Channel Attacks (Abstract)

• Wednesday, April 28, 2:15pm, CS Open Area (note unusual date, time and place): Guy Rothblum: Boosting and Differential Privacy (Abstract)

• Monday, May 3, 11am, CS Conference Room: Mohammad Mahmoody: Interactive Locking, Zero-Knowledge PCPs and Unconditional Cryptography (Abstract)

• Friday, May 7, Davis Auditorium, Columbia University:

# The IBM Research|NYU|Columbia Theory Day

### Talk Abstracts

Monday, January 25:
Suffix Trays and Suffix Trists - Structures for Faster Text Indexing
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.

Monday, February 8:
Approximating Multiobjective Optimization Problems
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.

Wednesday, February 17:
Finding collisions on a Hamiltonian Cycle
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.

Monday, February 22:
Fully Homomorphic Encryption over the Integers
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

Monday, March 1:
Real-Time Streaming String-Matching
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

Monday, March 22:
Two Results in Game Dynamics: Matching Markets and Potential Games
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.

Monday, March 29:
A Celtic Framework for Knots and Links
Jonathan Gross
Columbia University

Thursday, April 8:
Fairness in Secure Computation
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.

Monday, April 12:
On the Computation of Equilibria
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.

Friday, April 23:
A Unified Framework for Concurrent Security
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.

Monday, April 26:
Cryptography in The Presence of Continuous Side-Channel Attacks
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.

Wednesday, April 28:
Boosting and Differential Privacy
Guy Rothblum

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.

Monday, May 3:
TBA
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 rocco-at-cs-dot-columbia-dot-edu if you want to volunteer to give a talk (especially for students!). The talk can be about your or others' work. It can be anything from a polished presentation of a completed result, to an informal black-board presentation of an interesting topic where you are stuck on some open problem. It should be accessible to a general theory audience. I will be happy to help students choose papers to talk about.
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.