On the security of Goldreich's one-way function

Publisher:
Springer
Publication Type:
Journal Article
Citation:
Computational Complexity, 2012, 21 (1), pp. 83 - 127
Issue Date:
2012-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005432OK.pdf449.88 kB
Adobe PDF
Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1} n ? {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 inputs, f can be inverted with high probability.
Please use this identifier to cite or link to this item: