Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Lossy Functions Do Not Amplify Well
verfasst von : Krzysztof Pietrzak, Alon Rosen, Gil Segev
Erschienen in: Theory of Cryptography
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
We consider the problem of amplifying the “lossiness” of functions. We say that an oracle circuit
C
*
: {0,1}
m
→ {0,1}
*
amplifies relative lossiness from ℓ/
n
to
L
/
m
if for every function
f
:{0,1}
n
→ {0,1}
n
it holds that
1
If
f
is injective then so is
C
f
.
2
If
f
has image size of at most 2
n
− ℓ
, then
C
f
has image size at most 2
m
−
L
.
The question is whether such
C
*
exists for
L
/
m
≫ ℓ/
n
. This problem arises naturally in the context of cryptographic “lossy functions,” where the relative lossiness is the key parameter.
We show that for every circuit
C
*
that makes at most
t
queries to
f
, the relative lossiness of
C
f
is at most
L
/
m
≤ ℓ/
n
+
O
(log
t
)/
n
. In particular, no black-box method making a polynomial
t
=
poly
(
n
) number of queries can amplify relative lossiness by more than an
O
(log
n
)/
n
additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification.