---
res:
bibo_abstract:
- '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(logn)/n additive term. We show that this is tight by giving a simple
construction (cascading with some randomization) that achieves such amplification.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Alon
foaf_name: Rosen, Alon
foaf_surname: Rosen
- foaf_Person:
foaf_givenName: Gil
foaf_name: Segev, Gil
foaf_surname: Segev
bibo_doi: 10.1007/978-3-642-28914-9_26
bibo_volume: 7194
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Lossy functions do not amplify well@
...