Top

Published in:

2018 | OriginalPaper | Chapter

On the Concrete Security of Goldreich’s Pseudorandom Generator

Authors : Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, Yann Rotella

Published in: Advances in Cryptology – ASIACRYPT 2018

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Local pseudorandom generators allow to expand a short random string into a long pseudo-random string, such that each output bit depends on a constant number d of input bits. Due to its extreme efficiency features, this intriguing primitive enjoys a wide variety of applications in cryptography and complexity. In the polynomial regime, where the seed is of size n and the output of size \(n^{\textsf {s}}\) for \(\textsf {s}> 1\), the only known solution, commonly known as Goldreich’s PRG, proceeds by applying a simple d-ary predicate to public random size-d subsets of the bits of the seed.

While the security of Goldreich’s PRG has been thoroughly investigated, with a variety of results deriving provable security guarantees against class of attacks in some parameter regimes and necessary criteria to be satisfied by the underlying predicate, little is known about its concrete security and efficiency. Motivated by its numerous theoretical applications and the hope of getting practical instantiations for some of them, we initiate a study of the concrete security of Goldreich’s PRG, and evaluate its resistance to cryptanalytic attacks. Along the way, we develop a new guess-and-determine-style attack, and identify new criteria which refine existing criteria and capture the security guarantees of candidate local PRGs in a more fine-grained way.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter New MILP Modeling: Improved Conditional Cube Attacks on Keccak-Based Constructions

next chapter A Framework for Achieving KDM-CCA Secure Public-Key Encryption

The subsets form an expander graph if for some k, every k subsets cover \(k+\varOmega (n)\) elements of [n]. In practice, it suffices to pick once for all the subsets \((\sigma ^1, \ldots , \sigma ^m)\) at random to guarantee that they will be expanding except with o(1) probability.

A linear test attempts to distinguish a string from random by checking whether the xor of a subset of the bits of the string is biased toward either 0 or 1.

The locality requirement can in fact be weakened to a related notion of block locality.

In this model, n parties securely compute a function f on private inputs \((x_1,\ldots , x_n)\); in the preprocessing phase, the parties have access to f (but not to the input), and generate some preprocessing material. Then, in the online phase, the parties execute an information-theoretically secure protocol to compute f(x), using the preprocessed material. MPC protocols in the preprocessing model are among the most promising candidates for getting practical solutions to the multiparty computation problem.

A predicate P has r-bit fixing degree e if the minimal degree of the restriction of P obtained by fixing r inputs is e.

An annihilator of a predicate P is a non-zero polynomials Q such that \(Q\cdot P = 0\).

If more than n linear equations are recovered from Step 1 and 2, the system is unlikely to be solvable for an incorrect guess. In that case, it is not necessary to check if the public output matches with the candidate seed.

It is very unlikely that two seeds give the same output by evaluating the same quadratic system. Even though, if it is the case, this procedure still finds an equivalent seed which makes the system insecure.

We actually took a margin of \(10\%\) to take into account the possible improvements of our implementation.

This curve should not be extrapolated because outside of its range, Gröbner attacks seem more powerful, see Fig. 5.

[ABR12]

Applebaum, B., Bogdanov, A., Rosen, A.: A dichotomy for local small-bias generators. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 600–617. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_34CrossRef

[ABR16]

Applebaum, B., Bogdanov, A., Rosen, A.: A dichotomy for local small-bias generators. J. Cryptol. 29(3), 577–596 (2016)MathSciNetCrossRef

[ADI+17a]

Applebaum, B., Damgård, I., Ishai, Y., Nielsen, M., Zichron, L.: Secure arithmetic computation with constant computational overhead. Cryptology ePrint Archive, Report 2017/617 (2017). http://eprint.iacr.org/2017/617

[ADI+17b]

Applebaum, B., Damgård, I., Ishai, Y., Nielsen, M., Zichron, L.: Secure arithmetic computation with constant computational overhead. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 223–254. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_8CrossRef

[AHI05]

Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason. 35(1–3), 51–72 (2005)MathSciNetMATH

[AIK04]

Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC\(^0\). In: 45th FOCS, pp. 166–175. IEEE Computer Society Press, October 2004

[AIK08]

Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC\(^0\). Comput. Complex. 17(1), 38–69 (2008)MathSciNetCrossRef

[AL16]

Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. In: 48th ACM STOC, pp. 1087–1100. ACM Press, June 2016

[App12]

Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. In: 44th ACM STOC, pp. 805–816. ACM Press, May 2012

[App13]

Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput. 42(5), 2008–2037 (2013)MathSciNetCrossRef

[App15]

Applebaum, B.: The cryptographic hardness of random local functions - survey. Cryptology ePrint Archive, Report 2015/165 (2015). http://eprint.iacr.org/2015/165

[ARS+15]

Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_17CrossRef

[BCG+17]

Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Orrù, M.: Homomorphic secret sharing: optimizations and applications. In: ACM CCS 2017, pp. 2105–2122. ACM Press (2017)

[Bet11]

Bettale, L.: Cryptanalyse algebrique: outils et applications, Ph.D. thesis (2011)

[BGI+01]

Barak, B., et al.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1CrossRef

[BQ09]

Bogdanov, A., Qiao, Y.: On the security of Goldreich’s one-way function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX/RANDOM -2009. LNCS, vol. 5687, pp. 392–405. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03685-9_30CrossRef

[CCF+16]

Canteaut, A., et al.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 313–333. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_16CrossRef

[CDM+18]

Couteau, G., Dupin, A., Méaux, P., Rossi, M., Rotella, Y.: On the concrete security of Goldreich’s pseudorandom generator (2018)

[CEMT14]

Cook, J., Etesami, O., Miller, R., Trevisan, L.: On the one-way function candidate proposed by Goldreich. ACM Trans. Comput. Theor. (TOCT) 6(3), 14 (2014)MathSciNetMATH

[CM01]

Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC⁰. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 272–284. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44683-4_24CrossRef

[CM03]

Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_21CrossRef

[Cou03]

Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_11CrossRef

[DGM05]

Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically significant boolean functions: construction and analysis in terms of algebraic immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005). https://doi.org/10.1007/11502760_7CrossRef

[DLR16]

Duval, S., Lallemand, V., Rotella, Y.: Cryptanalysis of the FLIP family of stream ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 457–475. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_17CrossRef

[DMS05]

Dalai, D.K., Maitra, S., Sarkar, S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Cryptology ePrint Archive, Report 2005/229 (2005). http://eprint.iacr.org/2005/229

[EJ00]

Ekdahl, P., Johansson, T.: SNOW - a new stream cipher. In: Proceedings of First NESSIE Workshop, Heverlee (2000)

[GGM84]

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: 25th FOCS, pp. 464–479. IEEE Computer Society Press, October 1984

[Gol00]

Goldreich, O.: Candidate one-way functions based on expander graphs. Cryptology ePrint Archive, Report 2000/063 (2000). http://eprint.iacr.org/2000/063

[GRR+16]

Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.P.: MPC-friendly symmetric key primitives. In: ACM CCS 2016, pp. 430–443. ACM Press, October 2016

[HR00]

Hawkes, P., Rose, G.G.: Exploiting multiples of the connection polynomial in word-oriented stream ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 303–316. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_23CrossRef

[IKOS08]

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: 40th ACM STOC, pp. 433–442. ACM Press, May 2008

[IPS08]

Ishai, Y., Prabhakaran, M., Sahai, A.: Secure arithmetic computation with no honest majority. Cryptology ePrint Archive, Report 2008/465 (2008)

[Lin17]

Lin, H.: Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 599–629. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_20CrossRef

[LT17]

Lin, H., Tessaro, S.: Indistinguishability obfuscation from trilinear maps and block-wise local PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 630–660. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_21CrossRef

[LV17]

Lombardi, A., Vaikuntanathan, V.: Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 119–137. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_5CrossRefMATH

[MJSC16]

Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_13CrossRef

[MST03]

Mossel, E., Shpilka, A., Trevisan, L.: On e-Biased generators in NC0. In: 44th FOCS, pp. 136–145. IEEE Computer Society Press, October 2003

[OW14]

ODonnell, R., Witmer, D.: Goldreich’s PRG: evidence for near-optimal polynomial stretch. In: IEEE 29th Conference on Computational Complexity (CCC), pp. 1–12. IEEE (2014)

[Sie84]

Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications (corresp.). IEEE Trans. Inf. Theor. 30(5), 776–780 (1984)MathSciNetCrossRef

[SW14]

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: 46th ACM STOC, pp. 475–484. ACM Press, May/June 2014

[Wie86]

Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theor. 32(1), 54–62 (1986)MathSciNetCrossRef

Title: On the Concrete Security of Goldreich’s Pseudorandom Generator
Authors: Geoffroy Couteau
Aurélien Dupin
Pierrick Méaux
Mélissa Rossi
Yann Rotella
Publisher: Springer International Publishing
Book: Advances in Cryptology – ASIACRYPT 2018
Print ISBN: 978-3-030-03328-6

Electronic ISBN: 978-3-030-03329-3

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-03329-3_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner