[{
"publication_status" : "published",
"publist_id" : "3365",
"page" : "458 - 475",
"conference" : {
"name" : "TCC: Theory of Cryptography Conference",
"start_date" : "2012-03-19",
"end_date" : "2012-03-21",
"location" : "Taormina, Sicily, Italy"
},
"language" : [
{
"iso" : "eng"
}
],
"publisher" : "Springer",
"type" : "conference",
"main_file_link" : [
{
"url" : "http://www.iacr.org/archive/tcc2012/tcc2012-index.html"
}
],
"author" : [
{
"last_name" : "Pietrzak",
"full_name" : "Pietrzak, Krzysztof Z",
"id" : "3E04A7AA-F248-11E8-B48F-1D18A9856A87",
"first_name" : "Krzysztof Z"
},
{
"last_name" : "Rosen",
"full_name" : "Rosen, Alon",
"first_name" : "Alon"
},
{
"last_name" : "Segev",
"full_name" : "Segev, Gil",
"first_name" : "Gil"
}
],
"date_published" : "2012-05-04T00:00:00Z",
"status" : "public",
"year" : "2012",
"creator" : {
"id" : "3E5EF7F0-F248-11E8-B48F-1D18A9856A87",
"login" : "kschuh"
},
"intvolume" : " 7194",
"month" : "05",
"doi" : "10.1007/978-3-642-28914-9_26",
"department" : [
{
"_id" : "KrPi",
"tree" : [
{
"_id" : "ResearchGroups"
},
{
"_id" : "IST"
}
]
}
],
"abstract" : [
{
"lang" : "eng",
"text" : "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."
}
],
"user_id" : "3E5EF7F0-F248-11E8-B48F-1D18A9856A87",
"_version" : 13,
"acknowledgement" : "We would like to thank Oded Goldreich and Omer Rein- gold for discussions at an early stage of this project, and Scott Aaronson for clarifications regarding the collision problem.\r\n",
"citation" : {
"chicago" : "Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not Amplify Well,” 7194:458–75. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_26.",
"mla" : "Pietrzak, Krzysztof Z., et al. *Lossy Functions Do Not Amplify Well*. Vol. 7194, Springer, 2012, pp. 458–75, doi:10.1007/978-3-642-28914-9_26.",
"ista" : "Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well. TCC: Theory of Cryptography Conference, LNCS, vol. 7194. 458–475.",
"apa" : "Pietrzak, K. Z., Rosen, A., & Segev, G. (2012). Lossy functions do not amplify well (Vol. 7194, pp. 458–475). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_26",
"ieee" : "K. Z. Pietrzak, A. Rosen, and G. Segev, “Lossy functions do not amplify well,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 458–475.",
"short" : "K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.",
"ama" : "Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol 7194. Springer; 2012:458-475. doi:10.1007/978-3-642-28914-9_26"
},
"date_created" : "2018-12-11T12:02:26Z",
"oa_version" : "None",
"volume" : 7194,
"title" : "Lossy functions do not amplify well",
"_id" : "3281",
"alternative_title" : [
"LNCS"
],
"quality_controlled" : "1",
"day" : "04",
"date_updated" : "2019-08-02T12:38:08Z"
}]