Abstract
We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph G and a small predicate P that is applied at each output. Following the works of Cryan and Miltersen (MFCS ’01) and by Mossel et al (FOCS ’03), we ask: which graphs and predicates yield “small-bias” generators (that fool linear distinguishers)?
We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, \(f\colon \{0,1\}^n \rightarrow \{0,1\}^m\), with output length m = n 1 + ε for some constant ε > 0. Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear m = n + Ω(n). Taken together, these results expose a dichotomy: every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs.
As a secondary contribution, we give evidence in support of the view that small bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks for such functions.
Chapter PDF
Similar content being viewed by others
References
Alekhnovich, M.: More on average case vs approximation complexity. In: FOCS, pp. 298–307. IEEE Computer Society (2003)
Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity. SIAM Journal of Computation 34(1), 67–88 (2004)
Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reasoning 35(1-3), 51–72 (2005)
Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. Electronic Colloquium on Computational Complexity (ECCC) 18 (2011)
Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 171–180 (2010)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM Journal on Computing 36(4), 845–888 (2006)
Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. Journal of Computational Complexity 17(1), 38–69 (2008)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. Journal of Cryptology 22(4), 429–469 (2009)
Arora, S., Ge, R.: New Algorithms for Learning in Presence of Errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 403–415. Springer, Heidelberg (2011)
Ben-Sasson, E., Wigderson, A.: Short proofs are narrow - resolution made simple. In: STOC, pp. 517–526 (1999)
Bogdanov, A., Papakonstantinou, P., Wan, A.: Pseudorandomness for read-once formulas. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (2011) (to appear)
Bogdanov, A., Qiao, Y.: On the Security of Goldreich’s One-Way Function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol. 5687, pp. 392–405. Springer, Heidelberg (2009)
Bogdanov, A., Rosen, A.: Input Locality and Hardness Amplification. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 1–18. Springer, Heidelberg (2011)
Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. SIAM J. Comput. 39(6), 2464–2486 (2010)
Braverman, M.: Poly-logarithmic independence fools AC0 circuits. In: Annual IEEE Conference on Computational Complexity, pp. 3–8 (2009)
Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 521–538. Springer, Heidelberg (2009)
Cryan, M., Miltersen, P.B.: On Pseudorandom Generators in NC0. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 272–284. Springer, Heidelberg (2001)
Diakonikolas, I., Gopalan, P., Jaiswal, R., Servedio, R.A., Viola, E.: Bounded independence fools halfspaces. SIAM Journal of Computation 39(8), 3441–3462 (2010)
Diakonikolas, I., Kane, D.M., Nelson, J.: Bounded independence fools degree-2 threshold functions. In: FOCS, pp. 11–20 (2010)
Etesami, S.O.: Pseudorandomness against depth-2 circuits and analysis of goldreich’s candidate one-way function. Technical Report EECS-2010-180, UC Berkeley (2010)
Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM: Journal of the ACM 42 (1995)
Goldreich, O.: Candidate one-way functions based on expander graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(090) (2000)
Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 356–364 (1994)
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 433–442. ACM (2008)
Itsykson, D.: Lower bound on average-case complexity of inversion of goldreich’s function by drunken backtracking algorithms. In: Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia, pp. 204–215 (2010)
Miller, R.: Goldreich’s one-way function candidate and drunken backtracking algorithms. Distinguished major thesis, University of Virginia (2009)
Mossel, E., Shpilka, A., Trevisan, L.: On ε-biased generators in NC0. In: Proc. 44th FOCS, pp. 136–145 (2003)
Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing 22(4), 838–856 (1993); Preliminary version in Proc. 22th STOC (1990)
Panjwani, S.K.: An experimental evaluation of goldreich’s one-way function. Technical report, IIT, Bombay (2001)
Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory 30(5), 776–778 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Applebaum, B., Bogdanov, A., Rosen, A. (2012). A Dichotomy for Local Small-Bias Generators. In: Cramer, R. (eds) Theory of Cryptography. TCC 2012. Lecture Notes in Computer Science, vol 7194. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28914-9_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-28914-9_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28913-2
Online ISBN: 978-3-642-28914-9
eBook Packages: Computer ScienceComputer Science (R0)