On the Security of Goldreich's One-Way Function
by Andrej Bogdanov and Youming Qiao.
Oded's comments
For a couple of reasons,
my original suggestion referred to the length preserving case,
where $m=n$, yet the generalization to $m=O(n)$ seems natural.
Interestingly, this work shows that this generalization
is problematic when the O-notation hides a sufficiently large constant
(i.e., a constant that is exponential in the constant degree $d$).
In this case, predicates that have non-zero correlation with
any single bit (or even any fixed pair of bits) yield a function
that is easy to invert on mosl inputs (for a random underlying graph).
My interpretation of this result is that $m >> n$ should not
be allowed (recall that $m > n^d$ is definitely bad).
The original abstract
Goldreich (ECCC 2000) suggested a simple construction of
a candidate one-way function $f: \B^n \to \B^m$ where each bit
of output is a fixed predicate $P$ of a constant number $d$ of (random)
input bits. We investigate the security of this
construction in the regime $m = Dn$, where $D=D(d)$
is a sufficiently large constant.
We prove that for any predicate $P$ that correlates with
either one or two of its variables, $f$ can be inverted
with high probability.
We also prove an amplification claim regarding Goldreich's construction.
Suppose we are given an assignment $x' \in \B^n$ that has correlation
$\epsilon > 0$ with the hidden assignment $x \in \B^n$.
Then, given access to $x'$, it is possible to invert $f$ on $x$,
with high probability, provided $D = D(d,\epsilon)$ is sufficiently large.
Back to
list of Oded's choices.