nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

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

verfasst von : Aloni Cohen, Saleet Klein

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel 3-Message Zero Knowledge Against Human Ignorance

Nächstes Kapitel On the (In)Security of SNARKs in the Presence of Oracles

Nur mit Berechtigung zugänglich

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)

Titel: The GGM Function Family Is a Weakly One-Way Family of Functions
verfasst von: Aloni Cohen
Saleet Klein
Verlag: Springer Berlin Heidelberg
Buch: Theory of Cryptography
Print ISBN: 978-3-662-53640-7

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

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53641-4_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner