The Distinction Between Fixed and Random Generators in Group-Based Assumptions | SpringerLink
Skip to main content
Springer Nature Link
Log in

The Distinction Between Fixed and Random Generators in Group-Based Assumptions

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2019 (CRYPTO 2019)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11693))

Included in the following conference series:

Abstract

There is surprisingly little consensus on the precise role of the generator g in group-based assumptions such as DDH. Some works consider g to be a fixed part of the group description, while others take it to be random. We study this subtle distinction from a number of angles.

  • In the generic group model, we demonstrate the plausibility of groups in which random-generator DDH (resp. CDH) is hard but fixed-generator DDH (resp. CDH) is easy. We observe that such groups have interesting cryptographic applications.

  • We find that seemingly tight generic lower bounds for the Discrete-Log and CDH problems with preprocessing (Corrigan-Gibbs and Kogan, Eurocrypt 2018) are not tight in the sub-constant success probability regime if the generator is random. We resolve this by proving tight lower bounds for the random generator variants; our results formalize the intuition that using a random generator will reduce the effectiveness of preprocessing attacks.

  • We observe that DDH-like assumptions in which exponents are drawn from low-entropy distributions are particularly sensitive to the fixed- vs. random-generator distinction. Most notably, we discover that the Strong Power DDH assumption of Komargodski and Yogev (Komargodski and Yogev, Eurocrypt 2018) used for non-malleable point obfuscation is in fact false precisely because it requires a fixed generator. In response, we formulate an alternative fixed-generator assumption that suffices for a new construction of non-malleable point obfuscation, and we prove the assumption holds in the generic group model. We also give a generic group proof for the security of fixed-generator, low-entropy DDH (Canetti, Crypto 1997).

The full version of this paper is available at iacr.org/2019/202 [3].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 16015
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 20019
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    For example, the Katz-Lindell textbook [29] defines DDH with a fixed generator, while Cramer-Shoup [19] defines DDH with a random generator.

  2. 2.

    Sadeghi and Steiner [37] actually consider the more general possibility of the untrusted party choosing the group itself maliciously. This question is beyond the scope of our work, but in many cases it is an equally important consideration.

  3. 3.

    This inequivalence was also suggested by Saxena and Soh [38].

  4. 4.

    A similar observation was also made in [38].

  5. 5.

    The authors privately communicated these issues to the authors of [23, 31].

  6. 6.

    Relying on a random generator would require a common random string, which is not the model considered in [31] or in the version of [23] dated Jan 30, 2019 at eprint.iacr.org/2018/957/20190130:190441.

  7. 7.

    This issue appears in the Eurocrypt 2018 version of [31], in an older ePrint version of [32] dated May 1, 2018 at eprint.iacr.org/2018/149/20180211:142746, and in the ePrint version of [23] dated Jan 30, 2019 at eprint.iacr.org/2018/957/20190130:190441.

  8. 8.

    This refers to the newer ePrint version of [32] dated Feb 21, 2019 available at https://eprint.iacr.org/2018/149/20190221:133556.

  9. 9.

    Previously, such proofs had been obtained by Bitanksy and Canetti [6] and Damgård, Hazay, and Zottarel [20], who considered the random- and fixed-generator versions, respectively. We observe that both of these proofs treat the well-spread distribution as independent of the generic group labeling. Our proof handles distributions with arbitrary dependence on the labels; for more discussion refer to Part 4 of Sect. 1.2.

  10. 10.

    We defer a more detailed discussion on virtual-black-box obfuscation to [1] (see [42] for specifics on point function obfuscation).

  11. 11.

    As noted in Sect. 1.1, Komargodski and Yogev have offered a fix through a new Entropic Power DDH Assumption in a revised ePrint posting [32], which does not come with a generic group proof. The goal of this section is to build non-malleable point obfuscation from an assumption that holds against generic adversaries.

  12. 12.

    The assumption we actually use is slightly different: instead of stating indistinguishability from uniform, we require indistinguishability from \(\{g^{k_{i}y+y^i}\}_{i \in \{2,\dots ,n\}}\) for the same \(\{k_i\}_i\) but uniformly random y. We can prove both forms of this assumption hold in the GGM, but this second form yields a simpler proof of VBB security. For the purposes of this technical overview this distinction can be ignored.

  13. 13.

    Note that constant and identity polynomials correspond to “trivial” mauling attacks that cannot be prevented. A constant polynomial corresponds to picking an unrelated y and obfuscating y, while the identity polynomial corresponds to doing nothing.

References

  1. 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_1

    Chapter  Google Scholar 

  2. Barthe, G., Fagerholm, E., Fiore, D., Mitchell, J.C., Scedrov, A., Schmidt, B.: Automated analysis of cryptographic assumptions in generic group models. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 95–112. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_6

    Chapter  MATH  Google Scholar 

  3. Bartusek, J., Ma, F., Zhandry, M.: The distinction between fixed and random generators in group-based assumptions. Cryptology ePrint Archive, Report 2019/202 (2019). https://eprint.iacr.org/2019/202

  4. Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, pp. 62–73. ACM Press, November 1993

    Google Scholar 

  5. Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: the power of free precomputation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 321–340. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_17

    Chapter  Google Scholar 

  6. Bitansky, N., Canetti, R.: On strong simulation and composable point obfuscation. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 520–537. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_28

    Chapter  Google Scholar 

  7. Bitansky, N., Canetti, R.: On strong simulation and composable point obfuscation. J. Cryptol. 27(2), 317–357 (2014)

    Article  MathSciNet  Google Scholar 

  8. Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_13

    Chapter  Google Scholar 

  9. Boneh, D., Silverberg, A.: Applications of multilinear forms to cryptography. Contemp. Math. 324, 71–90 (2002)

    Article  MathSciNet  Google Scholar 

  10. Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 480–499. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_27

    Chapter  Google Scholar 

  11. Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Selecting elliptic curves for cryptography: an efficiency and security analysis. J. Crypt. Eng. 6(4), 259–286 (2016). https://doi.org/10.1007/s13389-015-0097-y

    Article  Google Scholar 

  12. Brands, S.: Untraceable off-line cash in wallet with observers. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 302–318. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_26

    Chapter  MATH  Google Scholar 

  13. Canetti, R.: Towards realizing random oracles: hash functions that hide all partial information. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052255

    Chapter  Google Scholar 

  14. Canetti, R., Dakdouk, R.R.: Extractable perfectly one-way functions. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 449–460. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_37

    Chapter  Google Scholar 

  15. Canetti, R., Varia, M.: Non-malleable obfuscation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 73–90. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_6

    Chapter  Google Scholar 

  16. Coretti, S., Dodis, Y., Guo, S.: Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 693–721. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_23

    Chapter  MATH  Google Scholar 

  17. Coretti, S., Dodis, Y., Guo, S., Steinberger, J.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 227–258. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_9

    Chapter  Google Scholar 

  18. Corrigan-Gibbs, H., Kogan, D.: The discrete-logarithm problem with preprocessing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 415–447. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_14

    Chapter  Google Scholar 

  19. Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055717

    Chapter  Google Scholar 

  20. Damgård, I., Hazay, C., Zottarel, A.: Short paper on the generic hardness of DDH-II (2014)

    Google Scholar 

  21. Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)

    Article  MathSciNet  Google Scholar 

  22. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_2

    Chapter  Google Scholar 

  23. Fenteany, P., Fuller, B.: Non-malleable digital lockers for efficiently sampleable distributions. Cryptology ePrint Archive, Report 2018/957 (2018). https://eprint.iacr.org/2018/957

  24. Fujisaki, E.: Improving practical UC-secure commitments based on the DDH assumption. In: Zikas, V., De Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 257–272. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44618-9_14

    Chapter  Google Scholar 

  25. Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)

    Book  Google Scholar 

  26. Gat, E., Goldwasser, S.: Probabilistic search algorithms with unique answers and their cryptographic applications. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 136 (2011)

    Google Scholar 

  27. Goldwasser, S., Tauman Kalai, Y.: Cryptographic assumptions: a position paper. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 505–522. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_21

    Chapter  Google Scholar 

  28. Kalai, Y.T., Li, X., Rao, A., Zuckerman, D.: Network extractor protocols. In: 49th FOCS, pp. 654–663. IEEE Computer Society Press, October 2008

    Google Scholar 

  29. Katz, J., Lindell, Y.: Modern Cryptography, 2nd edn. (2014)

    Google Scholar 

  30. Kim, J., Kim, S., Seo, J.H.: Multilinear map via scale-invariant FHE: Enhancing security and efficiency. Cryptology ePrint Archive, Report 2015/992 (2015). https://ia.cr/2015/992

  31. Komargodski, I., Yogev, E.: Another step towards realizing random oracles: non-malleable point obfuscation. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 259–279. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_10

    Chapter  Google Scholar 

  32. Komargodski, I., Yogev, E.: Another step towards realizing random oracles: non-malleable point obfuscation. Cryptology ePrint Archive, Report 2018/149 (2018). https://ia.cr/2018/149

  33. Lee, H.T., Cheon, J.H., Hong, J.: Accelerating ID-based encryption based on trapdoor DL using pre-computation. Cryptology ePrint Archive, Report 2011/187 (2011). https://ia.cr/2011/187

  34. Maurer, U.M.: Abstract models of computation in cryptography. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (2005). https://doi.org/10.1007/11586821_1

    Chapter  MATH  Google Scholar 

  35. Mihalcik, J.: An analysis of algorithms for solving discrete logarithms in fixed groups, master’s thesis, Naval Postgraduate School (2010)

    Google Scholar 

  36. Nechaev, V.I.: Complexity of a determinate algorithm for the discrete logarithm. Math. Notes 55(2), 165–172 (1994)

    Article  MathSciNet  Google Scholar 

  37. Sadeghi, A.-R., Steiner, M.: Assumptions related to discrete logarithms: why subtleties make a real difference. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 244–261. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_16

    Chapter  Google Scholar 

  38. Saxena, A., Soh, B.: A new cryptosystem based on hidden order groups. Cryptology ePrint Archive, Report 2006/178 (2006). https://ia.cr/2006/178

  39. Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18

    Chapter  Google Scholar 

  40. Shoup, V.: On formal models for secure key exchange. Technical report, RZ 3120, IBM (1999)

    Google Scholar 

  41. Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_12

    Chapter  Google Scholar 

  42. Wee, H.: On obfuscating point functions. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 523–532. ACM Press, May 2005

    Google Scholar 

  43. Yamakawa, T., Yamada, S., Hanaoka, G., Kunihiro, N.: Self-bilinear map on unknown order groups from indistinguishability obfuscation and its applications. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 90–107. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_6

    Chapter  Google Scholar 

  44. Yamakawa, T., Yamada, S., Hanaoka, G., Kunihiro, N.: Generic hardness of inversion on ring and its relation to self-bilinear map. Cryptology ePrint Archive, Report 2018/463 (2018). https://ia.cr/2018/463

  45. Yun, A.: Generic hardness of the multiple discrete logarithm problem. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 817–836. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_27

    Chapter  Google Scholar 

Download references

Acknowledgements

We thank Justin Holmgren for collaboration in the early stages of this work and for contributing a number of extremely valuable insights. We also thank Alon Rosen for helpful feedback regarding exposition and presentation.

This material is based upon work supported by the ARO and DARPA under Contract No. W911NF-15-C-0227. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the ARO and DARPA.

Author information

Authors and Affiliations

  1. Princeton University, Princeton, USA

    James Bartusek & Fermi Ma

  2. Princeton University & NTT Research, Princeton, USA

    Mark Zhandry

Authors
  1. James Bartusek
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fermi Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mark Zhandry
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to James Bartusek or Fermi Ma .

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    Alexandra Boldyreva

  2. University of California at San Diego, La Jolla, CA, USA

    Daniele Micciancio

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bartusek, J., Ma, F., Zhandry, M. (2019). The Distinction Between Fixed and Random Generators in Group-Based Assumptions. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11693. Springer, Cham. https://doi.org/10.1007/978-3-030-26951-7_27

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-26951-7_27

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-26950-0

  • Online ISBN: 978-3-030-26951-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation