Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On the Security of Goldreich’s One-Way Function
verfasst von : Andrej Bogdanov, Youming Qiao
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 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
′ ∈ {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.