Lossy functions do not amplify well
LNCS
Pietrzak, Krzysztof Z
Rosen, Alon
Segev, Gil
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.
Springer
2012
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/3281
Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol 7194. Springer; 2012:458-475. doi:<a href="https://doi.org/10.1007/978-3-642-28914-9_26">10.1007/978-3-642-28914-9_26</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-28914-9_26
info:eu-repo/semantics/closedAccess