^January February – 2009 ^March

Jonathan Katz and Luca Trevisan defined the concept of Locally Decodable Codes (LDC). LDC are error correcting codes where a bit of the message can be probabilistically recovered by looking at a limited number of symbols of a corrupted encoding. After defining LDCs formally we will see some negative results. First, that local decoding is impossible when looking at only one symbol of the corrupted encoding. Then we will see a lower bound on the codewords' length.

This paper appeared in STOC00.

Verifiable random functions, introduced by Micali, Rabin and Vadhan, are a primitive aimed at coping with the absence of random oracles in the real world. While replacing the random oracle with a pseudorandom function can be a solution in some cases, its drawback is the function's seed owner's ability to adaptively change its answers and thus manipulate the protocol. In a verifiable random function, the seed owner produces a public-key at the beginning of the interaction, which constitutes a commitment to all (pseudorandom) values of the function. It can then produce, for any input, a proof that the output has been computed correctly (with respect to that public-key). Even a maliciously chosen public-key must not enable proving different outputs for the same input.

Verifiable random functions found various implementations and uses. However, no implementation based on a general assumption (such as the existence of one-way functions or even stronger assumptions like trapdoor permutations) is known.

We define a relaxation of verifiable random functions, which we call weak verifiable random functions, in the spirit of Naor and Reingold's weak pseudorandom functions. We show that this relaxed notion can be derived from various assumptions (including general assumptions); that the existence of weak verifiable random functions is essentially equivalent to the existence of non-interactive zero-knowledge proof systems for all of NP (in the common random string model); and prove that weak verifiable random functions (and thus also "standard" verifiable random functions) cannot be constructed from one-way permutations in a black-box manner, providing a first separation result for (standard) verifiable random functions from any cryptographic primitive.

No prior knowledge on black-box separations is assumed.

Joint work with Shafi Goldwasser, Guy Rothblum and Vinod Vaikuntanathan.

The Black-and-White Coloring (BWC) problem is defined as follows. Given an undirected graph $G$ and positive integers $b, w$, determine whether there exists a partial vertex-coloring of $G$ such that $b$ vertices are colored black and $w$ vertices white (with all other vertices left uncolored), such that no black vertex and white vertex are adjacent.

The BWC problem has been introduced in general, and proved to be $NP$-complete, by Hansen, Hertz and Quinodoz, who also gave an $O(n^3)$ algorithm for trees. In this talk we introduce another algorithm, whose running time is $O(n^2 lg ^3 n)$. We also present an improvement to our algorithm, which works for almost all labelled trees in time~$n^{1+o(1)}$.

If time permits, we will present an algorithm which solves the BWC problem for chordal graphs.