Sunday, August 29, 2004

Computationally Simple One-Way Functions

An upcoming FOCS paper is drawing a lot of interest at TTI and Chicago, Cryptography in NC0 by Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.

Don't let "NC0" scare you, it simply means that every output bit depends on a constant number of input bits. In this paper the authors show that under reasonable assumptions one can have one-way functions and pseudo-random generators where each output bit depends on only four input bits. Quite surprising that such simple functions can be so hard to invert.

Their proof uses a clever but not overly complicated reduction using randomized polynomials from a larger class (⊕L/poly) to NC0 and so if one-way function and PRGs exist in the larger class than slightly weaker versions exist in NC0 respectively. The larger class contains many functions conjectured to be one-way or a PRG, including those based on factoring.

I remember Mike Sipser mentioning in a complexity class I took back in the mid-80's that "We don't even know how to show there are no one-way functions in NC0." Now we know why.

No comments:

Post a Comment