Top

Published in:

2016 | OriginalPaper | Chapter

The GGM Function Family Is a Weakly One-Way Family of Functions

Authors : Aloni Cohen, Saleet Klein

Published in: Theory of Cryptography

Publisher: Springer Berlin Heidelberg

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

search-config

AI-assisted search

Off

Abstract

We give the first demonstration of the cryptographic hardness of the Goldreich-Goldwasser-Micali (GGM) function family when the secret key is exposed. We prove that for any constant \(\epsilon >0\), the GGM family is a \(1/n^{2+\epsilon }\)-weakly one-way family of functions, when the lengths of secret key, inputs, and outputs are equal. Namely, any efficient algorithm fails to invert GGM with probability at least \(1/n^{2+\epsilon }\) – even when given the secret key.

Additionally, we state natural conditions under which the GGM family is strongly one-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 3-Message Zero Knowledge Against Human Ignorance

next chapter On the (In)Security of SNARKs in the Presence of Oracles

Available only for authorised users

And posed much earlier by Micali and by Barak: see Acknowledgments of [Gol02].

We consider the secret keys, inputs, and outputs to be of the same lengths. See Remark 2.

While these are indeed facts in the land of wishful thinking, they are not generally true. In this overview we wish to highlight only the usefulness of these facts, and believe that their proofs (though elementary), do not further this goal.

For example, the distribution \((x,\mathsf {Bernoulli(x)})_{\mathsf {Uniform[0,1]}}\) is the distribution over (x, b) by drawing the parameter x uniformly from [0, 1], and subsequently taking a sample b from the Bernoulli distribution with parameter x.

Whether this indeed holds depends on the PRG used to instantiate the GGM ensemble. We do not know if such a PRG exists.

If there exists a PRG, then there exists a PRG such that \(\text {SD}(D_{\mathsf {owf}},D_{\mathsf {rand}})= 1 - {\mathbb E}_{s\leftarrow U_n}[|\mathsf {Img}(f_s)|/2^n]\ge 1-1/n^2\). For example, if the PRG only uses the first n / 2 bits of its input, then \(|\mathsf {Img}(f_s)|< 2^{n/2+1}\).

This essentially a data-processing inequality.

[BGI14]

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54631-0_29 CrossRef

[BGI15]

Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337–367. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46803-6_12

[BLL+15]

Bai, S., Langlois, A., Lepoint, T., Stehlé, D., Steinfeld, R.: Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 3–24. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48797-6_1 CrossRef

[BW13]

Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 280–300. Springer, Heidelberg (2013). doi:10.1007/978-3-642-42045-0_15 CrossRef

[CGH04]

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM (JACM) 51(4), 557–594 (2004)MathSciNetCrossRefMATH

[FN94]

Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994). doi:10.1007/3-540-48329-2_40 CrossRef

[GGM86]

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM (JACM) 33(4), 792–807 (1986)MathSciNetCrossRefMATH

[Gol02]

Goldreich, O.: The GGM construction does not yield correlation intractable function ensembles (2002)

[Gol04]

Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)CrossRefMATH

[KPTZ13]

Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013, Berlin, Germany, 4–8 November 2013, pp. 669–684 (2013)

[LR88]

Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH

[RR97]

Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24–35 (1997)MathSciNetCrossRefMATH

[SW14]

Sahai, A., Waters, B.: How to use indistinguishability obfuscation, deniable encryption, and more. In: Symposium on Theory of Computing, STOC 2014, 31 May–3 June 2014, pp. 475–484. ACM, New York (2014)

[Val84]

Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984)CrossRefMATH

[Zha12]

Zhandry, M.: How to construct quantum random functions. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 679–687. IEEE (2012)

Title: The GGM Function Family Is a Weakly One-Way Family of Functions
Authors: Aloni Cohen
Saleet Klein
Publisher: Springer Berlin Heidelberg
Book: Theory of Cryptography
Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-662-53641-4_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