{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T10:57:34Z","timestamp":1649069854439},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T00:00:00Z","timestamp":1475452800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00145-016-9244-6","type":"journal-article","created":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T18:48:14Z","timestamp":1475520494000},"page":"1-22","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Minimizing Locality of One-Way Functions via Semi-private Randomized Encodings"],"prefix":"10.1007","volume":"31","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,3]]},"reference":[{"key":"9244_CR1","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ajtai. Secure computation with information leaking to an adversary, in Proceedings of 43rd STOC (2011), pp. 715\u2013724.","DOI":"10.1145\/1993636.1993731"},{"key":"9244_CR2","doi-asserted-by":"publisher","unstructured":"B.\u00a0Applebaum. The cryptographic hardness of random local functions. Comput. Complex., 25(3):667\u2013722, 2015. doi:\n                    10.1007\/s00037-015-0121-8\n                    \n                  .","DOI":"10.1007\/s00037-015-0121-8"},{"issue":"4","key":"9244_CR3","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B Applebaum","year":"2006","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, and E.\u00a0Kushilevitz. Cryptography in \n                    \n                      \n                    \n                    $${{\\rm NC}}^0$$\n                    \n                      \n                        \n                          \n                            NC\n                          \n                          0\n                        \n                      \n                    \n                  . SIAM J. Comput., 36(4):845\u2013888, 2006. Preliminary version in Proc.\u00a045th FOCS, 2004.","journal-title":"SIAM J. Comput."},{"key":"9244_CR4","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, and E.\u00a0Kushilevitz. Cryptography by cellular automata or how fast can complexity emerge in nature? in Proceedings of 1st ICS (2010), pp. 1\u201319."},{"key":"9244_CR5","unstructured":"M.\u00a0Ben-Or, S.\u00a0Goldwasser, and A.\u00a0Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation, in Proceedings of 20th STOC (1988), pp. 1\u201310."},{"issue":"1","key":"9244_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00037-011-0034-0","volume":"21","author":"A Bogdanov","year":"2012","unstructured":"A.\u00a0Bogdanov and Y.\u00a0Qiao. On the security of Goldreich\u2019s one-way function. Computational Complexity, 21(1):83\u2013127, 2012. Preliminary version in Proc. of 13th RANDOM, 2009.","journal-title":"Computational Complexity"},{"key":"9244_CR7","unstructured":"D.\u00a0Boneh, and B.\u00a0Waters. Conjunctive, subset, and range queries on encrypted data, in Proceedings of 4th TCC (2007), pp. 535\u2013554."},{"issue":"3","key":"9244_CR8","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2633602","volume":"6","author":"J Cook","year":"2014","unstructured":"J.\u00a0Cook, O.\u00a0Etesami, R.\u00a0Miller, and L.\u00a0Trevisan. On the one-way function candidate proposed by goldreich. TOCT, 6(3):14, 2014. Preminary version in Proc. of 6th TCC.","journal-title":"TOCT"},{"key":"9244_CR9","unstructured":"I.\u00a0Dinur, and H.\u00a0Finucane. Cryptography with locality two. Unpublished manuscript (2011)."},{"key":"9244_CR10","unstructured":"I.\u00a0Dinur, S.\u00a0Goldwasser, and H.\u00a0Lin. The computational benefit of correlated instances, in Proceedings of 6th ITCS (2015), pp. 219\u2013228."},{"key":"9244_CR11","doi-asserted-by":"crossref","unstructured":"D.\u00a0P. Dubhashi and A.\u00a0Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms (Cambridge University Press, Cambridge, 2009).","DOI":"10.1017\/CBO9780511581274"},{"issue":"5","key":"9244_CR12","doi-asserted-by":"publisher","first-page":"1564","DOI":"10.1137\/120880343","volume":"43","author":"S Faust","year":"2014","unstructured":"S.\u00a0Faust, T.\u00a0Rabin, L.\u00a0Reyzin, E.\u00a0Tromer, and V.\u00a0Vaikuntanathan. Protecting circuits from computationally bounded and noisy leakage. SIAM J. Comput., 43(5):1564\u20131614, 2014.","journal-title":"SIAM J. Comput."},{"key":"9244_CR13","unstructured":"T. K. Frederiksen, J. B. Nielsen, and C. Orlandi. Privacy-free garbled circuits with applications to efficient zero-knowledge. in Proceedings of 34th EUROCRYPT (2015), pp. 191\u2013219."},{"issue":"3","key":"9244_CR14","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1006\/jcss.1999.1689","volume":"60","author":"Y Gertner","year":"2000","unstructured":"Y.\u00a0Gertner, Y.\u00a0Ishai, E.\u00a0Kushilevitz, and T.\u00a0Malkin. Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci., 60(3):592\u2013629, 2000.","journal-title":"J. Comput. Syst. Sci."},{"key":"9244_CR15","doi-asserted-by":"crossref","unstructured":"O. Goldreich. Candidate one-way functions based on expander graphs, in Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (2011), pp. 76\u201387.","DOI":"10.1007\/978-3-642-22670-0_10"},{"key":"9244_CR16","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich. Foundations of Cryptography: Basic Tools. (Cambridge University Press, Cambridge, 2001).","DOI":"10.1017\/CBO9780511546891"},{"key":"9244_CR17","unstructured":"S. Gorbunov, V. Vaikuntanathan, and H. Wee. Predicate encryption for circuits from LWE, in Proceedings of 35th CRYPTO (2015), pp. 503\u2013523."},{"key":"9244_CR18","unstructured":"V.\u00a0Goyal, O.\u00a0Pandey, A.\u00a0Sahai, and B.\u00a0Waters. Attribute-based encryption for fine-grained access control of encrypted data, in Proceedings of 13th CCS (2006), pp. 89\u201398."},{"key":"9244_CR19","unstructured":"R.\u00a0Impagliazzo, and M.\u00a0Luby. One-way functions are essential for complexity based cryptography, in Proceedings of the 30th FOCS (1989), pp. 230\u2013235."},{"key":"9244_CR20","unstructured":"Y.\u00a0Ishai, and E.\u00a0Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of 41st FOCS (2000), pp. 294\u2013304."},{"key":"9244_CR21","unstructured":"Y.\u00a0Ishai, and E.\u00a0Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials, in Proceedings of 29th ICALP (2002), pp. 244\u2013256."},{"key":"9244_CR22","unstructured":"Y.\u00a0Ishai, E.\u00a0Kushilevitz, X.\u00a0Li, R.\u00a0Ostrovsky, M.\u00a0Prabhakaran, A.\u00a0Sahai, and D.\u00a0Zuckerman. Robust pseudorandom generators, in Proceedings of 40th ICALP (2013), pp. 576\u2013588."},{"key":"9244_CR23","unstructured":"Y.\u00a0Ishai, A.\u00a0Sahai, and D.\u00a0Wagner. Private circuits: Securing hardware against probing attacks, in Proceedings of 23rd CRYPTO (2003), pp. 463\u2013481."},{"key":"9244_CR24","unstructured":"Y. Ishai, and H. Wee. Partial garbling schemes and their applications, in Proceedings of 41st ICALP (2014), pp. 650\u2013662."},{"key":"9244_CR25","unstructured":"J.\u00a0Katz, A.\u00a0Sahai, and B.\u00a0Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products, in Proceedings of 27th EUROCRYPT (2008), pp. 146\u2013162."},{"key":"9244_CR26","unstructured":"A.\u00a0Sahai, and B.\u00a0Waters. Fuzzy identity-based encryption, in Proceedings of 24th EUROCRYPT (2005), pp. 457\u2013473."},{"key":"9244_CR27","unstructured":"E.\u00a0Shi, J.\u00a0Bethencourt, H.\u00a0T. Chan, D.\u00a0X. Song, and A.\u00a0Perrig. Multi-dimensional range query over encrypted data, in 2007 IEEE Symposium on Security and Privacy (S&P 2007), 20\u201323 May 2007, Oakland, CA, USA (2007), pp. 350\u2013364."},{"key":"9244_CR28","doi-asserted-by":"crossref","unstructured":"A.\u00a0C. Yao. Theory and application of trapdoor functions, in Proceedings of 23rd FOCS (1982), pp. 80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-016-9244-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9244-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9244-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:22:59Z","timestamp":1586334179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-016-9244-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9244"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9244-6","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,3]]},"assertion":[{"value":"31 March 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}