Algebraic attacks against random local functions and their countermeasures

ABSTRACT

Suppose that you have n truly random bits x=(x₁,…,x_n) and you wish to use them to generate m≫ n pseudorandom bits y=(y₁,…, y_m) using a local mapping, i.e., each y_i should depend on at most d=O(1) bits of x. In the polynomial regime of m=n^s, s>1, the only known solution, originates from (Goldreich, ECCC 2000), is based on Random Local Functions: Compute y_i by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct inputs (x_i1,…,x_id). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results:

(1) We show that pseudorandomness against F₂-linear adversaries (i.e., the distribution y has low-bias) is achieved if the predicate is (a) k=Ω(s)-resilience, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local low-bias generator can have output length of n^Ω(d), answering an open question of Mossel, Shpilka and Trevisan (FOCS, 2003). Our negative result shows that a candidate for pseudorandom generator proposed by the first author (computational complexity, 2015) and by O’Donnell and Witmer (CCC 2014) is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins and Vempala (STOC 2015) regarding the hardness of planted constraint satisfaction problems.

(2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the Polynomial Calculus proof system. We show that algebraic attacks succeed if and only if there exist a degree e=O(s) non-zero polynomial Q whose roots cover the roots of P or cover the roots of P’s complement. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by the first author (Question 4.9, computational complexity 2015).

References

1. M. Alekhnovich. More on average case vs approximation complexity. In 44th FOCS, pages 298–307, 2003.
2. M. Alekhnovich and A. A. Razborov. Lower bounds for polynomial calculus: Non-binomial case. In 42nd FOCS, pages 190–199, 2001.
3. B. Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput, 42(5):2008–2037, 2013.
4. B. Applebaum. Cryptographic hardness of random local functions - survey. Computational Complexity, 10.1007/s00037-015-0121-8, 1–56, 2015.
5. B. Applebaum, B. Barak, and A. Wigderson. Public-key cryptography from different assumptions. In 42nd ACM STOC, pages 171–180, 2010.
6. B. Applebaum, A. Bogdanov, and A. Rosen. A dichotomy for local small-bias generators. In TCC 2012, pages 600–617, 2012.
7. B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography in NC 0. SIAM J. Comput, 36(4):845–888, 2006.
8. B. Applebaum, Y. Ishai, and E. Kushilevitz. On pseudorandom generators with linear stretch in NC 0. Computational Complexity, 17(1):38–69, 2008.
9. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998.
10. S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998.
11. B. Barak, G. Kindler, and D. Steurer. On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. In ITCS 2013, pages 197–214, 2013.
12. A. Bogdanov and Y. Qiao. On the security of Goldreich’s one-way function. Computational Complexity, 21(1):83–127, 2012.
13. A. Bogdanov and A. Rosen. Input locality and hardness amplification. In TCC 2011, pages 1–18, 2011.
14. C. Carlet. Boolean models and methods in mathematics, computer science, and engineering. Chapter in Boolean functions for cryptography and error-correcting codes, pages 257-397. Cambridge University Press, 2010.
15. M. Clegg, J. Edmonds, and R. Impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability. In 28th ACM STOC, pages 174–183, 1996.
16. J. Cook, O. Etesami, R. Miller, and L. Trevisan. Goldreich’s one-way function candidate and myopic backtracking algorithms. In TCC 2009, pages 521–538, 2009.
17. J. Cook, O. Etesami, R. Miller, and L. Trevisan. On the one-way function candidate proposed by Goldreich. ACM ToCT, 6(3):14:1–14:35, 2014.
18. S. Cook. The complexity of theorem proving procedures. pages 151–158, 1971.
19. N. Courtois. The security of hidden field equations (HFE). In CT-RSA 2001, pages 266–281, 2001.
20. N. Courtois. Fast algebraic attacks on stream ciphers with linear feedback. In CRYPTO 2003, pages 176–194, 2003.
21. N. Courtois. General principles of algebraic attacks and new design criteria for cipher components. In H. Dobbertin, V. Rijmen, and A. Sowa, editors, Advanced Encryption Standard: AES, volume 3373 of Lecture Notes in Computer Science, pages 67–83, 2005.
22. N. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In EUROCRYPT 2000, pages 392–407, 2000.
23. N. Courtois and W. Meier. Algebraic attacks on stream ciphers with linear feedback. In EUROCRYPT 2003, pages 345–359, 2003.
24. M. Cryan and P. B. Miltersen. On pseudorandom generators in NC. In Proc. of 26th Mathematical Foundations of Computer Science (MFCS), pages 272–284, 2001.
25. I. Dinur, S. Goldwasser, and H. Lin. The computational benefit of correlated instances. In ITCS 2015, pages 219–228, 2015.
26. J.-C. Faugère. A new efficient algorithm for computing Gröbner bases F 4. Journal of Pure and Applied Algebra, 139(1-3):61–88, 1999.
27. J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5 ). In ISSAC’2002, pages 75–83. ACM Press, 2002.
28. U. Feige. Relations between average case complexity and approximation complexity. In 34th ACM STOC, pages 534–543, 2002.
29. V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. In 45th ACM STOC, pages 655–664, 2013.
30. V. Feldman, W. Perkins, and S. Vempala. On the complexity of random satisfiability problems with planted solutions. In 47th ACM STOC, pages 77–86, 2015.
31. Y. Filmus, M. Lauria, M. Miksa, J. Nordström, and M. Vinyals. Towards an understanding of polynomial calculus: New separations and lower bounds - (extended abstract). In ICALP 2013, Part I, pages 437–448, 2013.
32. O. Goldreich. Candidate one-way functions based on expander graphs. ECCC, 7(090), 2000.
33. R. Impagliazzo, P. Pudlák, and J. Sgall. Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Computational Complexity, 8(2):127–144, 1999.
34. Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Cryptography with constant computational overhead. In 40th ACM STOC, pages 433–442, 2008.
35. M. J. Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983–1006, 1998.
36. L. A. Levin. Universal sequential search problems. Problems of Information Transmission, 9, 1973.
37. E. Mossel, A. Shpilka, and L. Trevisan. On e-biased generators in NC0. In 44th FOCS, pages 136–145, 2003.
38. R. O’Donnell and D. Witmer. Goldreich’s PRG: evidence for near-optimal polynomial stretch. In 29th CCC, pages 1–12, 2014.
39. J. Patarin. Cryptoanalysis of the Matsumoto and Imai public key scheme of eurocrypt’88. In CRYPTO’95, pages 248–261, 1995.
40. C. E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28-4:656–715, 1949.
41. T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory, 30(5):776–778, 1984.
42. Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Syst., E75-D:116–124, 1992.

Index Terms

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data encryption

• Security and privacy

  • Cryptography

• Theory of computation

  • Computational complexity and cryptography