On the security of Goldreich's one-way function
- Publication Type:
- Journal Article
- Citation:
- Computational Complexity, 2012, 21 (1), pp. 83 - 127
- Issue Date:
- 2012-03-01
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
2013005432OK.pdf | 449.88 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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. We also prove an amplification claim regarding Goldreich's construction. Suppose we are given an assignment x′ ∈ {0,1} n that has correlation ε > 0 with the hidden assignment x′ ∈ {0,1} n. Then, given access to x′, it is possible to invert f on x with high probability, provided D = D(d,ε) is sufficiently large. © 2012 Springer Basel AG.
Please use this identifier to cite or link to this item: