{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:40:28Z","timestamp":1761975628808,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642383472"},{"type":"electronic","value":"9783642383489"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38348-9_29","type":"book-chapter","created":{"date-parts":[[2013,5,9]],"date-time":"2013-05-09T00:46:38Z","timestamp":1368060398000},"page":"486-502","source":"Crossref","is-referenced-by-count":2,"title":["Locally Computable UOWHF with Linear Shrinkage"],"prefix":"10.1007","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]},{"given":"Yoni","family":"Moses","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. In: STOC: ACM Symposium on Theory of Computing (STOC) (2006)","DOI":"10.1145\/1132516.1132537"},{"issue":"1-3","key":"29_CR2","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10817-005-9006-x","volume":"35","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satis_able formulas. J. Autom. Reasoning\u00a035(1-3), 51\u201372 (2005)","journal-title":"J. Autom. Reasoning"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. In: STOC, pp. 805\u2013816 (2012)","DOI":"10.1145\/2213977.2214050"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1007\/978-3-642-28914-9_34","volume-title":"Theory of Cryptography","author":"B. Applebaum","year":"2012","unstructured":"Applebaum, B., Bogdanov, A., Rosen, A.: A dichotomy for local small-bias generators. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 600\u2013617. Springer, Heidelberg (2012)"},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00037-006-0211-8","volume":"15","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Journal of Computational Complexity\u00a015(2), 115\u2013162 (2006)","journal-title":"Journal of Computational Complexity"},{"issue":"4","key":"29_CR6","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM Journal on Computing\u00a036(4), 845\u2013888 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"29_CR7","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00145-009-9039-0","volume":"22","author":"B. Applebaum","year":"2009","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. Journal of Cryptology\u00a022(4), 429\u2013469 (2009)","journal-title":"Journal of Cryptology"},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1007\/BFb0052256","volume-title":"Advances in Cryptology - CRYPTO \u201997","author":"M. Bellare","year":"1997","unstructured":"Bellare, M., Rogaway, P.: Collision-resistant hashing: Towards making UOWHFs practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol.\u00a01294, pp. 470\u2013484. Springer, Heidelberg (1997)"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Qiao, Y.: On the security of goldreich\u2019s one-way function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 392\u2013405. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_30"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-19571-6_1","volume-title":"Theory of Cryptography","author":"A. Bogdanov","year":"2011","unstructured":"Bogdanov, A., Rosen, A.: Input locality and hardness amplification. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 1\u201318. Springer, Heidelberg (2011)"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-540-74143-5_15","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"R. Canetti","year":"2007","unstructured":"Canetti, R., Rivest, R., Sudan, M., Trevisan, L., Vadhan, S.P., Wee, H.M.: Amplifying collision resistance: A complexity-theoretic treatment. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 264\u2013283. Springer, Heidelberg (2007)"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Capalbo, Reingold, Vadhan, Wigderson: Randomness conductors and constant-degree lossless expanders. In: STOC: ACM Symposium on Theory of Computing (STOC) (2002)","DOI":"10.1145\/509907.510003"},{"key":"29_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-642-00457-5_31","volume-title":"Theory of Cryptography","author":"J. Cook","year":"2009","unstructured":"Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich\u2019s one-way function candidate and myopic backtracking algorithms. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 521\u2013538. Springer, Heidelberg (2009)"},{"key":"29_CR14","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(090), citeseer.nj.nec.com\/382413.html (2000)"},{"key":"29_CR15","first-page":"120","volume":"2010","author":"I. Haitner","year":"2010","unstructured":"Haitner, I., Holenstein, T., Reingold, O., Vadhan, S.P., Wee, H.: Universal one-wayhash functions via inaccessible entropy. IACR Cryptology ePrint Archive\u00a02010, 120 (2010)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Kabanets, V.: Constructive proofs of concentration bounds. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15369-3_46"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Proc. of 40th STOC, pp. 433\u2013442 (2008)","DOI":"10.1145\/1374376.1374438"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Knudsen, Preneel: Construction of secure and fast hash functions using nonbinary error-correcting codes. IEEETIT: IEEE Transactions on Information Theory\u00a048 (2002)","DOI":"10.1109\/TIT.2002.801402"},{"key":"29_CR19","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1017\/S0025557200006690","volume":"94","author":"N. Lord","year":"2010","unstructured":"Lord, N.: Binomial averages when the mean is an integer. The Mathematical Gazette\u00a094, 331\u2013332 (2010)","journal-title":"The Mathematical Gazette"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On _-biased generators in NC0. Proc. 44th FOCS, 136\u2013145 (2003)","DOI":"10.1109\/SFCS.2003.1238188"},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Naor, Yung: Universal one-way hash functions and their cryptographic applications. STOC: ACM Symposium on Theory of Computing (STOC) (1989)","DOI":"10.1145\/73007.73011"},{"key":"29_CR22","unstructured":"Panjwani, S.K.: An experimental evaluation of goldreich\u2019s one-way function. Tech.rep., IIT, Bombay oded\/PS\/ow-report.ps (2001), http:\/\/www.wisdom.weizmann.ac.il\/"},{"key":"29_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-540-25937-4_24","volume-title":"Fast Software Encryption","author":"P. Rogaway","year":"2004","unstructured":"Rogaway, P., Shrimpton, T.: Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol.\u00a03017, pp. 371\u2013388. Springer, Heidelberg (2004)"},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"Rompel: One-way functions are necessary and su_cient for secure signatures. STOC: ACM Symposium on Theory of Computing (STOC) (1990)","DOI":"10.1145\/100216.100269"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38348-9_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T09:17:45Z","timestamp":1746004665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38348-9_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642383472","9783642383489"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38348-9_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}