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.