zbMATH — the first resource for mathematics

On the security of Goldreich’s one-way function. (English) Zbl 1255.94053
Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 392-405 (2009).
Summary: O. Goldreich [Lect. Notes Comput. Sci. 6650, 76–87 (2011; Zbl 1306.94056)] suggested a simple construction of a candidate one-way function \(f:\{0,1\}^n \to \{0,1\}^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)\) 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\{0,1\}^n\) that has correlation \(\varepsilon > 0\) with the hidden assignment \(x\in\{0,1\}^n\). Then, given access to \(x^{\prime}\), it is possible to invert \(f\) on \(x\) with high probability, provided \(D=D(d, \varepsilon)\) is sufficiently large.
For the entire collection see [Zbl 1173.68008].

94A60 Cryptography
Full Text: DOI