On the security of Goldreich's one-way function

Bogdanov, A; Qiao, Y

On the security of Goldreich's one-way function

Bogdanov, A Qiao, Y

Permalink

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	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Bogdanov, A	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2012-03-01	en_US
dc.identifier.citation	Computational Complexity, 2012, 21 (1), pp. 83 - 127	en_US
dc.identifier.issn	1016-3328	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28913
dc.description.abstract	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.	en_US
dc.relation.ispartof	Computational Complexity	en_US
dc.relation.isbasedon	10.1007/s00037-011-0034-0	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	On the security of Goldreich's one-way function	en_US
dc.type	Journal Article
utslib.citation.volume	1	en_US
utslib.citation.volume	21	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	1702 Cognitive Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access
pubs.issue	1	en_US
pubs.publication-status	Published	en_US
pubs.volume	21	en_US

Abstract:

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:

http://hdl.handle.net/10453/28913