×

The GGM function family is a weakly one-way family of functions. (English) Zbl 1369.94527

Hirt, Martin (ed.) et al., Theory of cryptography. 14th international conference, TCC 2016-B, Beijing, China, October 31 – November 3, 2016. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-53640-7/pbk; 978-3-662-53641-4/ebook). Lecture Notes in Computer Science 9985, 84-107 (2016).
Summary: 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+\varepsilon}\)-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.
For the entire collection see [Zbl 1347.94003].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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 · Zbl 1290.94145 · doi:10.1007/978-3-642-54631-0_29
[2] 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 · Zbl 1371.94664 · doi:10.1007/978-3-662-46803-6_12
[3] 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 · Zbl 1337.94021 · doi:10.1007/978-3-662-48797-6_1
[4] 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 · Zbl 1314.94057 · doi:10.1007/978-3-642-42045-0_15
[5] Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM (JACM) 51(4), 557–594 (2004) · Zbl 1204.94063 · doi:10.1145/1008731.1008734
[6] 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 · Zbl 0870.94026 · doi:10.1007/3-540-48329-2_40
[7] Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM (JACM) 33(4), 792–807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503
[8] Goldreich, O.: The GGM construction does not yield correlation intractable function ensembles (2002) · Zbl 1343.94052
[9] Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011 · doi:10.1017/CBO9780511721656
[10] 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) · doi:10.1145/2508859.2516668
[11] Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988) · Zbl 0644.94018 · doi:10.1137/0217022
[12] Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24–35 (1997) · Zbl 0884.68055 · doi:10.1006/jcss.1997.1494
[13] 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) · Zbl 1315.94102
[14] Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984) · Zbl 0587.68077 · doi:10.1145/1968.1972
[15] 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) · doi:10.1109/FOCS.2012.37
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.