For Fall 2013, the usual time for the meetings will be Friday at 11:30 - 13:00 in the CS conference room, CSB 453. Abstracts for talks are given below the talk schedule.
Abstract: The problem of searching over encrypted data arises often and, most notably, in the design of secure database systems, file systems, cloud storage systems and in the design of cryptographic protocols. Many solutions to this problem have been proposed in the past, including searchable encryption, deterministic encryption, order preserving encryption, functional encryption, oblivious RAMs, secure two-party computation and fully-homomorphic encryption.
In this talk, I will survey the different solutions to the encrypted search problem and discuss their various strengths and limitations, paying particularly close attention to the tradeoffs made between security, efficiency and functionality. I will then present recent advances in the area of searchable encryption and give an overview of the state-of-the art constructions and implementations.
Abstract: In this talk we show several results regarding Boolean functions with small spectral norm (the spectral norm of f is [;\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|;]). Specifically, we prove the following results for functions [;f:\{0,1\}^n \to \{0,1\};] with [;\|\hat{f}\|_1=A;].
1. There is a subspace V of co-dimension at most [;A^2;] such that [;f|_V;] is constant.
2. f can be computed by a parity decision tree of size [;2^{A^2}n^{2A};]. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.)
3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth [;A^2 \log s;].
4. For every [;0<\epsilon;] there is a parity decision tree of depth [;O(A^2 + \log(1/\epsilon));] and size [;2^{O(A^2)} \cdot \min\{1/\epsilon^2,O(\log(1/\epsilon))^{2A}\};] that [;\epsilon;]-approximates f. Furthermore, this tree can be learned, with probability [;1-\delta;], using [;\poly(n,\exp(A^2),1/\epsilon,\log(1/\delta));] membership queries.
All the results above also hold (with a slight change in parameters) to functions [;f:Z_p^n\to \{0,1\};].
Joint work with Amir Shpilka and Avishay Tal
Abstract: In this talk I will describe nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In our theorems one assumes that a function F is "mildly hard" against nondeterministic circuits of some size s(n), and concludes that the t-fold direct product F^t is "extremely hard" against probabilistic circuits of only polynomially smaller size s'(n). The main advantage of these results compared with previous DPTs is the greatly improved size bound in our conclusion.
As an application, we show that if NP is not in coNP/poly then, for every PPT algorithm attempting to produce satisfying assignments to Boolean formulas, there are infinitely many satisfiable instances on which the algorithm's success probability is nearly-exponentially small. This furthers a project of Paturi and Pudlak [STOC'10].
Comments on this page are welcome; please send them to xichen-at-cs.columbia.edu