^March April – 2006 ^May

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security. Joint work with Eyal Kushilevitz and Tal Rabin.

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results:

1. We prove an exponential lower bound on the length of linear LDC with 2 queries over arbitrary fields (previously it was known only for fields of size smaller than $2^n$)
2. We show that from every depth 3 arithmetic circuit C, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct an LDC with 2 queries.
3. We prove a structural theorem for depth 3 arithmetic circuits, with a bounded top fan-in, that compute the zero polynomial.
4. We give new PIT algorithms for depth 3 arithmetic circuits with a bounded top fan-in.

Joint work with Zeev Dvir from the Weizmann Institute

A short bio:
I finished my B.Sc. in the Hebrew university in 1996. I finished my Ph.D. also at the Hebrew university in 2001. I was a post-doc at Weizmann from 2001-2 and from 2003-5. I was a post-doc in Harvard and MIT in 2002-3. As of October I am a faculty member in the Technion.