{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:05:37Z","timestamp":1767139537329,"version":"build-2238731810"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T00:00:00Z","timestamp":1464825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T00:00:00Z","timestamp":1464825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00145-016-9232-x","type":"journal-article","created":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T15:21:15Z","timestamp":1464880875000},"page":"672-698","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Locally Computable UOWHF with Linear Shrinkage"],"prefix":"10.1007","volume":"30","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]},{"given":"Yoni","family":"Moses","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,2]]},"reference":[{"key":"9232_CR1","doi-asserted-by":"crossref","unstructured":"D.\u00a0Achlioptas, F.\u00a0Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, in J.M. Kleinberg, editor, 38th ACM STOC (ACM Press, 2006), pp. 130\u2013139","DOI":"10.1145\/1132516.1132537"},{"key":"9232_CR2","doi-asserted-by":"crossref","unstructured":"M.\u00a0Alekhnovich, E.A. Hirsch, D.\u00a0Itsykson, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason., 35(1\u20133), 51\u201372 (2005)","DOI":"10.1007\/s10817-005-9006-x"},{"key":"9232_CR3","unstructured":"B.\u00a0Applebaum, Cryptography in Constant Parallel Time. Phd thesis, Technion (Israel Institute of Technology, 2007)"},{"key":"9232_CR4","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput. 42(5), (2013)","DOI":"10.1137\/120884857"},{"key":"9232_CR5","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, A.\u00a0Bogdanov, A.\u00a0Rosen, A dichotomy for local small-bias generators, in R.\u00a0Cramer, editor, TCC\u00a02012, volume 7194 of LNCS (Springer, 2012), pp. 600\u2013617","DOI":"10.1007\/978-3-642-28914-9_34"},{"key":"9232_CR6","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, E.\u00a0Kushilevitz, Computationally private randomizing polynomials and their applications. J. Comput. Complex. 15(2), 115\u2013162 (2006)","DOI":"10.1007\/s00037-006-0211-8"},{"key":"9232_CR7","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, E.\u00a0Kushilevitz, Cryptography in $$\\text{NC}^{\\text{0 }}$$. SIAM J. Comput. 36(4), 845\u2013888 (2006)","DOI":"10.1137\/S0097539705446950"},{"key":"9232_CR8","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, E.\u00a0Kushilevitz, Cryptography with constant input locality. J. Cryptol. 22(4), 429\u2013469 (2009)","DOI":"10.1007\/s00145-009-9039-0"},{"key":"9232_CR9","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, P.\u00a0Rogaway, Collision-resistant hashing: towards making UOWHFs practical, in B.S. Kaliski Jr., editor, CRYPTO\u201997, volume 1294 of LNCS (Springer, 1997), pp. 470\u2013484","DOI":"10.1007\/BFb0052256"},{"key":"9232_CR10","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bogdanov, Y.\u00a0Qiao. On the security of goldreich\u2019s one-way function, in Proceedings of the 13th RANDOM (2009), pp. 392\u2013405","DOI":"10.1007\/978-3-642-03685-9_30"},{"key":"9232_CR11","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bogdanov, A.\u00a0Rosen, Input locality and hardness amplification, in Y.\u00a0Ishai, editor, TCC\u00a02011, volume 6597 of LNCS (Springer, 2011), pp. 1\u201318","DOI":"10.1007\/978-3-642-19571-6_1"},{"key":"9232_CR12","doi-asserted-by":"crossref","unstructured":"M.R. Capalbo, O.\u00a0Reingold, S.P. Vadhan, A.\u00a0Wigderson, Randomness conductors and constant-degree lossless expanders, in 34th ACM STOC (ACM Press, 2002), pp. 659\u2013668","DOI":"10.1145\/509907.510003"},{"key":"9232_CR13","doi-asserted-by":"crossref","unstructured":"J.\u00a0Cook, O.\u00a0Etesami, R.\u00a0Miller, L.\u00a0Trevisan, Goldreich\u2019s one-way function candidate and myopic backtracking algorithms, in O.\u00a0Reingold, editor, TCC\u00a02009, volume 5444 of LNCS (Springer, 2009), pp. 521\u2013538","DOI":"10.1007\/978-3-642-00457-5_31"},{"key":"9232_CR14","unstructured":"S.O. Etesami. Pseudorandomness against depth-2 circuits and analysis of goldreich\u2019s candidate one-way function. Technical Report EECS-2010-180 (UC Berkeley, 2010)"},{"key":"9232_CR15","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography: Basic Tools (Cambridge University Press, 2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"9232_CR16","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Candidate one-way functions based on expander graphs, in Studies in Complexity and Cryptography (2011), pp. 76\u201387. ECCC 2010","DOI":"10.1007\/978-3-642-22670-0_10"},{"key":"9232_CR17","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, T.\u00a0Holenstein, O.\u00a0Reingold, S.P. Vadhan, H.\u00a0Wee. Universal one-way hash functions via inaccessible entropy, in H.\u00a0Gilbert, editor, EUROCRYPT\u00a02010, volume 6110 of LNCS (Springer, 2010), pp. 616\u2013637","DOI":"10.1007\/978-3-642-13190-5_31"},{"key":"9232_CR18","doi-asserted-by":"crossref","unstructured":"R.\u00a0Impagliazzo, V.\u00a0Kabanets, Constructive proofs of concentration bounds, in APPROX-RANDOM (2010), pp. 617\u2013631","DOI":"10.1007\/978-3-642-15369-3_46"},{"key":"9232_CR19","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Ishai, E.\u00a0Kushilevitz, R.\u00a0Ostrovsky, A.\u00a0Sahai, Cryptography with constant computational overhead, in R.E. Ladner, C.\u00a0Dwork, editors, 40th ACM STOC (ACM Press, 2008), pp. 433\u2013442","DOI":"10.1145\/1374376.1374438"},{"key":"9232_CR20","doi-asserted-by":"crossref","unstructured":"D.\u00a0Itsykson, Lower bound on average-case complexity of inversion of goldreich\u2019s function by drunken backtracking algorithms, in Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia (2010), pp. 204\u2013215","DOI":"10.1007\/978-3-642-13182-0_19"},{"key":"9232_CR21","unstructured":"R.\u00a0Miller, Goldreich\u2019s one-way function candidate and drunken backtracking algorithms. Distinguished major thesis (University of Virginia, 2009)"},{"key":"9232_CR22","doi-asserted-by":"crossref","unstructured":"E.\u00a0Mossel, A.\u00a0Shpilka, L.\u00a0Trevisan, On e-biased generators in NC0, in 44th FOCS (IEEE Computer Society Press, 2003), pp. 136\u2013145","DOI":"10.1109\/SFCS.2003.1238188"},{"key":"9232_CR23","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor, M.\u00a0Yung, Universal one-way hash functions and their cryptographic applications, in 21st ACM STOC (ACM Press, 1989), pp. 33\u201343","DOI":"10.1145\/73007.73011"},{"key":"9232_CR24","unstructured":"S.K. Panjwani, An experimental evaluation of goldreich\u2019s one-way function. Technical report (IIT, Bombay, 2001)"},{"key":"9232_CR25","doi-asserted-by":"crossref","unstructured":"P.\u00a0Rogaway, T.\u00a0Shrimpton, Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance, in B.K. Roy, W.\u00a0Meier, editors, FSE\u00a02004, volume 3017 of LNCS (Springer, 2004), pp. 371\u2013388","DOI":"10.1007\/978-3-540-25937-4_24"},{"key":"9232_CR26","doi-asserted-by":"crossref","unstructured":"J.\u00a0Rompel, One-way functions are necessary and sufficient for secure signatures, in 22nd ACM STOC (ACM Press, 1990), pp. 387\u2013394","DOI":"10.1145\/100216.100269"},{"key":"9232_CR27","doi-asserted-by":"crossref","unstructured":"M.\u00a0Sipser, D.A. Spielman, Expander codes. IEEETIT: IEEE Transactions on Information Theory (1996), p. 42","DOI":"10.1109\/18.556667"}],"updated-by":[{"DOI":"10.1007\/s00145-023-09443-9","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T00:00:00Z","timestamp":1676332800000}}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-016-9232-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9232-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9232-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9232-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T16:27:17Z","timestamp":1748968037000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-016-9232-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,2]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["9232"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9232-x","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,2]]},"assertion":[{"value":"30 June 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2014","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2023","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00145-023-09443-9","URL":"https:\/\/doi.org\/10.1007\/s00145-023-09443-9","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}