^{0}by Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.

Don't let "NC^{0}" 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
NC^{0} and
so if one-way function and PRGs exist in the larger class than slightly
weaker versions exist in NC^{0} 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
NC^{0}." Now we know why.

## No comments:

## Post a Comment