{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T12:00:05Z","timestamp":1768910405592,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,4,11]],"date-time":"2009-04-11T00:00:00Z","timestamp":1239408000000},"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":[[2009,10]]},"DOI":"10.1007\/s00145-009-9039-0","type":"journal-article","created":{"date-parts":[[2009,4,10]],"date-time":"2009-04-10T14:39:00Z","timestamp":1239374340000},"page":"429-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Cryptography with Constant Input Locality"],"prefix":"10.1007","volume":"22","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":[[2009,4,11]]},"reference":[{"key":"9039_CR1","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich, More on average case vs approximation complexity, in Proc. 44th FOCS, 2003, pp.\u00a0298\u2013307","DOI":"10.1109\/SFCS.2003.1238204"},{"issue":"2","key":"9039_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00037-006-0211-8","volume":"15","author":"B. Applebaum","year":"2006","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Computationally private randomizing polynomials and their applications. Comput. Complex. 15(2), 115\u2013162 (2006). Preliminary version in Proc. 20th CCC, 2005","journal-title":"Comput. Complex."},{"issue":"4","key":"9039_CR3","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in NC0. SIAM J. Comput. 36(4), 845\u2013888 (2006). Preliminary version in Proc. 45th FOCS, 2004","journal-title":"SIAM J. Comput."},{"key":"9039_CR4","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, On pseudorandom generators with linear stretch in NC0, in Proc. 10th Random, 2006","DOI":"10.1007\/11830924_25"},{"key":"9039_CR5","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography with constant latency. Manuscript, 2009","DOI":"10.1007\/s00145-009-9039-0"},{"issue":"1","key":"9039_CR6","first-page":"70","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, S. Safra, Probabilistic checking of proofs: A\u00a0new characterization of np. J.\u00a0ACM 45(1), 70\u2013122 (1998). Preliminary version in Proc. 33rd FOCS, 1992","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"9039_CR7","first-page":"501","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems. J.\u00a0ACM 45(3), 501\u2013555 (1998). Preliminary version in Proc. 33rd FOCS, 1992","journal-title":"J.\u00a0ACM"},{"issue":"1","key":"9039_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0020-0190(87)90036-6","volume":"26","author":"L. Babai","year":"1987","unstructured":"L. Babai, Random oracles separate PSPACE from the polynomial-time hierarchy. Inf. Process. Lett. 26(1), 51\u201353 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9039_CR9","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E.R. Berlekamp","year":"1978","unstructured":"E.R. Berlekamp, R.J. McEliece, H.C. van Tilborg, On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9039_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/1008908.1008911","volume":"15","author":"M. Blum","year":"1983","unstructured":"M. Blum, Coin flipping by telephone: a\u00a0protocol for solving impossible problems. SIGACT News 15(1), 23\u201327 (1983)","journal-title":"SIGACT News"},{"key":"9039_CR11","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 850\u2013864 (1984). Preliminary version in Proc. 23rd FOCS, 1982","journal-title":"SIAM J. Comput."},{"key":"9039_CR12","unstructured":"A. Blum, M. Furst, M. Kearns, R.J. Lipton, Cryptographic primitives based on hard learning problems, in Advances in Cryptology: Proc. of CRYPTO \u201993, LNCS, vol.\u00a0773 (1994), pp.\u00a0278\u2013291"},{"issue":"4","key":"9039_CR13","first-page":"506","volume":"50","author":"A. Blum","year":"2003","unstructured":"A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J.\u00a0ACM 50(4), 506\u2013519 (2003). Preliminary version in Proc. 32nd STOC, 2000","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"9039_CR14","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/0890-5401(87)90022-8","volume":"74","author":"R.B. Boppana","year":"1987","unstructured":"R.B. Boppana, J.C. Lagarias, One-way functions and circuit complexity. Inf. Comput. 74(3), 226\u2013240 (1987)","journal-title":"Inf. Comput."},{"key":"9039_CR15","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1145\/800157.805047","volume-title":"STOC \u201971: Proceedings of the Third Annual ACM Symposium on Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, in STOC \u201971: Proceedings of the Third Annual ACM Symposium on Theory of Computing, New York, NY, USA (ACM Press, New York, 1971), pp. 151\u2013158"},{"key":"9039_CR16","doi-asserted-by":"crossref","unstructured":"M. Cryan, P.B. Miltersen, On pseudorandom generators in NC0, in Proc. 26th MFCS, 2001, pp.\u00a0272\u2013284","DOI":"10.1007\/3-540-44683-4_24"},{"issue":"2","key":"9039_CR17","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/S0097539795291562","volume":"30","author":"D. Dolev","year":"2000","unstructured":"D. Dolev, C. Dwork, M. Naor, Non-malleable cryptography. SIAM J. Comput. 30(2), 391\u2013437 (2000)","journal-title":"SIAM J. Comput."},{"key":"9039_CR18","doi-asserted-by":"crossref","unstructured":"U. Feige, J. Killian, M. Naor, A\u00a0minimal model for secure computation (extended abstract), in Proc. of the 26th STOC, 1994, pp.\u00a0554\u2013563","DOI":"10.1145\/195058.195408"},{"key":"9039_CR19","doi-asserted-by":"crossref","unstructured":"V. Feldman, P. Gopalan, S. Khot, A.K. Ponnuswami, New results for learning noisy parities and halfspaces, in Proc. 47th FOCS, 2006, pp.\u00a0563\u2013574","DOI":"10.1109\/FOCS.2006.51"},{"key":"9039_CR20","unstructured":"O. Goldreich, Candidate one-way functions based on expander graphs. Electron. Colloq. Comput. Complex. (ECCC) 7(090) (2000)"},{"key":"9039_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Tools (Cambridge University Press, Cambridge, 2001)"},{"key":"9039_CR22","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Applications (Cambridge University Press, Cambridge, 2004)"},{"key":"9039_CR23","doi-asserted-by":"crossref","unstructured":"O. Goldreich, L. Levin, A\u00a0hard-core predicate for all one-way functions, in Proc. 21st STOC, 1989, pp.\u00a025\u201332","DOI":"10.1145\/73007.73010"},{"key":"9039_CR24","first-page":"792","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J.\u00a0ACM 33, 792\u2013807 (1986)","journal-title":"J.\u00a0ACM"},{"issue":"6","key":"9039_CR25","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O. Goldreich","year":"1993","unstructured":"O. Goldreich, H. Krawczyk, M. Luby, On the existence of pseudorandom generators. SIAM J. Comput. 22(6), 1163\u20131175 (1993). Preliminary version in Proc. 29th FOCS, 1988","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9039_CR26","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser, S. Micali, Probabilistic encryption. J.\u00a0Comput. Syst. Sci. 28(2), 270\u2013299 (1984). Preliminary version in Proc. STOC \u201982","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"4","key":"9039_CR27","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"9039_CR28","doi-asserted-by":"crossref","unstructured":"T. Holenstein, Pseudorandom generators from one-way functions: A\u00a0simple construction for any hardness, in Proc. 3rd TCC, 2006, pp.\u00a0443\u2013461","DOI":"10.1007\/11681878_23"},{"key":"9039_CR29","unstructured":"N.J. Hopper, M. Blum, Secure human identification protocols, in Advances in Cryptology: Proc. of ASIACRYPT \u201901, LNCS, vol.\u00a02248 (2001), pp.\u00a052\u201366"},{"key":"9039_CR30","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography, in Proc. of the 30th FOCS, 1989, pp.\u00a0230\u2013235","DOI":"10.1109\/SFCS.1989.63483"},{"issue":"4","key":"9039_CR31","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"R. Impagliazzo, M. Naor, Efficient cryptographic schemes provably as secure as subset sum. J.\u00a0Cryptol. 9(4), 199\u2013216 (1996). Preliminary version in FOCS \u201989","journal-title":"J.\u00a0Cryptol."},{"key":"9039_CR32","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proc. 41st FOCS, 2000, pp.\u00a0294\u2013304","DOI":"10.1109\/SFCS.2000.892118"},{"key":"9039_CR33","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, Perfect constant-round secure computation via perfect randomizing polynomials, in Proc. 29th ICALP, 2002, pp.\u00a0244\u2013256","DOI":"10.1007\/3-540-45465-9_22"},{"issue":"3","key":"9039_CR34","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/A:1027351723034","volume":"8","author":"H. Janwa","year":"1996","unstructured":"H. Janwa, O. Moreno, Mceliece public key cryptosystems using algebraic-geometric codes. Des. Codes Cryptogr. 8(3), 293\u2013307 (1996)","journal-title":"Des. Codes Cryptogr."},{"key":"9039_CR35","unstructured":"A. Juels, S. Weis, Authenticating pervasive devices with human protocols, in Advances in Cryptology: Proc. of CRYPTO \u201905, LNCS, vol.\u00a03621 (2005), pp.\u00a0293\u2013308"},{"key":"9039_CR36","unstructured":"J. Katz, J.-S. Shin, Parallel and concurrent security of the hb and hb+ protocols, in Advances in Cryptology: Proc. of Eurocrypt 06\u2019, LNCS, vol.\u00a04004 (2006), pp.\u00a073\u201387"},{"key":"9039_CR37","doi-asserted-by":"crossref","unstructured":"J. Katz, M. Yung, Complete characterization of security notions for probabilistic private-key encryption, in Proc. 32nd STOC, 2000, pp.\u00a0245\u2013254","DOI":"10.1145\/335305.335335"},{"key":"9039_CR38","doi-asserted-by":"crossref","unstructured":"M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R.E. Schapire, L. Sellie, On the learnability of discrete distributions, in Proc. 26th STOC, 1994, pp.\u00a0273\u2013282","DOI":"10.1145\/195058.195155"},{"issue":"6","key":"9039_CR39","first-page":"983","volume":"45","author":"M.J. Kearns","year":"1998","unstructured":"M.J. Kearns, Efficient noise-tolerant learning from statistical queries. J.\u00a0ACM 45(6), 983\u20131006 (1998)","journal-title":"J.\u00a0ACM"},{"key":"9039_CR40","doi-asserted-by":"crossref","unstructured":"J. Kilian, Founding cryptography on oblivious transfer, in Proc. 20th STOC, 1988, pp.\u00a020\u201331","DOI":"10.1145\/62212.62215"},{"key":"9039_CR41","unstructured":"L.A. Levin, Universal sequential search problems. PINFTRANS: Probl. Inf. Transm. Translated from Problemy Peredachi Informatsii (Russian) 9 (1973)"},{"issue":"3","key":"9039_CR42","first-page":"607","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour, N. Nisan, Constant depth circuits, Fourier transform, and learnability. J.\u00a0ACM 40(3), 607\u2013620 (1993). Preliminary version in Proc. 30th FOCS, 1989","journal-title":"J.\u00a0ACM"},{"key":"9039_CR43","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem, in Proc. 9th Random, 2005","DOI":"10.1007\/11538462_32"},{"key":"9039_CR44","unstructured":"R.J. McEliece, A\u00a0public-key cryptosystem based on algebraic coding theory. Technical Report DSN PR 42-44, Jet Prop. Lab., 1978"},{"key":"9039_CR45","doi-asserted-by":"crossref","unstructured":"E. Mossel, A. Shpilka, L. Trevisan, On \u03b5-biased generators in NC0, in Proc. 44th FOCS, 2003, pp.\u00a0136\u2013145","DOI":"10.1109\/SFCS.2003.1238188"},{"issue":"2","key":"9039_CR46","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M. Naor","year":"1999","unstructured":"M. Naor, O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. J.\u00a0Comput. Syst. Sci. 58(2), 336\u2013375 (1999). Preliminary version in Proc. 36th FOCS, 1995","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9039_CR47","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes. J.\u00a0Comput. Syst. Sci. 43, 425\u2013440 (1991). Preliminary version in Proc. 20th STOC, 1988","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9039_CR48","doi-asserted-by":"crossref","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in Proc. 37th STOC, 2005, pp.\u00a084\u201393","DOI":"10.1145\/1060590.1060603"},{"key":"9039_CR49","unstructured":"M. Sudan, Algorithmic introduction to coding theory\u2014lecture notes, 2002. http:\/\/theory.csail.mit.edu\/~madhu\/FT01\/"},{"key":"9039_CR50","first-page":"739","volume":"117","author":"R. Varshamov","year":"1957","unstructured":"R. Varshamov, Estimate of the number of signals in error correcting codes. Dokl. Akad. Nauk SSSR 117, 739\u2013741 (1957)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9039_CR51","doi-asserted-by":"crossref","unstructured":"E. Viola, On constructing parallel pseudorandom generators from one-way functions, in Proc. IEEE Conference on Computational Complexity 2005, pp.\u00a0183\u2013197","DOI":"10.1109\/CCC.2005.16"},{"key":"9039_CR52","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Theory and application of trapdoor functions, in Proc. 23rd FOCS, 1982, pp.\u00a080\u201391","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-009-9039-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-009-9039-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-009-9039-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-009-9039-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T22:52:47Z","timestamp":1739055167000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-009-9039-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,11]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9039"],"URL":"https:\/\/doi.org\/10.1007\/s00145-009-9039-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,11]]},"assertion":[{"value":"27 November 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2009","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2009","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"}]}}